Sudoku Solver Using Backtracking in DSA Java

Mental Model

Try filling empty cells one by one with numbers that follow Sudoku rules, and backtrack if a number causes a conflict.

Analogy: Like trying keys on a locked door one by one; if a key doesn't fit, you go back and try another key until the door opens.

5 3 _ | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

_ means empty cell

Dry Run Walkthrough

Input: Partially filled 9x9 Sudoku board with some empty cells (represented by 0 or _).

Goal: Fill all empty cells with digits 1-9 so that each row, column, and 3x3 box contains all digits without repetition.

Step 1: Find first empty cell at row 0, column 2; try number 1.

5 3 [1] | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Try smallest valid number to fill empty cell to keep options open.

Step 2: Check if 1 is valid in that cell; it conflicts with 1 in row 1, column 3, so try 2.

5 3 [2] | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Try next number since 1 was invalid.

Step 3: 2 is valid; place 2 and move to next empty cell at row 0, column 3.

5 3 2 | [_] 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Fill cells one by one to solve the puzzle.

Step 4: Try numbers 1 to 9 in cell (0,3); 1 conflicts in column, 3 conflicts in box, 4 is valid; place 4.

5 3 2 | [4] 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Choose a valid number to continue solving.

Step 5: Continue filling cells; if stuck, backtrack to previous cell and try next number.

Eventually all cells filled correctly:
5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9

Why: Backtracking ensures all possibilities are tried to find the solution.

Result:

Final solved Sudoku board:
5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9

Annotated Code

DSA Java

public class SudokuSolver {
    private static final int SIZE = 9;

    public static boolean solveSudoku(int[][] board) {
        for (int row = 0; row < SIZE; row++) {
            for (int col = 0; col < SIZE; col++) {
                if (board[row][col] == 0) { // find empty cell
                    for (int num = 1; num <= SIZE; num++) {
                        if (isValid(board, row, col, num)) {
                            board[row][col] = num; // place number
                            if (solveSudoku(board)) {
                                return true; // solved
                            } else {
                                board[row][col] = 0; // backtrack
                            }
                        }
                    }
                    return false; // no valid number found
                }
            }
        }
        return true; // all cells filled
    }

    private static boolean isValid(int[][] board, int row, int col, int num) {
        // check row
        for (int c = 0; c < SIZE; c++) {
            if (board[row][c] == num) {
                return false;
            }
        }
        // check column
        for (int r = 0; r < SIZE; r++) {
            if (board[r][col] == num) {
                return false;
            }
        }
        // check 3x3 box
        int boxRowStart = (row / 3) * 3;
        int boxColStart = (col / 3) * 3;
        for (int r = boxRowStart; r < boxRowStart + 3; r++) {
            for (int c = boxColStart; c < boxColStart + 3; c++) {
                if (board[r][c] == num) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void printBoard(int[][] board) {
        for (int r = 0; r < SIZE; r++) {
            if (r % 3 == 0 && r != 0) {
                System.out.println("------+-------+------");
            }
            for (int c = 0; c < SIZE; c++) {
                if (c % 3 == 0 && c != 0) {
                    System.out.print("| ");
                }
                System.out.print(board[r][c] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] board = {
            {5,3,0,0,7,0,0,0,0},
            {6,0,0,1,9,5,0,0,0},
            {0,9,8,0,0,0,0,6,0},
            {8,0,0,0,6,0,0,0,3},
            {4,0,0,8,0,3,0,0,1},
            {7,0,0,0,2,0,0,0,6},
            {0,6,0,0,0,0,2,8,0},
            {0,0,0,4,1,9,0,0,5},
            {0,0,0,0,8,0,0,7,9}
        };

        if (solveSudoku(board)) {
            printBoard(board);
        } else {
            System.out.println("No solution exists");
        }
    }
}

if (board[row][col] == 0) { // find empty cell

Locate next empty cell to fill

for (int num = 1; num <= SIZE; num++) {

Try all possible numbers 1 to 9

if (isValid(board, row, col, num)) {

Check if placing num is valid by Sudoku rules

board[row][col] = num; // place number

Place number tentatively

if (solveSudoku(board)) { return true; } else { board[row][col] = 0; }

Recursively solve rest; backtrack if dead end

return false; // no valid number found

Backtrack when no number fits

return true; // all cells filled

Puzzle solved successfully

check row, column, and 3x3 box for conflicts

Validate number placement

Output

5 3 4 | 6 7 8 | 9 1 2 

6 7 2 | 1 9 5 | 3 4 8 

1 9 8 | 3 4 2 | 5 6 7 

------+-------+------

8 5 9 | 7 6 1 | 4 2 3 

4 2 6 | 8 5 3 | 7 9 1 

7 1 3 | 9 2 4 | 8 5 6 

------+-------+------

9 6 1 | 5 3 7 | 2 8 4 

2 8 7 | 4 1 9 | 6 3 5 

3 4 5 | 2 8 6 | 1 7 9 

Complexity Analysis

Time: O(9^(n)) where n is number of empty cells, because each empty cell tries up to 9 numbers recursively

Space: O(n) due to recursion stack for n empty cells

vs Alternative: Backtracking is more efficient than brute force checking all 9^81 board states by pruning invalid paths early

Edge Cases

Empty board (all zeros)

Solver tries all possibilities; may take longer but still finds solution

DSA Java

if (board[row][col] == 0) {

Already solved board

Solver returns true immediately without changes

DSA Java

return true; // all cells filled

No solution board (contradictory clues)

Solver backtracks fully and returns false

DSA Java

return false; // no valid number found

When to Use This Pattern

When you need to fill a grid with constraints and try all options systematically, use backtracking to explore and undo choices until a valid solution is found.

Common Mistakes

Mistake: Not resetting the cell to 0 when backtracking
Fix: Set board[row][col] = 0 before returning false to undo the tentative placement

Mistake: Checking only row or column but not the 3x3 box for validity
Fix: Include 3x3 box check in isValid function to ensure Sudoku rules

Summary

It fills empty Sudoku cells one by one using trial and error and backtracking when stuck.

Use it when you must find a valid arrangement under strict constraints like Sudoku.

The key insight is to try a number, move forward, and undo if it leads to a dead end.

Practice

1. What is the main purpose of backtracking in a Sudoku solver?

easy

A. To randomly fill the Sudoku board with numbers

B. To try possible numbers and undo choices if they lead to conflicts

C. To sort the Sudoku board numbers in ascending order

D. To count how many empty cells are in the Sudoku board

Solution

1. Step 1: Understand backtracking role

   Backtracking tries numbers in empty cells and removes them if they cause conflicts.

2. Step 2: Compare with other options

   Sorting or random filling does not solve Sudoku logically; counting empty cells is not solving.

3. Final Answer:

   To try possible numbers and undo choices if they lead to conflicts -> Option B

4. Quick Check:

   Backtracking = Try and undo choices [OK]

Hint: Backtracking means try and undo wrong moves [OK]

Common Mistakes:

• Thinking backtracking sorts numbers
• Assuming backtracking fills randomly
• Confusing backtracking with counting cells

2. Which of the following Java method signatures correctly represents a backtracking Sudoku solver method?

easy

A. public boolean solveSudoku(int[][] board)

B. void solveSudoku(int board[][])

C. public int solveSudoku(int[][] board, int row, int col)

D. boolean solveSudoku()

Solution

1. Step 1: Check method return type and parameters

   The solver should return boolean to indicate success and take the board as input.

2. Step 2: Validate options

   public boolean solveSudoku(int[][] board) matches this: returns boolean and takes int[][] board. void solveSudoku(int board[][]) returns void, not suitable. public int solveSudoku(int[][] board, int row, int col) returns int and has extra parameters, uncommon. boolean solveSudoku() has no parameters, so can't solve given board.

3. Final Answer:

   public boolean solveSudoku(int[][] board) -> Option A

4. Quick Check:

   Boolean return + board parameter = public boolean solveSudoku(int[][] board) [OK]

Hint: Solver returns boolean and takes board as int[][] [OK]

Common Mistakes:

• Using void return type for solver
• Missing board parameter
• Returning int instead of boolean

3. What will be the output of the following code snippet after calling solveSudoku(board) on a partially filled 9x9 Sudoku board?

int[][] board = {
  {5,3,0,0,7,0,0,0,0},
  {6,0,0,1,9,5,0,0,0},
  {0,9,8,0,0,0,0,6,0},
  {8,0,0,0,6,0,0,0,3},
  {4,0,0,8,0,3,0,0,1},
  {7,0,0,0,2,0,0,0,6},
  {0,6,0,0,0,0,2,8,0},
  {0,0,0,4,1,9,0,0,5},
  {0,0,0,0,8,0,0,7,9}
};
boolean solved = solveSudoku(board);
System.out.println(solved);

medium

A. Compilation error

B. false

C. true

D. Runtime exception

Solution

1. Step 1: Understand the input board

   The given board is a valid Sudoku puzzle with empty cells (0) and solvable configuration.

2. Step 2: Analyze solveSudoku output

   Backtracking solver returns true if it finds a solution. Since this is a standard solvable puzzle, it returns true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Solvable board returns true [OK]

Hint: Valid puzzle solved returns true [OK]

Common Mistakes:

• Assuming false means no solution without checking
• Confusing output with board print
• Expecting exceptions on valid input

4. Identify the bug in this backtracking Sudoku solver snippet:

public boolean solveSudoku(int[][] board) {
  for (int row = 0; row < 9; row++) {
    for (int col = 0; col < 9; col++) {
      if (board[row][col] == 0) {
        for (int num = 1; num <= 9; num++) {
          if (isSafe(board, row, col, num)) {
            board[row][col] = num;
            if (solveSudoku(board)) {
              return true;
            } else {
              board[row][col] = 0;
            }
          }
        }
        return false;
      }
    }
  }
  return true;
}

medium

A. Using wrong data type for board

B. Incorrect loop ranges for row and col

C. Not checking if board is already solved before recursion

D. Missing return false when no number fits in empty cell

Solution

1. Step 1: Analyze the nested loops and recursion

   The code tries numbers 1-9 in empty cells and recurses if safe.

2. Step 2: Identify missing return false

   If no number fits, the function should return false to backtrack, but here it continues loops and returns true at end incorrectly.

3. Final Answer:

   Missing return false when no number fits in empty cell -> Option D

4. Quick Check:

   Backtracking needs return false on failure [OK]

Hint: Return false if no valid number found in cell [OK]

Common Mistakes:

• Forgetting to return false to backtrack
• Returning true too early
• Ignoring base case for solved board

5. Given a 9x9 Sudoku board with multiple empty cells, which approach best improves the efficiency of the backtracking solver?

hard

A. Use a heuristic to select the empty cell with the fewest possible valid numbers first

B. Try numbers 1 to 9 in order for each empty cell without any checks

C. Fill all empty cells with 1 initially and then backtrack

D. Randomly assign numbers to empty cells and check if solved

Solution

1. Step 1: Understand naive backtracking

   Trying numbers 1-9 in order for each cell is simple but slow for complex puzzles.

2. Step 2: Identify heuristic improvement

   Selecting the empty cell with fewest valid options (minimum remaining value heuristic) reduces branching and speeds solving.

3. Step 3: Evaluate other options

   Filling all with 1 or random assignment leads to many conflicts and inefficiency.

4. Final Answer:

   Use a heuristic to select the empty cell with the fewest possible valid numbers first -> Option A

5. Quick Check:

   Heuristic cell choice speeds backtracking [OK]

Hint: Pick cell with fewest options first to speed solving [OK]

Common Mistakes:

• Trying numbers blindly without heuristics
• Filling cells with fixed number initially
• Random assignments causing many retries