Two very Simple and Neat Java DFS/Backtracking solutions


  • 11
    M

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

    private char[][] b;
    private boolean[][] row = new boolean[9][9];
    private boolean[][] col = new boolean[9][9];
    private boolean[][] block = new boolean[9][9];
    public void solveSudoku(char[][] board) {
        b = 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] = true;
                }
            }
        }
        Helper(0);
    }
    public boolean Helper(int ind){
        if(ind==81) return true; 
        int i=ind/9, j=ind%9, num, k;
        if(b[i][j]!='.') return Helper(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] = true;
                    if(Helper(ind+1)) return true;                
                    b[i][j]='.';
                    row[i][num] = col[j][num] = block[k][num] = false;
                }
            }
            return false;
        }
    }
    

    2.The second one check with board itself. The code is neat and simple. Running time is about 252-332ms. The time difference between these two version is small. But it's huge in C++ answer.

    private char[][] b;
    public void solveSudoku(char[][] board) {
        if(board == null || board.length < 9) return;
        b = board;
        solve(0);
    }
    public boolean solve(int ind){
        if(ind==81) return true; 
        int i=ind/9, j=ind%9;
        if(b[i][j]!='.') return solve(ind+1);
        else{
            for(char f = '1'; f <= '9'; f++){
                if(isValidFill(i, j, f)){
                    b[i][j]= f;
                    if(solve(ind+1)) return true;                
                    b[i][j]='.';
                }
            }
            return false;
        }
    }
    public boolean isValidFill(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;
    }
    

  • 1
    W

    I like this answer which utilize boolean[][] matrix to check the number, which is better than just loop through the row, column and box each time to check duplicates, why this answer just have 2 votes? It deserves more votes!


Log in to reply
 

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