思路

跟n皇后很相似，都是检验状态是否合法，合法就填进去然后进行下一步的dfs，在n皇后中，我们使用了check()函数，在每下一步棋之前都检查是否下了之后横竖斜对四条线上是否有其他皇后来判断是否合法，我们这一道题也可以用同样的方法，但是在这一道题我们进行进阶，将check()的时间复杂度由O(n)降到O(1)，具体来说，原本要检查27个格子，现在只需要3次判断就可以了。这就是————状态压缩。
我们可以用一个数组来记录某行/某列/某块中某个数字是否出现过，这就将复杂度又降低了n倍，由于本题n恒为9，所以就是降低了9倍，具体的，st1[x][i],st2[y][i],st3[x/3][y/3][i]分别表示第x行中、第y列中、xy对应的九宫格中是否出现过数字i。

未优化check()版

class Solution {
public:
    char ans[9][9];
    bool check(vector<vector<char>>& a,int x,int y,int v)
    {
        int mx=x/3*3,my=y/3*3;
        for(int i=0;i<9;i++)
        {
            if(a[i][y]==v+'0')return false;
            if(a[x][i]==v+'0')return false;
            if(a[mx+i/3][my+i%3]==v+'0')return false;
        }
        return 1;
    }
    bool dfs(vector<vector<char>>& a,int x,int y)
    {
        if(y==9)x+=1,y=0;
        if(x==9)return true;
        if(a[x][y]!='.')return dfs(a,x,y+1);
        for(int i=1;i<=9;i++)
        {
            if(check(a,x,y,i))
            {
                a[x][y]=i+'0';
                if(dfs(a,x,y+1))return true;
                a[x][y]='.';
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char>>& a) {
        dfs(a,0,0);
    }
};

状态压缩版

class Solution {
public:
    char ans[9][9];
    bool st1[15][15],st2[15][15],st3[5][5][15];
    bool dfs(vector<vector<char>>& a,int x,int y)
    {
        if(y==9)x+=1,y=0;
        if(x==9)return true;
        if(a[x][y]!='.')return dfs(a,x,y+1);
        for(int i=1;i<=9;i++)
        {
            if(!st1[x][i]&&!st2[y][i]&&!st3[x/3][y/3][i])
            {
                a[x][y]=i+'0';
                st1[x][i]=true,st2[y][i]=true,st3[x/3][y/3][i]=true;
                if(dfs(a,x,y+1))return true;
                a[x][y]='.';
                st1[x][i]=false,st2[y][i]=false,st3[x/3][y/3][i]=false;
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char>>& a) {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(a[i][j]!='.')
                {
                    int val=a[i][j]-'0';
                    st1[i][val]=true;
                    st2[j][val]=true;
                    st3[i/3][j/3][val]=true;
                }
            }
        }
        dfs(a,0,0);
    }
};