class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]!='.'){
                    mt[0][i][board[i][j]-'1'] = true;
                    mt[1][j][board[i][j]-'1'] = true;
                    flag[i][j] = true;
                    n++;
                }
            }
        }
        for(int i=0;i<9;i++){
            for(int j=i/3*3;j<3+i/3*3;j++){
                for(int k=0+i%3*3;k<3+i%3*3;k++){
                    if(board[j][k]!='.'){
                        mt[2][i][board[j][k]-'1'] = true;
                    }
                }
            }
        }
        addNode(board,0,0);
    }
private:
    int n;
    bool flag[10][10],mt[3][10][10];
    bool isSudoku(vector<vector<char>>board,int p,int q,char c){
        int t = nSudoku(p,q);
        // cout<<p<<q<<t<<endl;
        if(mt[0][p][c-'1']||mt[1][q][c-'1']||mt[2][t][c-'1'])
            return false;
        return true;
    }
    int nSudoku(int p,int q){
        int i = p/3,j = q/3;
        return i*3+j;
    }
    bool addNode(vector<vector<char>>&board,int p,int q){
        if(n==81){        
            return true;
        }
        bool f2 = false,f3;
        int t,i,j;
        char c2;
        stack<int>s1,s2;
        for(i=p;i<9;i++){
            f3 = false;
            for(j=0;j<9;j++){
                if(board[i][j]=='.'){
                    f3 = true;
                    break;
                }
            }
            if(f3)break;
        }
        p = i;
        q = j;
        for(char c='1';c<='9';c++){
            if(board[p][q]=='.'&&isSudoku(board,p,q,c)){
                // cout<<p<<q<<c<<endl;
                t = nSudoku(p,q);
                s1.push(p);
                s2.push(q);
                mt[0][p][c-'1'] = mt[1][q][c-'1'] = mt[2][t][c-'1'] = true;
                board[p][q] = c;
                n++;
                // cout<<p<<q<<endl;
                if(addNode(board,p,q))return true;
                c2 = board[p][q];
                t = nSudoku(p,q);
                // cout<<p<<" "<<q<<c2-'1'<<endl;
                p = s1.top();
                q = s2.top();
                s1.pop();
                s2.pop();
                board[p][q] = '.';
                mt[0][p][c2-'1'] = mt[1][q][c2-'1'] = mt[2][t][c2-'1'] = false;
                n--;
            }
        }
        return false;
    }
};