My easy to understand Java Code which is faster than 85% of code using recursive backtracking


  • 0
    C

    My code is just using recursive backtracking, no need to iterate from the starting point of the board each time. Each time the starting position is the position from last filled position using the row and column index.
    '''
    public void solveSudoku(char[][] board) {
    // explore(board);
    explore(board, 0, 0);
    }

    private boolean explore(char[][] board, int row, int col) {
        if (row == 9) {
            return true;
        } else {
            if (board[row][col] == '.') {
                for (char i = '1'; i <= '9'; i++) {
                    if (isValidSudoku(board, row, col, i)) {
                        board[row][col] = i;
                        if (col == 8) {
                            if (explore(board, row + 1, 0)) return true;
                        } else {
                            if (explore(board, row, col + 1)) return true;
                        }
                    }
                }
                board[row][col] = '.';
                return false;
            } else {
                if (col == 8) {
                    if (explore(board, row + 1, 0)) return true;
                } else {
                    if (explore(board, row, col + 1)) return true;
                }
                return false;
            }
        }
    }
    
    private boolean isValidSudoku(char[][] board, int row, int col, char c) {
            for (int j = 0; j < 9;j++){
                if(board[row][j] == c)
                    return false;
                if(board[j][col] == c)
                    return false;
                int RowIndex = 3 * (row / 3);
                int ColIndex = 3 * (col / 3);
                if(board[RowIndex + j / 3][ColIndex + j % 3] == c)
                    return false;
        }
        return true;
    }
    

    '''


Log in to reply
 

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