#Problem

#⭐️⭐️⭐️⭐️⭐️

Sudoku Solver

#Solution

为什么这道题是Holy Moly, 因为这么经典的backtracking题每次都做不对.

#Mistake

主要的问题在于这题跟N-Queue一样, 最好的是每一行每一列依次尝试, 而不是像dfs那样四个方向无脑尝试.

为什么?

想想backtrack到最后怎么样才算结束? 如果是四个方向扩展的话, 那么backtrack大概长这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
boolean backtrack(char[][] board, int x, int y) {
if (board[x][y] == '.') {
for (char k = '1'; k <= '9'; k++) {
board[x][y] = k;
for (int[] dir : dirs) {
int newX = x + dir[0];
int newY = y + dir[1];
if (backtrack(board, newX, newY)) return true;
}
board[x][y] = '.';
}
} else {
for (int[] dir : dirs) {
int newX = x + dir[0];
int newY = y + dir[1];
if (backtrack(board, newX, newY)) return true;
}
}
}

这个思路虽然看上去很麻烦, 但至少是make sense的. 可是有一个问题一直解决不了: 什么时候backtrack才会return true???

  • x == 9 && y == 9的时候? 显然不对啊. 往四个方向扩展怎么可能x和y同时都越界??
  • x == 9 || y == 9的时候? 明显也是不对的.

正确的思路应该是要维护一个remainingDots, 当remainingDots == 0的时候才能说明solve了整个sudoku, 才能return true.

但是这个backtrack法有点过于麻烦了.

#Correct solution

正确的思路应该像N-queen那种方法一样, 每一行每一列依次尝试. 这样的话边界条件就好处理的多了.

1
2
3
4
5
6
if x == 9: return true;
if y == 9: return backtrack(board, x + 1, 0);
if x, y not valid: return false;
if (board[x][y] != '.') return backtrack(board, x, y + 1);
// 1-9挨个填进board[x][y]看能不能solve.

#Code

#Java
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
class Solution {
public void solveSudoku(char[][] board) {
solve(board,0, 0);
}
private boolean solve(char[][] board, int x, int y) {
if (x == 9) {
return true;
} else if (y == 9) {
return solve(board,x + 1, 0);
} else if (board[x][y] != '.') {
return solve(board, x, y + 1);
}
for (char k = '1'; k <= '9'; k++) {
board[x][y] = k;
if (isValid(board, x, y)) {
if (solve(board, x, y + 1)) return true;
}
}
board[x][y] = '.';
return false;
}
private boolean isValid(char[][] board, int x, int y) {
int[] visited = new int[10];
for (int i = 0; i < 9; i++) {
if (board[x][i] != '.') {
if (visited[board[x][i] - '0'] == 1) return false;
visited[board[x][i] - '0'] = 1;
}
}
Arrays.fill(visited, 0);
for (int i = 0; i < 9; i++) {
if (board[i][y] != '.') {
if (visited[board[i][y] - '0'] == 1) return false;
visited[board[i][y] - '0'] = 1;
}
}
Arrays.fill(visited, 0);
int xx = x / 3 * 3;
int yy = y / 3 * 3;
for (int i = xx; i < xx + 3; i++) {
for (int j = yy; j < yy + 3; j++) {
if (board[i][j] != '.') {
if (visited[board[i][j] - '0'] == 1) return false;
visited[board[i][j] - '0'] = 1;
}
}
}
return true;
}
}

Comments