12.13 log

?37. 解数独

class Solution {
private:
    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(isValid(i,j,k,board)){
                        board[i][j]=k;
                        if(backtracking(board)) return true;
                        board[i][j]='.';
                    }
                }
                return false;
            }
        }
        return true;
    }
public:
    bool isValid(int row,int col,char k,vector<vector<char>>& board){
        for(int i=0;i<9;i++){
            if(board[i][col]==k||board[row][i]==k) return false;
        }
        int startRow=row/3;
        int startCol=col/3;
        for(int i=startRow*3;i<startRow*3+3;i++){
            for(int j=startCol*3;j<startCol*3+3;j++){
                if(board[i][j]==k) return false;
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board); 
    }
};

递归的参数为传入的9X9棋盘，返回值为bool类型，因为本题只要求遍历出一个结果就返回，所以递归要有返回值；递归的终止条件没有，因为如果本题无解那么直接最在任何合适数字后return false了，不会向下递归；递归的单层逻辑与n皇后有本质区别，因为n皇后一层只需要放一个数，所以如果符合判断条件直接进入下一层递归，而解数独一层要放不止一个数，所以不能用一维递归，要用两层for循环来进行二维递归，一层行一层列，碰到数字跳过，然后判断该位置是否符合条件，符合就插入数字，进入下一次递归，递归的范围不是一层，而是一个棋盘，如果递归返回值为true则返回true，一直返回上去，如果9个数都没解则return false，最后写return true，因为走到这里一定是填了最后一个数了，棋盘都填满了才能走到这里，然后再一路返回上去。

判断是否符合条件，注意是看在哪个九宫格，注意审题。