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-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
The '.' character indicates empty cells.
Solution
对于每一个空缺的位置，我们需要遍历所有的数字进行 \(check\)
\(check\) 的时候我们需要对于所在行，所在列，以及小九宫格进行检查，这里注意九宫格检查的写法
点击查看代码
class Solution {
private:
bool check(char c, vector<vector<char>>& board, int row, int col){
for(int i=0;i<9;i++){
if(board[i][col]==c)return false;
if(board[row][i]==c)return false;
if(board[3*(row/3)+i/3][3*(col/3)+i%3]==c)return false;
}
return true;
}
bool dfs(vector<vector<char>>& board){
int nr = board.size(), nc = board.size();
for(int i=0;i<nr;i++){
for(int j=0;j<nc;j++){
if(board[i][j]=='.'){
for(char c = '1';c<='9';c++){
if(check(c,board,i,j)){
board[i][j]=c;
if(dfs(board))return true;
else board[i][j]='.';
}
}
return false;
}
}
}
return true;
}
public:
void solveSudoku(vector<vector<char>>& board) {
dfs(board);
}
};