LeetCode-37 Sudoku Solver

37. Sudoku Solver

求解数独。前两天做了验证数独那道题,当时对于遍历hash的使用有了一些感悟,但看这道题时候特别头疼。这两天HackerRank也刷了一下,对于DFS和BFS的理解加深了一些,渐渐的思路就变得清晰。其实是很暴力的解法,但把他转化为代码,对几天前的我来说还有一些难度。经过这两天的学习,总算是可以勉强完成,但参考别人的答案后,果然进步空间还比较大。

我之前的版本,dfs函数没有加入i与j两个变量,每次调用都重新扫描一遍需要填的空,这导致效率很低,引入i和j后果然好了很多。另外之前的dfs是void不返回值,通过一个cnt变量计算总共的空数,当cnt等于0时停止,但由于我们需要在中途中断dfs函数(找到正确的解时,否则答案会被填回’.’),采用void的类型也会比较难以中断。借鉴了别人的解法,让dfs返回一个值来判定是否完成整个数独,这样好了很多。

算法解释:

  • solveSudoku: 功能函数入口。
  • dfs:深度优先搜索函数。
    • 输入整个表和一个坐标。
    • 如果该坐标已有数字,搜索下一个格子j++;当j==9,说明这一排已搜索完,搜索下一排的第一个格子i++, j=0;如果所有的行都已搜索完,说明所有的格子都被正确的填入了数字,则返回true
    • 如果该坐标下没有数字'.',从1开始填入,并验证该数字是否可行isValid(board, i, j)。如果不可行,擦除填入的数字并填入下一个数字直到9。如果可行,搜索下一个格子,并直到整张表被填完。
    • 如果一个没有填的格子所有的数字都不可行,代表之前填的数字有错,那么返回false
  • isValid:验证某个格子里的数字是否可行,是之前验证数独的简化版,因为只用验证特定位置的数字。
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
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
dfs(board, 0, 0);
}

bool dfs(vector<vector<char>>& board, int i, int j){
if (i>=9) return true;
if (j>=9) return dfs(board, i+1, 0);

if (board[i][j]=='.'){
for (int num = 1; num <= 9; num++){
board[i][j] = (char)(num+'0');

if(isValid(board, i, j)){
if(dfs(board, i, j+1)) return true;
}

board[i][j] = '.';
}
}else {
return dfs(board, i, j+1);
}
return false;
}

bool isValid(vector<vector<char>>& board, int i, int j){
for (int col = 0; col < 9; col++){
if (col != j && board[i][j]==board[i][col]) return false;
}
for (int row = 0; row < 9; row++){
if (row != i && board[i][j]==board[row][j]) return false;
}
for (int row = i / 3 * 3; row < i / 3 * 3 + 3; ++row) {
for (int col = j / 3 * 3; col < j / 3 * 3 + 3; ++col) {
if ((row != i || col != j) && board[i][j] == board[row][col]) return false;
}
}
return true;
}
};

Reference

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