7ms backtracking method, in JAVA with explaination


  • 0
    public class Solution {
        /*
        Idea: backtracking with multiple (sacrifice space to reduce time)
        
        method: scan the input board and maintains 3 9by9 boolean tables to save numbers used, namely row, col and grid
        e.g. row[i][num] = true means num has already showed up on ith row
        
        Backtracking process : scan from first row to last row, for each row scan from left to right.
        find the first '.' position, fill it will a valid number (1 to 9) which has not showed up in the same row, col and grid.
        Meanwhile updating the three boolean tables to set the newly filled number as true; find the next '.' position and do the
        same thing. If the table is fill successfully, return true, otherwise return false and change the target position's grid
        value to '.' and corresponding boolean values back to false. Fill in the next posible value and do it again. 
        
        Time complexity: I do not know
        real performance: 7ms
        */
        public void solveSudoku(char[][] board) {
            boolean[][] row = new boolean[9][9];
            boolean[][] col = new boolean[9][9];
            boolean[][] grid = new boolean[9][9];
            for (int i = 0; i < 9; i ++) {
                for (int j = 0; j < 9; j ++) {
                    if (board[i][j] != '.') {
                        int num = board[i][j] - '1';
                        row[i][num] = true;
                        col[j][num] = true;
                        grid[(i/3)*3 + j/3][num] = true;
                    }
                }
            }
            backtracking(board, 0, 0, row, col, grid);
        }
        
        public boolean backtracking(char[][] board, int x, int y, boolean[][] row, boolean[][] col, boolean[][] grid) {
            for (int i = x; i < 9; i ++) {
                for (int j = (i == x ? y : 0); j < 9; j ++) {
                    if (board[i][j] == '.') {
                        for (int k = 0; k < 9; k ++) {
                            if (!row[i][k] && !col[j][k] && !grid[(i/3)*3 + j/3][k]) {
                                row[i][k] = true;
                                col[j][k] = true;
                                grid[(i/3)*3 + j/3][k] = true;
                                board[i][j] = (char)(k + '1');
                                if (backtracking(board, i, j, row, col, grid)) {
                                    return true;
                                }
                                row[i][k] = false;
                                col[j][k] = false;
                                grid[(i/3)*3 + j/3][k] = false;
                            }
                        }
                        board[i][j] = '.';
                        return false;
                    }
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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