leetcode37. 解数独

思路

依次枚举每个空位的1-9，如果有重复则换一个数字，没重复继续下一个位置。

class Solution {
public:
    bool isValid(int row,int col,char t,vector<vector<char>>& board){
        for(int i=0;i<9;i++){
            if(board[row][i]==t)return false;
        }
         for(int i=0;i<9;i++){
            if(board[i][col]==t)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]==t)return false;
            }
        }
        return true;
    }
    bool dfs(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 c='1';c<='9';c++){
                    if(isValid(i,j,c,board)){
                        board[i][j]=c;
                        if(dfs(board))return true;
                        board[i][j]='.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        dfs(board);
    }
};