C++ simple backtracking solution


  • 0
    J
    class Solution {
    public:
        void solveSudoku(vector<vector<char>>& board) {
            
            vector<vector<int>> row(9, vector<int>(9,0));
            vector<vector<int>> col(9, vector<int>(9,0));
    
            vector<vector<int>> cub(9, vector<int>(9,0));
            for(int i=0; i<9; i++)
            {
                for(int j=0; j<9; j++)
                {
                    char c=board[i][j];
                    if(c!='.')
                    {
                        row[i][c-'1']=1;
                        col[j][c-'1']=1;
                        cub[i/3*3+j/3][c-'1']=1;
                    }
                }
            }
         
          
            help(board, row, col, cub);
            return;
        }
        
        bool help(vector<vector<char>>& board, vector<vector<int>>& row, vector<vector<int>>& col, vector<vector<int>>& cub)
        {
            for(int i=0; i<9; i++)
            {
                for(int j=0; j<9; j++)
                {
                    if(board[i][j]=='.' )
                    {
                       
                        for(int k=0; k<9; k++)
                        {
                           
                            if(row[i][k] == 0 && col[j][k] == 0 && cub[i/3*3+j/3][k]==0 )
                            {
                                
                                board[i][j]=k+'1';
                                row[i][k]=1;
                                col[j][k]=1;
                                cub[i/3*3+j/3][k]=1;
                                
                                if(help(board, row, col, cub))
                                    return true;
                                board[i][j]='.';
                                row[i][k]=0;
                                col[j][k]=0;
                                cub[i/3*3+j/3][k]=0;   
                                    
                                
                            }
                        }
                        return false;
                            
                    }
                }
            }
            return true;
        }
    };
    

Log in to reply
 

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