37. 解数独

class Solution {
public:
    vector<vector<char>> b;
    bool check(int i,int j,int val) {
        for(int k=0;k<9;k++)if(b[i][k]==val||b[k][j]==val)return false;
        int ibase = i/3*3, jbase = j/3*3;
        for(int u=0;u<3;u++)for(int v=0;v<3;v++)if(b[ibase+u][jbase+v]==val)return false;
        return true;
    }
    bool bt(int pos) {
        int i = pos/9, j = pos%9;
        if(i==9)return true;
        if(b[i][j]!='.')return bt(pos+1);
        for(int v=1; v<=9; v++) {
            if(check(i,j,'0'+v)) {
                b[i][j]='0'+v;
                if(bt(pos+1))return true;
                b[i][j]='.';
            }
        }
        return false; // unreachable
    }
    void solveSudoku(vector<vector<char>>& board) {
        b=board;
        bt(0);
        // for(int i=0;i<9;i++){
        //     for(int j=0;j<9;j++){
        //         cout<<b[i][j];
        //     }
        //     cout<<endl;
        // }
        board=b;
    }
};