37. Sudoku Solver 数独解题器

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        memset(row, 0, sizeof row);
        memset(col, 0, sizeof col);
        memset(box, 0, sizeof box);
        // 预处理得到限制表格，搜索的时候用这个来剪枝
        for(int i=0;i<9;++i) {
            for(int j=0;j<9;++j) {
                if (board[i][j]=='.') continue;
                int n=board[i][j]-'0';
                row[i][n]=1;
                col[j][n]=1;
                box[(i/3)*3+j/3][n]=1;
            }
        }
        
        DFS(board, 0, 0);
    }
    
    bool DFS(vector<vector<char>>& bd, int x, int y) {
		// x 为 9 说明解已经找到
        if (x==9) return true;
        // 下一格子
        int ny=(y+1)%9;
        int nx=(ny==0) ? x+1:x;
        
        if (bd[x][y]!='.') return DFS(bd, nx, ny);
        for(int n=1;n<=9;++n) {
            if (!row[x][n] && !col[y][n] && !box[(x/3)*3+y/3][n]) {
                row[x][n]=1;
                col[y][n]=1;
                box[(x/3)*3+y/3][n]=1;
                bd[x][y]=n+'0';
				// 已经找到就不用再找了
                if (DFS(bd, nx, ny)) return true;
                bd[x][y]='.';
                row[x][n]=0;
                col[y][n]=0;
                box[(x/3)*3+y/3][n]=0;
            }
        }
        return false;
    }
    
private:
    int row[9][10];
    int col[9][10];
    int box[9][10];
};