Share a 4ms solution c++ with comments


  • 0
    H
    /*
    The idea is to use the lower 9 bits of an int to store the occurrence of 1~9 in a row/col/sub_board
    
    e.g. row[0] is "..9748..." then the 9 low bits of the int representing row[0] are "111001000"(left to right = high to low bit)
         
         col[0] is ".7.......", the 9 low bits are "001000000"
         
         sub_board[0][0] is "..9"
                            "7.."
                            ".2.", the 9 low bits are "101000010"
                            
        Thus for the empty cell at board[0][0], the candidates are row[0] | col[0] | sub[0][0] = "111001010"
        All the 0 bits are possible candidates for this empty cell. (1, 3, 5, and 6, aka. the 1st, 3rd, 5th, and 6th bits are 0)
        
    So for each empty cell at board[x][y], we could use (row[x] | col[y] | sub[x/3][y/3]) to generate the candidates for it.
    We go through all the candidates (aka the 0 bits index) in the same backtracking method as the simple backtracking solution.
    
    */
    
    class Solution {
    public:
        void solveSudoku(vector<vector<char>>& board) {
            initialize(board);
            solve(board,0,0);
        }
    private:
        vector<int> row;  //store row info
        vector<int> col;  //store col info
        vector<vector<int>> sub;  //store sub_board info
        
        /*given the board, initialize the row, col, and sub_board info*/
    
        void initialize(vector<vector<char>>& board){
            row = vector<int>(9,0);
            col = vector<int>(9,0);
            sub = vector<vector<int>>(3, vector<int>(3,0));
            for(int i = 0; i < 9; i++){
                for(int j = 0; j < 9; j++){
                    if(board[i][j] == '.') continue;
                    int num = board[i][j] - '0';
                    int mask = 1 << (num-1);
                    row[i] |= mask;
                    col[j] |= mask;
                    sub[i/3][j/3] |= mask;
                }
            }
        }
        
        /*use backtracking to solve the sudoku starting at cell board[r][c]*/
    
        bool solve(vector<vector<char>>& board, int r, int c) {
            for(; r < 9; r++){
                for(; c < 9; c++){
                    //find the next empty cell
                    if(board[r][c] == '.'){
                        //generate the candidates for this cell
                        int cands = (row[r] | col[c] | sub[r/3][c/3]);
                        //all 1~9 are occupied, impossible to fill the cell, backtrack to the previous empty cell
                        if(cands == 511) return false;
                        for(int i = 0; i < 9; i++){
                            int mask = 1 << i;
                            //try candidates
                            if((cands & mask) == 0) {
                                //update all info
                                cands |= mask;
                                row[r] |= mask;
                                col[c] |= mask;
                                sub[r/3][c/3] |= mask;
                                //fill the cell
                                board[r][c] = (char)('1' + i);
                                //go to next empty space
                                if(solve(board, r, c)) return true;
                                //backtrack, need to rollback info to the state before update
                                int recover = ~mask;
                                cands &= recover;
                                row[r] &= recover;
                                col[c] &= recover;
                                sub[r/3][c/3] &= recover;
                                board[r][c]='.';
                            }
                        }
                        //tried all possible candidates, but still reached here, backtrack to the previous empty cell
                        return false;
                    }
                }
                c = 0;
            }
            //filled all empty cells, done!
            return true;
        }
    };

Log in to reply
 

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