A Fast solution in JAVA and how the hashtable can be used to solve


  • 1
    N
    public class Solution {
    boolean[][] row = new boolean[9][9];
    boolean[][] col = new boolean[9][9];
    boolean[][] blo = new boolean[9][9];
    
    public void solveSudoku(char[][] board) {
        for(int i=0;i<9;i++)
            for(int j =0;j<9;j++){
                int temp =board[i][j]-'1';
                if(board[i][j]!='.'){
                    row[i][temp]=true;
                    col[j][temp]=true;
                    blo[3*(i/3)+j/3][temp]=true;
                }
            }
        solveHelper(0,0,board);
    }
    public boolean solveHelper(int i, int j, char[][] board){
        if(i==9)
            return true;
        if(board[i][j]!='.'){
            if(j<8)
                return solveHelper(i,j+1,board);
            else 
                return solveHelper(i+1,0,board);
        }else for(int k =0;k<9;k++){
                if(row[i][k]==false&&col[j][k]==false&&blo[3*(i/3)+j/3][k]==false){
                    board[i][j] = (char)(k+'0'+1);
                    row[i][k]=true;
                    col[j][k]=true;
                    blo[3*(i/3)+j/3][k]=true;
                    if(j<8&&solveHelper(i,j+1,board))
                        return true;
                    else if(j==8&&solveHelper(i+1,0,board))
                        return true;
                    else{
                        board[i][j] = '.';
                        row[i][k]=false;
                        col[j][k]=false;
                        blo[3*(i/3)+j/3][k]=false;
                    }
                }
            }
        return false;
    }
    

    }

    Use three boolean arrays to store the status of three patterns(vertical horizontal block), then use backtracking and DFS to solve the board Sequentially.

    Question: How the hashtable can be used to solve this question?


  • 0
    M

    Very cool solution!

    I think the hashtable would be used to store potential moves for rows/cols/blocks, similar to your solution, except you've figured out a better way imo.

    I did it using hashtable and the code wasn't pretty, plus it uses more memory.

    Then I took inspiration from your method and redid it and it came out much clearer.

    public class Solution {
        private int n = 9, m = 3;
        private char empty = '.';
        private char[][] board;
        private boolean[][] rows, cols, boxs;
        
        public void solveSudoku(char[][] board) {
            this.board = board;
            this.rows = new boolean[n][n];
            this.cols = new boolean[n][n];
            this.boxs = new boolean[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == empty) continue;
                    int cell = (int)(board[i][j] - '1');
                    rows[i][cell] = true;
                    cols[j][cell] = true;
                    boxs[m * (i/m) + j/m][cell] = true;
                }
            }
            solveSudoku(0, 0);
        }
        
        public boolean solveSudoku(int i, int j) {
            if (i == n) return true;
            
            if (board[i][j] != empty) return solveSudoku(i + (j+1)/n, (j+1) % n);
            
            for (int k = 0; k < n; k++) {
                if (!(rows[i][k] || cols[j][k] || boxs[m * (i/m) + j/m][k])) {
                    board[i][j] = (char)(k + '1');
                    rows[i][k] = true;
                    cols[j][k] = true;
                    boxs[m * (i/m) + j/m][k] = true;
                    if (solveSudoku(i + (j+1)/n, (j+1) % n)) {
                        return true;
                    }
                    else {
                        board[i][j] = empty;
                        rows[i][k] = false;
                        cols[j][k] = false;
                        boxs[m * (i/m) + j/m][k] = false;
                    }
                }
            }
            return false;
        }
    }

Log in to reply
 

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