Simple also fast Java backtracking not using hash table with inline comments


  • 0
    H
    public void solveSudoku(char[][] board) {
            // Three boolean arrays.
            // rowSet[i][j] - j+1 is used in the i-th row
            boolean[][] rowSet = new boolean[9][9];
    
            boolean[][] colSet = new boolean[9][9];
          
            boolean[][] blkSet = new boolean[9][9];
            
            // set initialization
            for (int r = 0; r < 9; r++) {
                for (int c = 0; c < 9; c++) {
                    char ch = board[r][c];
                    if (ch == '.') continue;
                    rowSet[r][ch-'1'] = true;
                    colSet[c][ch-'1'] = true;
                    blkSet[r/3*3+c/3][ch-'1'] = true;
                }
            }
            backtracking(board, 0, 0, rowSet, colSet, blkSet);
            return;
        }
        private boolean backtracking(char[][] board, int startR, int startC, boolean[][] rowSet, 
                boolean[][] colSet, boolean[][] blkSet) {
            int i, r = 0, c = 0;
            // look for the next empty cell
            for (i = startR*9 + startC; i < 81; i++) {
                r = i / 9;
                c = i % 9;
                if (board[r][c] == '.')
                    break;
                }
            // no more empty
            if (i == 81) return true;
            
            for (char ch = '1'; ch <= '9'; ch++) {
                if (rowSet[r][ch-'1'] || colSet[c][ch-'1'] || 
                        blkSet[r/3*3+c/3][ch-'1'])
                    continue;
                    
                board[r][c] = ch;
                rowSet[r][ch-'1'] = true;
                colSet[c][ch-'1'] = true;;
                blkSet[r/3*3+c/3][ch-'1'] = true;
                
                if (backtracking(board, r, c, rowSet, colSet, blkSet))
                    return true;
                else {
                    board[r][c] = '.';
                    rowSet[r][ch-'1'] = false;
                    colSet[c][ch-'1'] = false;
                    blkSet[r/3*3+c/3][ch-'1'] = false;
                }
            }
            return false;
        }
    

Log in to reply
 

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