Sudoku Solver Using Backtracking in DSA Python - Execution Trace

Concept Flow - Sudoku Solver Using Backtracking

Start with empty cell

↓

Try number 1 to 9

↓

Is number valid?

No→Try next number

Yes↓

Place number

↓

Move to next empty cell

↓

Repeat until all cells filled

↓

If stuck, backtrack to previous cell

↓

Try next number in previous cell

↩Back to validity check

The solver tries numbers 1-9 in each empty cell, checks if valid, places it, moves forward, and backtracks if stuck.

Execution Sample

DSA Python

def solve(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                for num in range(1,10):
                    if valid(board, i, j, num):
                        board[i][j] = num
                        if solve(board):
                            return True
                        board[i][j] = 0
                return False
    return True

This code tries to fill empty cells with valid numbers using backtracking until the board is solved.

Execution Table

Step	Operation	Cell (row,col)	Number Tried	Valid?	Action	Board State (partial visual)
1	Find empty cell	(0,0)	-	-	Empty cell found	[0,0,0,...] (row 0 partial)
2	Try number	(0,0)	1	No	Try next number	[0,0,0,...]
3	Try number	(0,0)	2	Yes	Place number	[2,0,0,...]
4	Move to next empty	(0,1)	-	-	Empty cell found	[2,0,0,...]
5	Try number	(0,1)	1	Yes	Place number	[2,1,0,...]
6	Move to next empty	(0,2)	-	-	Empty cell found	[2,1,0,...]
7	Try number	(0,2)	1	No	Try next number	[2,1,0,...]
8	Try number	(0,2)	3	Yes	Place number	[2,1,3,...]
9	Move to next empty	(0,3)	-	-	Empty cell found	[2,1,3,0,...]
10	Try number	(0,3)	1	No	Try next number	[2,1,3,0,...]
11	Try number	(0,3)	4	Yes	Place number	[2,1,3,4,...]
12	Move to next empty	(0,4)	-	-	Empty cell found	[2,1,3,4,0,...]
...	...	...	...	...	...	...
N-2	Backtrack	(0,4)	9	No	Reset cell to 0	[2,1,3,4,0,...]
N-1	Backtrack	(0,3)	4	No further numbers	Reset cell to 0	[2,1,3,0,0,...]
N	Backtrack	(0,2)	3	Try next number	Reset cell to 0 and try next	[2,1,0,0,0,...]
Exit	All cells filled	-	-	-	Sudoku solved	[Full board with no zeros]

💡 All cells filled with valid numbers, backtracking complete, puzzle solved.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 8	After Step 11	Final
board[0][0]	0	2	2	2	2	Filled
board[0][1]	0	0	1	1	1	Filled
board[0][2]	0	0	0	3	3	Filled
board[0][3]	0	0	0	0	4	Filled

Key Moments - 3 Insights

Why do we reset a cell to 0 during backtracking?

When a number placed leads to no solution ahead, we reset the cell to 0 to try other numbers later, as shown in steps N-2 to N.

How do we know if a number is valid in a cell?

We check if the number is not already in the same row, column, or 3x3 box before placing it, as indicated in the 'Valid?' column in steps 2, 5, 7.

What happens when all numbers 1-9 fail in a cell?

We backtrack to the previous cell to try a different number, shown in steps N-1 and N.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what number was placed in cell (0,0)?

A 1

B 2

C 3

D 0

💡 Hint

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

At which step does the solver backtrack from cell (0,4)?

A Step 10

B Step N-2

C Step 5

D Step 1

💡 Hint

Look for 'Backtrack' operations in the execution_table and find the step mentioning cell (0,4).

If the number 2 was valid at cell (0,1), how would the board state change after step 5?

A board[0][1] would be 2

B board[0][1] would remain 0

C board[0][0] would change to 2

D No change in board

💡 Hint

Check variable_tracker for board[0][1] after step 5 and relate to the 'Place number' action.

Concept Snapshot

Sudoku Solver Using Backtracking:
- Find an empty cell
- Try numbers 1 to 9
- Check if number is valid (row, column, box)
- Place number and move forward
- If stuck, backtrack and try next number
- Repeat until board is complete

Full Transcript

The Sudoku solver uses backtracking to fill empty cells. It starts at the first empty cell and tries numbers 1 through 9. For each number, it checks if placing it is valid by ensuring no conflicts in the row, column, or 3x3 box. If valid, it places the number and moves to the next empty cell. If no number fits, it backtracks to the previous cell to try a different number. This process repeats until all cells are filled correctly, solving the puzzle.

Practice

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

easy

A. To count how many empty cells are in the Sudoku grid

B. To randomly fill the Sudoku grid without checking rules

C. To sort the numbers in each row before solving

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

Solution

1. Step 1: Understand backtracking role

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

2. Step 2: Compare other options

   Other options do not describe backtracking's trial and error approach.

3. Final Answer:

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

4. Quick Check:

   Backtracking = Try and undo choices [OK]

Hint: Backtracking means try, check, and undo if wrong [OK]

Common Mistakes:

• Thinking backtracking fills randomly without checks
• Confusing backtracking with sorting or counting
• Ignoring the undo step in backtracking

2. Which of the following is the correct Python syntax to check if a number is safe to place in a Sudoku cell using backtracking?

easy

A. if is_safe(board, row, col, num):

B. if isSafe(board, row, col, num);

C. if is_safe(board, row, col, num)

D. if is_safe board, row, col, num:

Solution

1. Step 1: Identify correct function call syntax

   Python requires parentheses and a colon after the if condition, so 'if is_safe(board, row, col, num):' is correct.

2. Step 2: Check other options for syntax errors

   if isSafe(board, row, col, num); uses semicolon instead of colon; C misses colon; D misses parentheses.

3. Final Answer:

   if is_safe(board, row, col, num): -> Option A

4. Quick Check:

   Python if syntax = condition + colon [OK]

Hint: Remember if statements end with a colon in Python [OK]

Common Mistakes:

• Forgetting the colon at the end of if statement
• Missing parentheses around function arguments
• Using semicolon instead of colon

3. What will be the output of the following code snippet when solving a Sudoku board with backtracking?

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]
]

solve_sudoku(board)
print(board)

medium

A. [[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]]

B. [[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]]

C. SyntaxError

D. RuntimeError

Solution

1. Step 1: Understand solve_sudoku function effect

   The solve_sudoku function fills empty cells (zeros) with correct numbers to complete the Sudoku board.

2. Step 2: Analyze output after solving

   After solving, the board will be fully filled with valid numbers, matching [[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]]'s completed grid.

3. Final Answer:

   Completed Sudoku board with all zeros replaced by correct numbers -> Option A

4. Quick Check:

   Backtracking fills zeros to complete board [OK]

Hint: Backtracking fills zeros to complete Sudoku [OK]

Common Mistakes:

• Expecting the board to remain unchanged after solve
• Confusing syntax or runtime errors with correct output
• Not recognizing that zeros are placeholders for empty cells

4. Identify the error in this backtracking Sudoku solver code snippet:

def solve(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1, 10):
                    if is_safe(board, row, col, num):
                        board[row][col] = num
                        if solve(board):
                            return True
                        board[row][col] = 0
                return False
    return True

# Error: The function is_safe is not defined anywhere.

medium

A. The range for num should be range(0, 9)

B. The board size should be 8 instead of 9

C. The function is_safe is missing, causing NameError

D. The function solve should return False at the end

Solution

1. Step 1: Check for missing functions

   The code calls is_safe but does not define it, causing a NameError at runtime.

2. Step 2: Verify other options

   Board size 9 is correct for Sudoku; num range 1-9 is correct; solve returns True at end which is correct.

3. Final Answer:

   The function is_safe is missing, causing NameError -> Option C

4. Quick Check:

   Undefined function causes NameError [OK]

Hint: Always define helper functions before calling them [OK]

Common Mistakes:

• Assuming board size is 8 instead of 9
• Using wrong range for numbers (should be 1 to 9)
• Forgetting to return True when solved

5. Given a partially filled Sudoku board, which strategy best improves the efficiency of the backtracking solver?

hard

A. Fill cells randomly without checking constraints

B. Always pick the next empty cell with the fewest possible valid numbers

C. Try numbers in ascending order without checking row or column

D. Restart solving from the first cell after each failed attempt

Solution

1. Step 1: Understand backtracking optimization

   Choosing the empty cell with the fewest valid options reduces branching and speeds solving.

2. Step 2: Evaluate other options

   Random filling ignores constraints; trying numbers without checks wastes time; restarting after failure is inefficient.

3. Final Answer:

   Always pick the next empty cell with the fewest possible valid numbers -> Option B

4. Quick Check:

   Minimum options first = faster backtracking [OK]

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

Common Mistakes:

• Ignoring constraints when filling cells
• Trying numbers in fixed order without pruning
• Restarting solving unnecessarily wastes time