题解 | #数独#

回溯

class Solution {
public:
    int Count;
    bool row[10][10];
    bool column[10][10];
    bool subsquare[10][10];
    struct Node{
        int x;
        int y;
        Node(int xx, int yy) :x(xx), y(yy) {}
        Node() {}
    }Points[100];
    int Judge(int i, int j){ //规定每个小九宫格的号码
        return ((i - 1) / 3 )* 3 + (j - 1) / 3 + 1;
    /*
     1 2 3
     4 5 6
     7 8 9

     1+3*0 2+3*0 3+3*0
     1+3*1 2+3*1 3+3*1
     1+3*2 2+3*2 3+3*2
    */
    }
    bool helper(int n, vector<vector<char>> & board){
        if (n > Count) return true;
        //每个空点都有1-9九种可能
        for(int i = 1; i <= 9; i++){
            if(!row[Points[n].x][i] && !column[i][Points[n].y] && !subsquare[Judge(Points[n].x, Points[n].y)][i]){
                row[Points[n].x][i] = true;
                column[i][Points[n].y] = true;
                subsquare[Judge(Points[n].x, Points[n].y)][i] = true;
                board[Points[n].x - 1][Points[n].y - 1] = i + '0';
                if(helper(n + 1, board)) return true;
                row[Points[n].x][i] = false;
                column[i][Points[n].y] = false;
                subsquare[Judge(Points[n].x, Points[n].y)][i] = false;
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char> > &board) {
        memset(row, false, sizeof(row));
        memset(column, false, sizeof(column));
        memset(subsquare, false, sizeof(subsquare));
        for(int i = 1; i <= 9; i ++){
            for(int j = 1; j <= 9; j ++){
                if(board[i - 1][j - 1] == '.'){
                    Count ++;
                    Points[Count].x = i;
                    Points[Count].y = j;
                }else{
                    int val = board[i - 1][j - 1] - '0';
                    row[i][val] = true;
                    column[val][j] = true;
                    subsquare[Judge(i, j)][val] = true;
                }
            }
        }
        helper(1, board);
    }
};