题解:
1、确定回溯函数参数
bool backtracking(vector<vector<char>>& board)
2、确定递归终止条件
无终止条件 填满为止
3、单层搜索过程
双重循环遍历棋盘,然后递归遍历某位置放9个数字的可能性
class Solution {
public:
bool isVaild(int row,int col,char val,vector<vector<char>>& board){
//判断行是否重复
for(int i = 0;i<9;i++){
if(board[row][i]==val){
return false;
}
}
//判断列是否重复
for(int i = 0;i<9;i++){
if(board[i][col]==val){
return false;
}
}
int startrow = (row/3)*3;
int startCol = (col/3)*3;
//判断九宫格是否重复
for(int i = startrow;i<startrow+3;i++){
for(int j = startCol;j<startCol+3;j++){
if(board[i][j] == val){
return false;
}
}
}
return true;
}
bool backtracking(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] != '.'){
continue;
}
//为空格 填数字
for(char k = '1';k<='9';k++){
if(isVaild(i,j,k,board)){
//有效
board[i][j] = k;
if(backtracking(board)){
return true;
}
board[i][j]='.';
}
}
//9个数都不行
return false;
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};