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);
    }

    bool dfs(vector<vector<char>>& board, int x, int y) {
        if (y == 9) x ++, y = 0;
        if (x == 9) return true;
        if (board[x][y] != '.') return dfs(board, x, y + 1);
        for (int i = 0; i < 9; i ++) { // 虽然枚举数字 1~9,但不可直接写i=1;i<=9;因为row[x][9]等数组会越界，当某个数字i（实际用i-1代替）出现在x行y列[x,y]九宫格，则说明该棋盘上的位置值是'1'+i
            if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {
                board[x][y] = '1' + i;
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
                if(dfs(board, x, y + 1)) return true;
                board[x][y] = '.'; //恢复现场
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false; //恢复现场
            }
        }
        return false;
    }
};