Sudoku Solver in Java: Efficient Backtracking and Pruning

Introduction to the Sudoku Solver Problem

The Sudoku puzzle is a classic number-placement puzzle. The objective is to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 subgrids (also called "boxes" or "blocks") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

Solving Sudoku is a perfect application for backtracking. It involves making a series of choices (placing a number in an empty cell) and, if a choice leads to an invalid state, undoing that choice and trying another (backtracking).

When Should You Think About Sudoku Solver?

While solving Sudoku is a specific problem, the techniques used are broadly applicable when:

• You need to fill a grid or structure with elements subject to local and global constraints.
• The problem involves constraint satisfaction where decisions at one point affect possibilities elsewhere.
• You are looking for a single valid solution (or all solutions) in a combinatorial search space.
• Problems that can be modeled as filling empty slots with valid choices.

Core Concepts of Solving Sudoku with Backtracking

The backtracking approach for Sudoku involves iterating through the cells of the grid. When an empty cell is found, we try placing digits from 1 to 9. For each digit, we check if its placement is valid according to Sudoku rules. If valid, we recursively try to solve the rest of the puzzle. If the recursive call returns true (meaning a solution was found), we propagate true upwards. If it returns false (meaning no solution was found with that digit), we undo the placement (backtrack) and try the next digit.

Algorithm:

1. Find an Empty Cell: Iterate through the 9x9 grid to find the next empty cell (represented by '.'). If no empty cells are found, the puzzle is solved.
2. Try Digits: For the empty cell, try placing digits from 1 to 9.
3. Check Validity: Before placing a digit, check if it's valid according to Sudoku rules:
   • Is the digit already present in the current row?
   • Is the digit already present in the current column?
   • Is the digit already present in the current 3x3 subgrid?
4. Make a Choice: If a digit is valid, place it in the empty cell.
5. Recurse: Recursively call the solver for the next empty cell.
6. Backtrack: If the recursive call returns false (meaning the current choice didn't lead to a solution), undo the placement (set the cell back to '.') and try the next digit.

Example: Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells. The given board contains only digits 1-9 and the character '.'. You may assume that the given Sudoku puzzle will have a single unique solution.

import java.util.Arrays;

class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        backtrackSudoku(board);
    }

    private boolean backtrackSudoku(char[][] board) {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == ".") {
                    for (char num = '1'; num <= '9'; num++) {
                        if (isValidPlacement(board, r, c, num)) {
                            board[r][c] = num; // Make a choice

                            if (backtrackSudoku(board)) { // Recurse
                                return true; // Solution found
                            }

                            board[r][c] = "."; // Undo choice (Backtrack)
                        }
                    }
                    return false; // No valid number for this cell
                }
            }
        }
        return true; // All cells filled, solution found
    }

    private boolean isValidPlacement(char[][] board, int row, int col, char num) {
        // Check row
        for (int c = 0; c < 9; c++) {
            if (board[row][c] == num) {
                return false;
            }
        }

        // Check column
        for (int r = 0; r < 9; r++) {
            if (board[r][col] == num) {
                return false;
            }
        }

        // Check 3x3 subgrid
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int r = startRow; r < startRow + 3; r++) {
            for (int c = startCol; c < startCol + 3; c++) {
                if (board[r][c] == num) {
                    return false;
                }
            }
        }
        return true;
    }
}

Complexity:

• Time Complexity: The worst-case time complexity for Sudoku is extremely high, often cited as O(9^(N*N)) where N is the side length (9 for standard Sudoku). However, due to pruning, the actual performance is much better. For a 9x9 grid, it's closer to O(9^M) where M is the number of empty cells. The number of operations can be very large, but the constraints significantly reduce the search space.
• Space Complexity: O(N*N) for the board and O(N*N) for the recursion stack depth in the worst case (if the board is almost empty and we fill it one by one).

Dry Run: Sudoku Solver (Simplified)

Let's consider a small 2x2 Sudoku (where each 2x2 box must contain 1-4, and each row/column 1-4) for simplicity. A standard 9x9 dry run is too extensive.

Input (partial 4x4 board):

4 . . .
. . 2 .
. 1 . .
. . . 3

backtrackSudoku(board)

1. Find empty cell (0,1) (value '.').
2. Try num = '1':
   • isValidPlacement(board, 0, 1, '1') -> true.
   • board[0][1] = '1'.
   • Call backtrackSudoku(board) (for next empty cell).
     • Find empty cell (0,2).
     • Try num = '1' (invalid, row 0 has '1').
     • Try num = '2' (invalid, 2x2 box has '2').
     • Try num = '3' (valid).
     • board[0][2] = '3'.
     • Call backtrackSudoku(board).
       • ... (continue filling cells)
       • If a solution is found, return true all the way up.
       • If no solution is found, board[0][2] = '.' (backtrack).
     • Try num = '4' (valid).
     • board[0][2] = '4'.
     • Call backtrackSudoku(board).
       • ... (continue filling cells)
       • If a solution is found, return true.
       • If no solution, board[0][2] = '.' (backtrack).
     • If no digit works for (0,2), return false.
   • If backtrackSudoku returned false, board[0][1] = '.' (backtrack).
3. Try num = '2' for (0,1).
   • ... (and so on)

This process continues until a valid assignment for all empty cells is found, or all possibilities are exhausted.

Reusable Template for Sudoku Solver

import java.util.Arrays;

class SudokuSolver {

    /**
     * Solves the given Sudoku board in-place.
     * @param board The 9x9 Sudoku board, where '.' represents empty cells.
     */
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        backtrackSudoku(board);
    }

    /**
     * Recursive backtracking function to solve the Sudoku puzzle.
     * @param board The current state of the Sudoku board.
     * @return True if a solution is found, false otherwise.
     */
    private boolean backtrackSudoku(char[][] board) {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == ".") { // Find an empty cell
                    for (char num = '1'; num <= '9'; num++) { // Try digits 1-9
                        if (isValidPlacement(board, r, c, num)) {
                            board[r][c] = num; // Make a choice

                            if (backtrackSudoku(board)) { // Recurse for the next empty cell
                                return true; // Solution found, propagate true
                            }

                            board[r][c] = "."; // Undo choice (Backtrack)
                        }
                    }
                    return false; // No valid number for this cell, backtrack further
                }
            }
        }
        return true; // All cells filled, solution found
    }

    /**
     * Checks if placing 'num' at (row, col) is valid according to Sudoku rules.
     * @param board The current Sudoku board.
     * @param row The row index.
     * @param col The column index.
     * @param num The digit to check.
     * @return True if the placement is valid, false otherwise.
     */
    private boolean isValidPlacement(char[][] board, int row, int col, char num) {
        // Check row
        for (int c = 0; c < 9; c++) {
            if (board[row][c] == num) {
                return false;
            }
        }

        // Check column
        for (int r = 0; r < 9; r++) {
            if (board[r][col] == num) {
                return false;
            }
        }

        // Check 3x3 subgrid
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int r = startRow; r < startRow + 3; r++) {
            for (int c = startCol; c < startCol + 3; c++) {
                if (board[r][c] == num) {
                    return false;
                }
            }
        }
        return true;
    }
}

How to Recognize Sudoku Solver in Interviews

Look for these clues:

• Problem Type: Grid-based puzzle, constraint satisfaction, filling empty slots.
• Goal: Find a single valid configuration (or all valid configurations) that satisfies a set of rules.
• Keywords: "Sudoku", "fill grid", "valid placement", "rules", "unique solution".
• Structure: Often involves a square grid with sub-grids and rules about unique elements in rows, columns, and sub-grids.

Common Mistakes

Mistake 1: Incorrect isValidPlacement Logic

Any error in checking rows, columns, or 3x3 subgrids will lead to incorrect solutions or infinite loops. Double-check the boundary conditions for the 3x3 subgrid calculation.

Mistake 2: Forgetting to Backtrack

Not resetting the cell to '.' after a failed recursive call is a common mistake. This prevents other branches of the search tree from being explored correctly.

Mistake 3: Inefficient Validity Checks

While the provided isValidPlacement is O(N) (where N is the side length of the board), it's called frequently. For very large grids (though Sudoku is fixed at 9x9), optimizing these checks (e.g., using boolean arrays or bitmasks to track available numbers in rows, columns, and boxes) can be beneficial. For standard Sudoku, the current approach is generally acceptable.

Mistake 4: Handling Multiple Solutions

The problem statement often specifies a unique solution. If multiple solutions are possible, the backtrackSudoku function would need to collect all solutions rather than returning true on the first one found.

Sudoku Solver vs. Other Backtracking Problems

• N-Queens: Both are grid-based constraint satisfaction problems. N-Queens focuses on non-attacking placements, while Sudoku focuses on unique digit placements within specific regions.
• Permutations/Combinations: Sudoku involves placing elements into fixed positions on a grid, whereas permutations/combinations are about arranging/selecting elements from a set.
• Word Search: Word Search is about finding a path that spells a word, not about filling a grid with elements under strict numerical constraints.

Practice Problems for This Pattern

1. Sudoku Solver (LeetCode 37) - The classic problem itself.
2. N-Queens (LeetCode 51) - Another classic grid-based backtracking problem.
3. Word Search (LeetCode 79) - Grid traversal with backtracking to find a word.
4. Solve the Equation (LeetCode 640) - Can sometimes be approached with backtracking for finding integer solutions.

Interview Script You Can Reuse

"To solve this Sudoku puzzle, I'll use a backtracking approach. I'll iterate through the 9x9 grid to find the first empty cell. If no empty cells are found, it means the puzzle is solved, and I'll return true. For each empty cell, I'll try placing digits from '1' to '9'. Before placing a digit, I'll use a helper function `isValidPlacement` to check if the digit is valid for that cell (i.e., not present in its row, column, or 3x3 subgrid). If the placement is valid, I'll place the digit and recursively call the solver for the next empty cell. If the recursive call returns true, I'll propagate true upwards. If it returns false, I'll undo the placement (backtrack by setting the cell back to '.') and try the next digit. If no digit works for the current cell, I'll return false, triggering backtracking to the previous cell. The time complexity is exponential in the number of empty cells, but pruning significantly reduces the actual search space. Space complexity is O(N*N) for the board and recursion stack."

Final Takeaways

• Sudoku Solver is a classic application of backtracking for constraint satisfaction.
• It involves iterating through empty cells, trying valid digits, recursing, and backtracking.
• isValidPlacement is crucial for pruning the search space.
• Always remember to undo choices (set cell back to '.') during backtracking.

Mastering the Sudoku Solver provides valuable insights into solving grid-based puzzles and constraint satisfaction problems using backtracking.

Read Next

• DSA in Java Series
• N-Queens Problem in Java
• Word Search in Java
• Subset Sum and Partition Problems in Java
• Backtracking Pattern in Java: Permutations and Combinations
• Bellman-Ford Algorithm in Java
• Kruskal’s Algorithm in Java
• Prim’s Algorithm in Java
• Matrix Traversal in Java
• Lowest Common Ancestor (LCA) in Java
• Dijkstra’s Algorithm in Java
• Union Find (DSU) in Java
• Topological Sort in Java
• BFS (Breadth First Search) in Java
• DFS (Depth First Search) in Java
• Monotonic Queue Pattern in Java
• Monotonic Stack Pattern in Java
• Sorting Algorithms in Java
• Binary Search Pattern in Java
• In-place Reversal of a Linked List in Java
• Fast & Slow Pointers in Java
• Dutch National Flag Pattern in Java
• Kadane’s Algorithm in Java
• Prefix Sum Pattern in Java
• Sliding Window Pattern in Java
• Two Pointers Pattern in Java
• Big-O Notation in Java