backtracking
预处理board把每个cell能算出来的都填上，再跑backtracking试数
先写backtracking，再写预处理优化
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(vector<vector<char>>& board) {
row.resize(9);
col.resize(9);
sub.resize(9);
s.resize(81);
for (int r = 0; r < 9; ++r) {
for (int c = 0; c < 9; ++c) {
if (board[r][c] != '.') {
int i = board[r][c] - '0';
row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = true;
}
}
}
int change = 0;
do {
change = 0;
for (int r = 0; r < 9; ++r) {
for (int c = 0; c < 9; ++c) {
if (board[r][c] == '.') {
for (int i = 1; i <= 9; ++i) {
if (!row[r][i] && !col[c][i] && !sub[r / 3 * 3 + c / 3][i]) {
s[r * 9 + c].insert(i);
}
}
if (s[r * 9 + c].size() == 1) {
int i = *s[r * 9 + c].begin();
board[r][c] = '0' + i;
++change;
row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = true;
}
}
}
}
} while (change > 0);
dfs(board, 0);
}
bool dfs(vector<vector<char>> &b, int idx) {
if (idx == 81) return true;
int r = idx / 9, c = idx % 9;
if (b[r][c] != '.') return dfs(b, idx + 1);
for (int i : s[idx]) {
if (row[r][i] || col[c][i] || sub[r / 3 * 3 + c / 3][i]) continue;
b[r][c] = '0' + i;
row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = true;
if (dfs(b, idx + 1)) return true;
row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = false;
}
b[r][c] = '.';
return false;
}
vector<bitset<10>> row, col, sub;
vector<unordered_set<int>> s;
};
|
没有预处理
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
| class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
h = [[False] * 10 for _ in range(9)]
v = [[False] * 10 for _ in range(9)]
s = [[False] * 10 for _ in range(9)]
for r in range(9):
for c in range(9):
x = board[r][c]
if x != '.':
x = int(x)
h[r][x] = v[c][x] = s[r // 3 * 3 + c // 3][x] = True
def dfs(idx):
if idx == 81: return True
r, c = divmod(idx, 9)
if board[r][c] != '.': return dfs(idx + 1)
for x in range(1, 10):
if h[r][x] or v[c][x] or s[r // 3 * 3 + c // 3][x]: continue
board[r][c] = str(x)
h[r][x] = v[c][x] = s[r // 3 * 3 + c // 3][x] = True
if dfs(idx + 1): return True
h[r][x] = v[c][x] = s[r // 3 * 3 + c // 3][x] = False
board[r][c] = '.'
return False
dfs(0)
|
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
| class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
row.resize(9);
col.resize(9);
sub.resize(9);
for (int r = 0; r < 9; ++r) {
for (int c = 0; c < 9; ++c) {
if (board[r][c] != '.') {
int i = board[r][c] - '0';
row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = true;
}
}
}
dfs(board, 0);
}
bool dfs(vector<vector<char>> &b, int idx) {
if (idx == 81) return true;
int r = idx / 9, c = idx % 9;
if (b[r][c] != '.') return dfs(b, idx + 1);
for (int i = 1; i <= 9; ++i) {
if (row[r][i] || col[c][i] || sub[r / 3 * 3 + c / 3][i]) continue;
b[r][c] = '0' + i;
row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = true;
if (dfs(b, idx + 1)) return true;
row[r][i] = col[c][i] = sub[r / 3 * 3 + c / 3][i] = false;
b[r][c] = '.';
}
return false;
}
vector<bitset<10>> row, col, sub;
};
|