C++ Solution Using Backtracking, 19ms


  • 0
    void solveSudoku(vector<vector<char>>& board) {
            solve(board, 0, 0);
        }
        
        bool solve(vector<vector<char>>& board, int i_begin,int j_begin){
            
            for(int i=i_begin;i<9; i++){
                for(int j=0;j<9; j++){
                    
                    if( i == i_begin && j<j_begin){
                        continue;
                    }
                    
                    if(board[i][j] == '.'){
                        
                        size_t cantfill = 0;
                        for(int k=0;k<9;k++){
                            if(board[k][j]!='.'){
                                cantfill |= (1u<<(board[k][j] - '1'));
                            }
                            if(board[i][k]!='.'){
                                cantfill |= (1u<<(board[i][k] - '1'));
                            }
                        }
                        for(int k=0;k<3;k++){
                            for(int m=0;m<3;m++){
                                char c = board[i/3*3 + k][j/3*3 + m];
                                if(c!='.'){
                                    cantfill |= (1u<<(c-'1'));
                                }
                            }
                        }
                        
                        if(cantfill == 0x1ff){
                            return false;
                        }
                        
                        for(int k=0;k<9;k++){
                            if( !(cantfill&(1u<<k))){
                                board[i][j] = '1'+k;
                                if(solve(board, i, j+1)){
                                    return true; 
                                }else{
                                    board[i][j] = '.';
                                }
                            }
                        }
                        
                        return false; // should not reach
                    }
                    
                    
                }
            }
            
            return true;
        }
    

Log in to reply
 

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