leetcode 37 解数独
程序员文章站
2022-05-20 13:00:14
...
题目
leetcode 37 解数独
编写一个程序,通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。
回溯分析
- 每次可以在
1~9
中选择,路径上的每个节点的解空间是[1~9] - 终止条件:路径长度超过81
- 解的判断条件:如果每个空白节点填入的数字都经过规则check,那么终止时,将有一个解,当出现一个解后,直接退出回溯算法,不再搜索解
- 减枝:填入当前节点的值需要符合数组规则
code
class Solution {
bool ok =false;
bool check(vector<vector<char>>& board,int row,int col,char v){
int a = (row/3)*3;
int b = (col/3)*3;
for(int i = 0; i < 9;++i){
if(v == board[row][i] || v == board[i][col])
return false;
}
for(int i = a; i < a+3;++i ){
for(int j = b;j < b+3;++j)
if(v == board[i][j]) return false;
}
return true;
}
void backtrace(vector<vector<char>>& board,int n){
if(n>80){
ok = true;
return;
}
int row = n / 9;
int col = n % 9;
//不用填充
if(board[row][col] != '.'){
return backtrace(board,n+1);
}
for(int i = 1; i <10;++i){
if(check(board,row,col,i+'0')){
board[row][col] = i+'0';
backtrace(board,n+1);
//如果找到了解,直接退出,否则回溯
if(ok) return;;
board[row][col] = '.';
}
}
}
public:
void solveSudoku(vector<vector<char>>& board) {
backtrace(board,0);
}
};