What is the algorithm of this problem?


  • 0
    N

    what is the algorithm of this problem?


  • 1
    S

    No exact algorithm, just the same way you solve this problem yourself in real life.


  • 1
    R

    Standard Backtracking can be used.

    class Solution {
    public:
    
       bool safeinrow_col(int r,int c,char digit,vector<vector<char>> &board){
           for(int j=0;j<9;j++){
               if(board[r][j]==digit || board[j][c]==digit)return false;
           }
           return true;
       }
       bool safeinbox(int r,int c,char digit,vector<vector<char>> &board){
           for(int i=0;i<3;i++){
               for(int j=0;j<3;j++){
                   if(board[(r-r%3)+i][(c-c%3)+j]== digit)return false;
               }
           }
           return true;
       }
    
    
    
        bool findunassigned(vector<vector<char> > &board,int &i,int &j) {
            for(i=0;i<9;i++){
                for(j=0;j<9;j++){
                    if(board[i][j]=='.'){
                        return true;
                    }
                }
            }
            return false;
        }
        
        bool solve_recur(vector<vector<char> > &board){
        int row,col;
        if(!findunassigned(board,row,col))return true;   //find next unassigned cell
        for(char c='1';c<='9';c++){
            
            if(safeinrow_col(row,col,c,board) && safeinbox(row,col,c,board)){     // safe to put c in this cell
                board[row][col]=c;                                    
                 if(solve_recur(board))return true;                  //current choice leads to the solution return true
            
                board[row][col]='.';                     // current choice is wrong hence undo the previous operation
        
            }
           
        }
        return false;
        }
        
        
         void solveSudoku(vector<vector<char> > &board) {
            if(solve_recur(board))return; 
         }
    };

Log in to reply
 

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