Two very Simple and Neat C++ DFS/Backtracking solutions


  • 4
    M

    1.The first one uses three 2D-array to check valid. Running time is about 4-8ms.

    bool row[9][9]={}, col[9][9]={}, block[9][9]={};
    void solveSudoku(vector<vector<char>>& board) {
        int num, k;
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                if(board[i][j]!='.') {
                    num = board[i][j]-'1'; 
                    k = i/3*3 + j/3;
                    row[i][num] = col[j][num] = block[k][num] = 1;
                }
            }
        }
        Helper(board, 0);
    }
    bool Helper(vector<vector<char>>& b, int ind){
        if(ind==81) return true; 
        int i=ind/9, j=ind%9, num, k;
        if(b[i][j]!='.') return Helper(b, ind+1);
        else{
            for(char f='1'; f<='9'; f++){
                num = f-'1'; 
                k= i/3*3 + j/3;
                if(!row[i][num] && !col[j][num] && !block[k][num]){
                    b[i][j]= f;
                    row[i][num] = col[j][num] = block[k][num] = 1;
                    if(Helper(b, ind+1)) return true;                
                    b[i][j]='.';
                    row[i][num] = col[j][num] = block[k][num] = 0;
                }
            }
            return false;
        }
    }
    

    2.The second one check with board itself. The code is neat and simple, but it runs so slow. Running time is about 52ms. Copy my own code from here. And there is the Java version.

    void solveSudoku(vector<vector<char>>& board) {
        helper(board, 0);
    }
    bool helper(vector<vector<char>>& b, int ind){
        if(ind==81) return true; 
        int i=ind/9, j=ind%9;
        if(b[i][j]!='.') return helper(b, ind+1);
        else{
            for(char f = '1'; f <= '9'; f++){
                if(isValidFill(b, i, j, f)){
                    b[i][j]= f;
                    if(helper(b, ind+1)) return true;                
                    b[i][j]='.';
                }
            }
            return false;
        }
    }
    bool isValidFill(vector<vector<char>>& b, int i, int j, char fill) {
        for(int k=0; k<9; k++){
            int r= i/3*3+j/3;   //select the block
            if(b[i][k]==fill || b[k][j]==fill || b[r/3*3+k/3][r%3*3+k%3]==fill) 
                return false; //check row, column, block
        }            
        return true;
    }
    

Log in to reply
 

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