LeetCode 37 解数独 - 回溯解法
https://leetcode.cn/problems/sudoku-solver/
思路
一个一个填，而填每个时要检查1-9的合法性（检查合法较为麻烦），然后递归的调用。
错误
for(int i =1;i<=9;i++){
if(check(board,row,col,i)){
board[row][col] = i
write(....) 下一层调用
board[row][col] = '.'
}
}
这样是有问题的，到最后没有修改board的值，因为执行完 write 函数后，立即会又改为 . ，这样到最后 board 又被修改回去了，错误的代码如下：
class Solution {
public:
bool check(vector<vector<char>>& board, int row, int col, int num) {
for (int i = 0; i < 9; i++) {
// 行：row 列：i
if (board[row][i] - '0' == num)
return false;
}
for (int i = 0; i < 9; i++) {
if (board[i][col] - '0' == num)
return false;
}
for (int i = (row / 3) * 3; i < (row / 3) * 3 + 3; i++) {
for (int j = (col / 3) * 3; j < (col / 3) * 3 + 3; j++) {
if (board[i][j] - '0' == num)
return false;
}
}
return true;
}
void write(vector<vector<char>>& board, int row, int col) {
if (row == 9)
return;
if (board[row][col] == '.') {
for (int i = 1; i <= 9; i++) {
if (check(board, row, col, i)) {
board[row][col] = (char)(i + '0');
write(board, row + 1, (col + 1) % 9);//这里row和col计算不对
board[row][col] = '.';
}
}
}
else{
write(board, row + 1, (col + 1) % 9);
}
}
void solveSudoku(vector<vector<char>>& board) { write(board, 0, 0); }
};
改正
我们要做的就是，在得到合法状态后，不要执行后面的 board[row][col] = '.'; ，所以需要 return， 这就需要下层调用向上返回是否找到合法状态
返回 true 表示找到合法状态， 这时直接return，不执行后面的 board[row][col] = '.' 。
for(int i =1;i<=9;i++){
if(check(board,row,col,i)){
board[row][col] = i
if(write(....) 下一层调用) return;
board[row][col] = '.'
}
}
小插曲： 我的代码计算 next_row next_col 有误，正确的应该是 在列到8时 row 要加一。只用取余函数是不对的。
代码
class Solution {
public:
bool check(vector<vector<char>>& board, int row, int col, int num) {
for (int i = 0; i < 9; i++) {
// 行：row 列：i
if (board[row][i] - '0' == num)
return false;
}
for (int i = 0; i < 9; i++) {
if (board[i][col] - '0' == num)
return false;
}
for (int i = (row / 3) * 3; i < (row / 3) * 3 + 3; i++) {
for (int j = (col / 3) * 3; j < (col / 3) * 3 + 3; j++) {
if (board[i][j] - '0' == num)
return false;
}
}
return true;
}
bool write(vector<vector<char>>& board, int row, int col) {
if (row == 9)
return true;
int next_row = col==8?row+1:row;
int next_col = (col + 1) % 9;
if (board[row][col] == '.') {
for (int i = 1; i <= 9; i++) {
if (check(board, row, col, i)) {
board[row][col] = (char)(i + '0');
if (write(board, next_row, next_col)) {
return true;
};
board[row][col] = '.';
}
}
return false;
} else {
return write(board, next_row, next_col);
}
}
void solveSudoku(vector<vector<char>>& board) { write(board, 0, 0); }
};