Java Commented Backtracking Beats 86%.


  • 0
    X
    public class Solution {
        boolean rows[][], cols[][], blks[][]; // boolean tables to mark used numbers
        final static int N = 9;
        public void solveSudoku(char[][] board) {
            rows = new boolean[N][N];
            cols = new boolean[N][N];
            blks = new boolean[N][N];
            initialize(board);
            backTrack(board, 0, 0);
        }
        private boolean backTrack(char[][] board, int r, int c) {
            for(int i = 0; i < N; i++)
                for(int j = 0; j < N; j++){
                    if(i < r && j < c) { // Skip to previous context.
                        i = r;
                        j = c;
                    }
                    if(board[i][j] == '.'){ // For cells not filled yet, use backtrack
                        if(!trackOneCell(board, i, j, 0)) return false;
                    }
                }
            return true; // Returning true means all cells are filled.
        }
        private boolean trackOneCell(char[][] board, int r, int c, int pos) {
            for(int i = pos; i < N; i++) {
                // Validate sudoku before filling, instead of after.
                if(rows[r][i] || cols[c][i] || blks[getBlk(r, c)][i]) continue;
                setCell(board, r, c, (char)(i + '1'));
                if(backTrack(board, r, c)) return true;
                setCell(board, r, c, '.');
            }
            return false; // Nothing to fill
        }
        private void setCell(char[][] board, int r, int c, char ch) {
            boolean isNum = (ch != '.');
            int num = isNum ? ch - '1' : board[r][c] - '1';
            board[r][c] = ch; // fill or unfill the cell
            rows[r][num] = isNum; // Update tables of used numbers
            cols[c][num] = isNum;
            blks[getBlk(r, c)][num] = isNum;
        }
        private void initialize(char[][] board) {
            for(int i = 0; i < N; i++)
                for(int j = 0; j < N; j++){
                    if(board[i][j] == '.') continue;
                    int num = board[i][j] - '1';
                    rows[i][num] = true;
                    cols[j][num] = true;
                    blks[getBlk(i, j)][num] = true;
                }
        }
        private int getBlk(int r, int c) { // get id (0 - 8) of blocks
            return (r / 3 * 3 + c / 3);
        }
    }
    

Log in to reply
 

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