友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

微信

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

37. 解数独

LeetCode - 37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。

  2. 数字 1-9 在每一列只能出现一次。

  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 . 表示。

示例 1：

0037 01
0037 02 
输入：board = [
 ["5","3",".",".","7",".",".",".","."],
 ["6",".",".","1","9","5",".",".","."],
 [".","9","8",".",".",".",".","6","."],
 ["8",".",".",".","6",".",".",".","3"],
 ["4",".",".","8",".","3",".",".","1"],
 ["7",".",".",".","2",".",".",".","6"],
 [".","6",".",".",".",".","2","8","."],
 [".",".",".","4","1","9",".",".","5"],
 [".",".",".",".","8",".",".","7","9"]]
输出：[
 ["5","3","4","6","7","8","9","1","2"],
 ["6","7","2","1","9","5","3","4","8"],
 ["1","9","8","3","4","2","5","6","7"],
 ["8","5","9","7","6","1","4","2","3"],
 ["4","2","6","8","5","3","7","9","1"],
 ["7","1","3","9","2","4","8","5","6"],
 ["9","6","1","5","3","7","2","8","4"],
 ["2","8","7","4","1","9","6","3","5"],
 ["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

  • board.length == 9

  • board[i].length == 9

  • board[i][j] 是一位数字或者 .

  • 题目数据 保证 输入数独仅有一个解

思路分析

这道题特别需要关注的点是：只要找到一个解就可以了，不需要求全部解。所以，需要重点思考的是，如何在找到第一个解时，就立即停止搜索。

尝试画一下递归树！

位运算牛逼：使用 1~9 的比特位来表示是否已经存在某个数字。

使用异或而不是使用或，或只能用于初次标记（从 0 开始标记，所以，无论是异或还是或，跟一个 1 相计算，都可以把 1`保留下来）。而异或的优点是，在选择和撤销时，可以使用相同的操作（原始比特是 `0，异或后是 1，再异或又是 0）。

行列块相或 rows | columns | boxes 后，还是 0 的比特位，就是需要待填充的值。拿题目实例来举例：

   84                             1010100  rows[0]
  128                            10000000  column[2]
  436                           110110100  box[0][0] 左上角的9个方格
  500                           111110100  rows[0] | columns[2] | boxes[0][0] = or
 -501    11111111111111111111111000001011  ~or
   11                                1011  ~or & 0x1FF = mask
    1                                   1  mask & (-mask) 取出最后一位 1 的下标

                                           mask &= (mask - 1) 演进到下一步
0037 03

  • 一刷

  • 二刷

  • 二刷（引入步进）

  • 三刷

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

/**
 *  * @author D瓜哥 · https://www.diguage.com
 *  * @since 2020-03-25 09:34
 */
public void solveSudoku(char[][] board) {
    backtrack(board, 0);
}

/**
 * Runtime: 17 ms, faster than 35.23% of Java online submissions for Sudoku Solver.
 * Memory Usage: 37 MB, less than 21.05% of Java online submissions for Sudoku Solver.
 */
private boolean backtrack(char[][] board, int step) {
    int len = board.length;
    if (step == len * len) {
        return true;
    }
    int y = step / len;
    int x = step % len;

    for (int i = y; i < len; i++) {
        for (int j = x; j < len; j++) {
            if (board[i][j] != '.') {
                return backtrack(board, step + 1);
            }
            for (char c = '1'; c <= '9'; c++) {
                if (!isValid(board, i, j, c)) {
                    continue;
                }
                board[i][j] = c;
                System.out.printf("y=%d,x=%d, num=%s, step=%d %n",
                        y, x, c, step);
                Printers.printMatrix(board);
                if (backtrack(board, step + 1)) {
                    return true;
                }
                board[i][j] = '.';
            }
            return false;
        }
    }
    return false;
}

private boolean isValid(char[][] board, int y, int x, char c) {
    for (int i = 0; i < 9; i++) {
        if (board[(y / 3) * 3 + i / 3][(x / 3) * 3 + i % 3] == c
                || board[y][i] == c
                || board[i][x] == c) {
            return false;
        }
    }
    return true;
}

/**
 * Copy From
 */
private boolean backtrackXY(char[][] board, int y, int x) {
    int len = board.length;
    if (x == len) {
        return backtrackXY(board, y + 1, 0);
    }
    if (y == len) {
        return true;
    }
    for (int i = y; i < len; i++) {
        for (int j = x; j < len; j++) {
            if (board[i][j] != '.') {
                return backtrackXY(board, i, j + 1);
            }
            for (char c = '1'; c <= '9'; c++) {
                if (!isValid(board, i, j, c)) {
                    continue;
                }
                board[i][j] = c;
                System.out.printf("y=%d,x=%d, num=%s %n", i, j, c);
                Printers.printMatrix(board);
                if (backtrackXY(board, i, j + 1)) {
                    return true;
                }
                board[i][j] = '.';
            }
            return false;
        }
    }
    return false;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

/**
 * * @author D瓜哥 · https://www.diguage.com
 * * @since 2024-09-11 10:59:08
 */
public void solveSudoku(char[][] board) {
  backtracking(board);
}

private boolean backtracking(char[][] board) {
  for (int r = 0; r < board.length; r++) {
    for (int c = 0; c < board[r].length; c++) {
      if (board[r][c] != '.') {
        continue;
      }
      // 根据限制条件，筛选出可选字符，否则重复判断
      char[] chars = selectChars(board, r, c);
      for (char sc : chars) {
        board[r][c] = sc;
        printMatrix(board);
        if (backtracking(board)) {
          return true;
        }
        board[r][c] = '.';
      }
      return false;
    }
  }
  return true;
}

private char[] selectChars(char[][] board, int row, int column) {
  char[] chars = new char[9];
  int length = 9;
  for (int i = 0; i < chars.length; i++) {
    chars[i] = (char) ('1' + i);
  }
  for (int i = 0; i < board.length; i++) {
    char c = board[i][column];
    if (c != '.' && chars[c - '1'] != '.') {
      chars[c - '1'] = '.';
      length--;
      if (length == 0) {
        return new char[0];
      }
    }
  }
  for (int i = 0; i < board[row].length; i++) {
    char c = board[row][i];
    if (c != '.' && chars[c - '1'] != '.') {
      chars[c - '1'] = '.';
      length--;
      if (length == 0) {
        return new char[0];
      }
    }
  }
  row = (row / 3) * 3;
  column = (column / 3) * 3;
  for (int i = row; i < row + 3; i++) {
    for (int j = column; j < column + 3; j++) {
      char c = board[i][j];
      if (c != '.' && chars[c - '1'] != '.') {
        chars[c - '1'] = '.';
        length--;
        if (length == 0) {
          return new char[0];
        }
      }
    }
  }
  char[] result = new char[length];
  for (int i = chars.length - 1; i >= 0; i--) {
    if (chars[i] != '.') {
      result[--length] = chars[i];
    }
  }
  return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

/**
 * * @author D瓜哥 · https://www.diguage.com
 * * @since 2024-09-11 10:59:08
 */
public void solveSudoku(char[][] board) {
  backtracking(board, 0);
}

private boolean backtracking(char[][] board, int step) {
  int row = step / board.length;
  int column = step % board.length;
  for (int r = row; r < board.length; r++) {
    for (int c = column; c < board[r].length; c++) {
      if (board[r][c] != '.') {
        return backtracking(board, step + 1);
      }
      // 根据限制条件，筛选出可选字符，否则重复判断
      char[] chars = selectChars(board, r, c);
      for (char sc : chars) {
        board[r][c] = sc;
        printMatrix(board);
        if (backtracking(board, step + 1)) {
          return true;
        }
        board[r][c] = '.';
      }
      return false;
    }
  }
  return true;
}

private char[] selectChars(char[][] board, int row, int column) {
  char[] chars = new char[9];
  int length = 9;
  for (int i = 0; i < chars.length; i++) {
    chars[i] = (char) ('1' + i);
  }
  for (int i = 0; i < board.length; i++) {
    char c = board[i][column];
    if (c != '.' && chars[c - '1'] != '.') {
      chars[c - '1'] = '.';
      length--;
      if (length == 0) {
        return new char[0];
      }
    }
  }
  for (int i = 0; i < board[row].length; i++) {
    char c = board[row][i];
    if (c != '.' && chars[c - '1'] != '.') {
      chars[c - '1'] = '.';
      length--;
      if (length == 0) {
        return new char[0];
      }
    }
  }
  row = (row / 3) * 3;
  column = (column / 3) * 3;
  for (int i = row; i < row + 3; i++) {
    for (int j = column; j < column + 3; j++) {
      char c = board[i][j];
      if (c != '.' && chars[c - '1'] != '.') {
        chars[c - '1'] = '.';
        length--;
        if (length == 0) {
          return new char[0];
        }
      }
    }
  }
  char[] result = new char[length];
  for (int i = chars.length - 1; i >= 0; i--) {
    if (chars[i] != '.') {
      result[--length] = chars[i];
    }
  }
  return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

/**
 * * @author D瓜哥 · https://www.diguage.com
 * * @since 2024-09-11 10:59:08
 */
public void solveSudoku(char[][] board) {
  // 使用比特位来标注已经存在哪些字符
  int[] rows = new int[9];
  int[] columns = new int[9];
  int[][] boxes = new int[3][3];
  List<int[]> positions = new ArrayList<>();
  for (int i = 0; i < board.length; i++) {
    for (int j = 0; j < board.length; j++) {
      char c = board[i][j];
      if (c == '.') {
        // 记录需要填充的位置
        positions.add(new int[]{i, j});
      } else {
        int num = c - '0' - 1;
        flip(rows, columns, boxes, i, j, num);
      }
    }
  }
  // 使用回溯尝试填充
  backtrack(board, rows, columns, boxes, positions, 0);
}

private boolean backtrack(char[][] board,
                          int[] rows, int[] columns, int[][] boxes,
                          List<int[]> positions, int index) {
  if (positions.size() == index) {
    return true;
  }
  int[] pos = positions.get(index);
  int r = pos[0];
  int c = pos[1];
  // 打开这些输出，就超时。关闭，就能超过 90%
  //    System.out.printf("%5d   %33s\n", rows[r], Integer.toBinaryString(rows[r]));
  //    System.out.printf("%5d   %33s\n", columns[c], Integer.toBinaryString(columns[c]));
  //    System.out.printf("%5d   %33s\n", boxes[r / 3][c / 3], Integer.toBinaryString(boxes[r / 3][c / 3]));
  int orNum = rows[r] | columns[c] | boxes[r / 3][c / 3];
  //    System.out.printf("%5d   %33s\n", orNum, Integer.toBinaryString(orNum));
  int negNum = ~orNum;
  //    System.out.printf("%5d   %33s\n", negNum, Integer.toBinaryString(negNum));
  int mask = negNum & 0x1FF;
  //    System.out.printf("%5d   %33s\n", mask, Integer.toBinaryString(mask));
  for (; mask != 0; mask &= (mask - 1)) {
    int digitMask = mask & (-mask);
    //      System.out.printf("%5d   %33s\n", digitMask, Integer.toBinaryString(digitMask));
    //      System.out.printf("%5d   %33s\n", digitMask - 1, Integer.toBinaryString(digitMask - 1));
    int num = Integer.bitCount(digitMask - 1);
    //      System.out.println(num);
    flip(rows, columns, boxes, r, c, num);
    board[r][c] = (char) (num + '0' + 1);
    boolean result = backtrack(board, rows, columns, boxes, positions, index + 1);
    if (result) {
      return true;
    }
    flip(rows, columns, boxes, r, c, num);
  }
  return false;
}

private void flip(int[] rows, int[] columns, int[][] boxes,
                  int i, int j, int num) {
  int digit = 1 << num;
  // 这里使用异或而不是使用或，或只能用于初次标记。
  // 而异或的优点是，在选择和撤销时，可以使用相同的操作。
  rows[i] ^= digit;
  columns[j] ^= digit;
  boxes[i / 3][j / 3] ^= digit;
}

参考资料

  1. 搞懂回溯算法，我终于能做数独了

  2. 37. 解数独 - 「代码随想录」带你学透回溯算法！

← Previous: 36. Valid Sudoku | ↑ Up: LeetCode 解题笔记 | Next: 38. Count and Say →