Standard solution using backtrack


  • 0
    T

    class Solution {
    public:
    void solveSudoku(vector<vector<char>>& board) {
    solveSudokuHelp(0,0,board); //using backtrack technique

    }
    

    private:
    const vector<char> digits={'1','2','3','4','5','6','7','8','9'};

    const int DIM=9;
    
    bool solveSudokuHelp(int i,int j, vector<vector<char>>& A){
        if(i==DIM){
            i=0;
            if(++j==DIM) return true;
        }
        
        if(A[i][j]!='.'){ //if board[i][j] filled, fill next square
            return solveSudokuHelp(i+1,j,A);
        }     
        
        for(char v: digits){ //check all possible numbers
            if(validSudoku(i,j,A,v)){ 
                A[i][j]=v;
                if(solveSudokuHelp(i+1,j,A)) 
                       return true;
            }
        }
        
      A[i][j]='.'; //if no valid number in (i,j), backtrack previous squares
      return false;
        }
    
     bool validSudoku(int i,int j, const vector<vector<char>>& A, int v){//check whether v can be filled
         for(int k=0;k<DIM;++k){ //check row rule
             if(v==A[k][j]) return false;
         }
         
         for(int k=0;k<DIM;++k){//check column rule
             if(v==A[i][k]) return false;
         }
         
         int blk=DIM/3;
         int I=i/3, J=j/3;
         for(int a=0;a<blk;++a){ //check block rule
             for(int b=0;b<blk;++b){
                 if(v==A[I*3+a][J*3+b]) return false;
             }
         }
         return true;
     }
    

    };


Log in to reply
 

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