class Solution {
public:

    bool row[9][9], col[9][9], cell[3][3][9];

    void solveSudoku(vector<vector<char>>& board) {
        memset(row, 0, sizeof row);//初始化
        memset(col, 0, sizeof col);
        memset(cell, 0, sizeof cell);
        //把已经填过的数更新到棋盘中
        for (int i = 0; i < 9; i ++ )
            for (int j = 0; j < 9; j ++ )
                if (board[i][j] != '.') {
                    int t = board[i][j] - '1';
                    row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
                }

        dfs(board, 0, 0);//从左上角开始dfs
    }

    bool dfs(vector<vector<char>>& board, int x, int y) {
        if (y == 9) x ++, y = 0;//纵坐标到头了(越界了)，让行号+1，列为0
        if (x == 9) return true;

        if (board[x][y] != '.') return dfs(board, x, y + 1);//当前点不是'.',说明有数了，直接枚举下一个数
        //否则就说明当前位置没有数，那么就枚举一下当前位置可以填哪些数
        for (int i = 0; i < 9; i ++ ){
            //第x行没有出现过，第j列没有出现过，所在的小九宫格页眉出现过
            if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {
                board[x][y] = '1' + i;//将xy这个位置填上数‘1’ + i
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;//填完之后记录已经填过了
                if (dfs(board, x, y + 1)) return true;//dfs下一个格子，返回true说明找到了答案，直接返回
                board[x][y] = '.';//恢复现场
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
            }
        }
        return false;//最后都没找到，说明当前分支无解，返回false
    }
};