Sudoku Solver Using Backtracking in DSA Java - Execution Trace

Concept Flow - Sudoku Solver Using Backtracking

Start with initial board

↓

Find empty cell

↓

Try numbers 1 to 9

↓

Check if number is safe

↓

Place num

↓

Move to next empty

↓

Repeat until board full

↓

Solved

The solver finds an empty cell, tries numbers 1-9, places a safe number, moves forward, and backtracks if stuck until the board is solved.

Execution Sample

DSA Java

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

This code tries numbers 1 to 9 in an empty cell, places a safe number, recursively solves the rest, and backtracks if needed.

Execution Table

Step	Operation	Cell (row,col)	Number Tried	Is Safe?	Action	Board State (partial visual)
1	Find empty cell	(0,2)	-	-	Start trying numbers	[5 3 0 | 0 7 0 | 0 0 0]
2	Try number	(0,2)	1	No	Try next number	[5 3 0 | 0 7 0 | 0 0 0]
3	Try number	(0,2)	2	No	Try next number	[5 3 0 | 0 7 0 | 0 0 0]
4	Try number	(0,2)	3	No	Try next number	[5 3 0 | 0 7 0 | 0 0 0]
5	Try number	(0,2)	4	Yes	Place 4	[5 3 4 | 0 7 0 | 0 0 0]
6	Find next empty	(0,3)	-	-	Start trying numbers	[5 3 4 | 0 7 0 | 0 0 0]
7	Try number	(0,3)	1	Yes	Place 1	[5 3 4 | 1 7 0 | 0 0 0]
8	Find next empty	(0,5)	-	-	Start trying numbers	[5 3 4 | 1 7 0 | 0 0 0]
9	Try number	(0,5)	2	No	Try next number	[5 3 4 | 1 7 0 | 0 0 0]
10	Try number	(0,5)	3	No	Try next number	[5 3 4 | 1 7 0 | 0 0 0]
11	Try number	(0,5)	4	No	Try next number	[5 3 4 | 1 7 0 | 0 0 0]
12	Try number	(0,5)	5	Yes	Place 5	[5 3 4 | 1 7 5 | 0 0 0]
13	Find next empty	(0,6)	-	-	Start trying numbers	[5 3 4 | 1 7 5 | 0 0 0]
14	Try number	(0,6)	1	No	Try next number	[5 3 4 | 1 7 5 | 0 0 0]
15	Try number	(0,6)	2	Yes	Place 2	[5 3 4 | 1 7 5 | 2 0 0]
...	...	...	...	...	...	...
N	Backtrack	(0,6)	No valid number	-	Remove 2, try next at (0,6)	[5 3 4 | 1 7 5 | 0 0 0]
N+1	Backtrack	(0,5)	No valid number	-	Remove 5, try next at (0,5)	[5 3 4 | 1 7 0 | 0 0 0]
N+2	Backtrack	(0,3)	No valid number	-	Remove 1, try next at (0,3)	[5 3 4 | 0 7 0 | 0 0 0]
Final	Board solved	-	-	-	All cells filled correctly	[5 3 4 | 6 7 8 | 9 1 2]

💡 All cells filled with safe numbers, board solved successfully

Variable Tracker

Variable	Start	After Step 5	After Step 12	After Step 15	Final
board[0][2]	0	4	4	4	4
board[0][3]	0	0	1	1	6
board[0][5]	0	0	5	5	8
board[0][6]	0	0	0	2	9
current cell	(0,2)	(0,3)	(0,5)	(0,6)	board complete

Key Moments - 3 Insights

Why do we backtrack by removing a number from the board?

When no number 1-9 fits safely in a cell (see steps N to N+2), we remove the last placed number to try a different number earlier. This is backtracking to fix wrong guesses.

How does the solver know which cell to fill next?

After placing a number safely, the solver searches for the next empty cell (see steps 6, 8, 13). It always moves forward cell by cell.

What does 'isSafe' check before placing a number?

'isSafe' ensures the number is not already in the same row, column, or 3x3 box (see 'Is Safe?' column in execution_table). Only safe numbers are placed.

Visual Quiz - 3 Questions

Look at the execution table at step 5. What number was placed in cell (0,2)?

A 4

B 3

C 1

D 0

💡 Hint

Check the 'Number Tried' and 'Action' columns at step 5 in the execution_table.

At which step does the solver backtrack by removing a number?

A Step 5

B Step N

C Step 12

D Step 15

💡 Hint

Look for 'Backtrack' operations in the 'Operation' column in the execution_table.

If the number 4 was not safe at cell (0,2), what would the solver do next?

A Place 4 anyway

B Backtrack immediately

C Try number 5 at (0,2)

D Stop solving

💡 Hint

Refer to the flow where the solver tries numbers 1 to 9 until a safe one is found.

Concept Snapshot

Sudoku Solver Using Backtracking:
- Find an empty cell
- Try numbers 1 to 9
- Check if number is safe (row, col, box)
- Place number if safe and recurse
- Backtrack if stuck (remove number)
- Repeat until board is complete

Full Transcript

The Sudoku solver uses backtracking to fill empty cells. It finds an empty cell, tries numbers 1 through 9, and checks if placing a number is safe by ensuring no conflicts in the row, column, or 3x3 box. If safe, it places the number and moves to the next empty cell recursively. If no number fits, it backtracks by removing the last placed number and tries the next possible number. This process repeats until the entire board is filled correctly, solving the puzzle.

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