My C++ solution (3ms)


  • 0
    A

    It is just simply depth first search. The cell which has least choices always goes first.

    class Solution {
    public:
        void solveSudoku(vector<vector<char>>& board) {
            int i, j;
            blank = 0;
            for(i = 0; i < 9; i++) {
                for(j = 0; j < 9; j++) {
                    if(board[i][j]=='.') {
                        dboard[i][j] = 0;
                        blank++;
                    }
                    else
                        dboard[i][j] = board[i][j] - '0';
                }
            }
            setCandidate();
            dfs();
            for(i = 0; i < 9; i++) {
                for(j = 0; j < 9; j++) {
                    if(board[i][j] == '.')
                        board[i][j] = '0'+dboard[i][j];
                }
            }
        }
        
        bool dfs() {
            if(blank == 0) return true;
            int x, y, i, j, k;
            getCandidate(x, y);
            for(k = 1; k < 10; k++) {
                if(candidate[x][y][k] == 0) continue;
                dboard[x][y] = k;
                --blank;
                int candidate_copy[9][9][10];
                copyArr(candidate_copy, candidate);
                updateCandidate(x, y, k);
                if(dfs()) return true;
                copyArr(candidate, candidate_copy);
                ++blank;
                dboard[x][y] = 0;
            }
            return false;
        }
        
        void setCandidate() {
            int i, j, k, r, c;
            for(i = 0; i < 9; i++) {
                for(j = 0; j < 9; j++) {
                    for(k = 1; k < 10; k++) {
                        candidate[i][j][k] = 1;
                    }
                }
            }
            for(i = 0; i < 9; i++) {
                for(j = 0; j < 9; j++) {
                    int digit = dboard[i][j];
                    if(digit != 0) {
                        updateCandidate(i, j, digit);
                    }
                }
            }
            for(i = 0; i < 9; i++) {
                for(j = 0; j < 9; j++) {
                    int cnt = 0;
                    for(k = 1; k < 10; k++) {
                        if(candidate[i][j][k] != 0)
                            ++cnt;
                    }
                    candidate[i][j][0] = cnt;
                }
            }
        }
        
        void getCandidate(int &x, int &y) {
            int i, j, min = 10;
            for(i = 0; i < 9; i++) {
                for(j = 0; j < 9; j++) {
                    if(dboard[i][j] == 0 && candidate[i][j][0] < min) {
                        min = candidate[i][j][0];
                        x = i;
                        y = j;
                    }
                }
            }
        }
        
        void updateCandidate(int x, int y, int d) {
            int i, j;
            for(i = 0; i < 9; i++) {
                if(dboard[i][y] == 0 && candidate[i][y][d] == 1) {
                    candidate[i][y][d] = 0;
                    candidate[i][y][0]--;
                }
            }
            for(j = 0; j < 9; j++) {
                if(dboard[x][j] == 0 && candidate[x][j][d] == 1) {
                    candidate[x][j][d] = 0;
                    candidate[x][j][0]--;
                }
            }
            int a = 3*(x/3), b = 3*(y/3);
            for(i = a; i < a+3; i++) {
                for(j = b; j < b+3; j++) {
                    if(dboard[i][j] == 0 && candidate[i][j][d] == 1) {
                        candidate[i][j][d] = 0;
                        candidate[i][j][0]--;
                    }
                }
            }
        }
        
        void copyArr(int dst[][9][10], int src[][9][10]) {
            int i, j, k;
            for(i = 0; i < 9; i++) {
                for(j = 0; j < 9; j++) {
                    for(k = 0; k < 10; k++) {
                        dst[i][j][k] = src[i][j][k];
                    }
                }
            }
        }
        
        int dboard[9][9];
        /* candidate[x][y][0] is the count of valid choices. 
           candidate[x][y][digit] = 0 or 1, marks if a digit is valid at position (x,y) */
        int candidate[9][9][10];
        int blank; // the count of blank cell to be fill
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.