博客

题目分析：本题属于深度遍历DFS的一个经典例子。按照从左往右，从上到下的顺序依次填充空格，用‘1’~‘9’之间的数进行试探，若发现填充的数不满足三条规则中的任意一条，就换一个数进行填充，若都不行，则回溯到上一层（即上一个要填充的空格，更换这个空格的数字）。一旦出现一种正确解，即返回。

代码展示：

class Solution {
public:
    bool dfs(vector<vector<char>>& board,int i,int j,int n){
        if(j>=n)
            return dfs(board,i+1,0,n);
        else if(i>=n)
            return true;
        else if(board[i][j]!='.')
            return dfs(board,i,j+1,n);
        else{
            for(int k=1;k<=n;k++){
                board[i][j] = char(k+'0');
                if(isValid(board,i,j,n)){
                    if(dfs(board,i,j+1,n))
                        return true;
                }
                board[i][j] = '.';
            }
        }
        return false;
    }
    
    bool isValid(vector<vector<char>>& board,int i,int j,int n){
        for(int k=0;k<n;k++){
            if(board[i][k]==board[i][j] && k!=j)
                return false;
        }
        for(int k=0;k<n;k++){
            if(board[k][j]==board[i][j] && k!=i)
                return false;
        }
        int x = i/3*3;
        int y = j/3*3;
        for(int u=x;u<x+3;u++){
            for(int v=y;v<y+3;v++){
                if(board[u][v]==board[i][j] && (u!=i || v!=j))
                    return false;
            }
        }
        return true;
    }
    
    void solveSudoku(vector<vector<char>>& board) {
        dfs(board,0,0,9);
    }
};