[LeetCode]37. Sudoku Solver

Problem

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. Empty cells are indicated by the character ‘.’.

A sudoku puzzle…

…and its solution numbers marked in red.

Note:

The given board contain only digits 1-9 and the character ‘.’. You may assume that the given Sudoku puzzle will have a single unique solution. The given board size is always 9x9.

Solution

### Analysis

回溯法. 针对每个”.”的位置,尝试1-9每个数字,确保当前数字在当前行,当前列, 以及3*3小方块中出现过. 填充之后,接着递归调用,知道所有’.’都被填充完毕,找到了一个解.

回溯法,本质上一种递归方法,但也有自己独特的部分,即剪枝, 当判断当前情况计算接着运行,也不会找到解, 就及时终止,返回,尝试另一种方法.

这里的终止情况是所有”.”被填充完, 需要一个辅助函数,确定从当前点填充之后能否找到解,如果找到,依次返回;如果找不到,返回false, 尝试下一个可能.

Code

方法一

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
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
if (board.empty() || board.size() != 9 || board[0].size() != 9) return;

dfs(board, 0, 0);
}
private:
bool isValid(vector<vector<char>>& board, int i, int j){
// 行检测, 列检测
for (int t=0; t< 9; t++){
if (t != j && board[i][t] == board[i][j]) return false;
if (t != i && board[t][j] == board[i][j]) return false;
}
// 检测小方块
int row_start = i / 3, col_start = j / 3;
for (int t=row_start*3; t < row_start*3+3; t++){
for (int k=col_start*3; k < col_start*3+3; k++)
if(t != i && k != j && board[t][k] == board[i][j]) return false;
}
return true;
}

bool dfs(vector<vector<char>>& board, int i, int j){
// 一行一行的填充,当当前行超出有效范围时,填充完毕,返回true.
if (i >= 9) return true;
// 当前行填充完,进行下一行的填充.
if (j >= 9) return dfs(board, i+1, 0);// 坐标有效性检查

if (board[i][j] == '.'){// 需要填充
for (char a='1'; a<= '9'; a++){
board[i][j] = a;
if(isValid(board, i, j)){//数值填充有效性检查
if (dfs(board, i, j+1)) return true;// 递推, 达到终止条件
}
// 没查找, 回溯
board[i][j] = '.';// for循环结束后,最终到最后,返回false, 提前终止
}
}
else// 当前位置是数字,跳过
return dfs(board, i, j+1);

return false;// 填充失败,是从board[i][j] == '.',执行过来的
// 说明当前位置,尝试所有的数字都不行,返回上一层.

}
};

方法二

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
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
if (board.empty() || board.size() != 9 || board[0].size() != 9) return;

dfs(board);
}
private:
bool isValid(vector<vector<char>>& board, int i, int j, char ch){
// 行检测, 列检测
for (int t=0; t< 9; t++){
if (t != j && board[i][t] == ch) return false;
if (t != i && board[t][j] == ch) return false;
}
// 检测小方块
int row_start = i / 3, col_start = j / 3;
for (int t=row_start*3; t < row_start*3+3; t++){
for (int k=col_start*3; k < col_start*3+3; k++)
if(t != i && k != j && board[t][k] == ch) return false;
}
return true;
}

bool dfs(vector<vector<char>>& board){
// 不需要位置参数.
// 每次调用时,遍历所有的位置,找到没有填充的空缺位置
for (int i=0; i< board.size(); i++){
for (int j=0; j< board[0].size(); j++){
if (board[i][j] == '.'){//需要填充
for (char ch='1'; ch <='9'; ch++){// 尝试各种可能
if(isValid(board, i, j, ch)){
board[i][j] = ch;
if (dfs(board)) return true;
board[i][j] = '.';
}
}// 都不行,返回上一层;之前已经完成了位置还原.
return false;
}
}
}
// 执行完成,填充完所有的"."
return true;
}
};

两种方法都想到过,关键是把两种方法合并到一块了,而且什么时候递推,什么时候回归,没有想清楚.Go on.

Anyone can be anything.

References

https://segmentfault.com/a/1190000016499520

https://www.cnblogs.com/grandyang/p/4421852.html

您的支持就是我更新的最大动力!谢谢!