https://leetcode-cn.com/problems/sudoku-solver/
首先，采用非常暴力的递归回溯，并使用了 Valid Sudoku 中对数独中数字进行验证的方法。需要注意返回 true 和 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
| func solveSudoku(board [][]byte) {
solve(&board)
}
func solve(board *[][]byte) bool{
for i:=0;i<9;i++ {
for j:=0;j<9;j++ {
if (*board)[i][j]=='.' {
var k byte
for k='1';k<='9';k++ {
if isValid(board,i,j,k) {
(*board)[i][j]=k
if solve(board) {
return true
}else{
(*board)[i][j]='.'
}
}
}
return false
}
}
}
return true
}
func isValid(board *[][]byte, row,col int, val byte) bool {
for i:=0;i<9;i++ {
if (*board)[i][col]==val || (*board)[row][i]==val || (*board)[(row/3)*3+i/3][(col/3)*3+i%3]==val {
return false
}
}
return true
}
|
下面是一个毫无新意的C++版本。
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
| class Solution {
public:
bool isValid(vector<vector<char>>& board, int m, int n, char k) {
for(int i=0; i<9; ++i) {
if(k == board[m][i] || k == board[i][n] || k == board[m/3*3+i/3][n/3*3+i%3]) {
return false;
}
}
return true;
}
bool solve(vector<vector<char>>& board) {
for(int i=0; i<9; ++i) {
for(int j=0; j<9; ++j) {
if(board[i][j] == '.') {
for(int k='1'; k<='9'; ++k) {
if(isValid(board, i, j, k)) {
board[i][j] = k;
if(solve(board)) return true;
else board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
solve(board);
}
};
|
在 Discuss 中还有一种更牛的 Solution，他通过自己为 Sudoku 中的每一个格子建立一个 cell 结构体来存储可能的信息，然后再通过按可能填入数字的多少进行排序，以减少 backtrack 的次数。