Sudoku Solver Using Backtracking in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sudoku Board After One Backtracking Step

Given the initial Sudoku board and one step of backtracking filling the first empty cell, what is the printed board state?

DSA Python

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

# After one backtracking step, the first empty cell (row 0, col 2) is filled with 4
board[0][2] = 4

for row in board:
    print(' -> '.join(str(num) for num in row) + ' -> null')

A

5 -> 3 -> 1 -> 0 -> 7 -> 0 -> 0 -> 0 -> 0 -> null
6 -> 0 -> 0 -> 1 -> 9 -> 5 -> 0 -> 0 -> 0 -> null
0 -> 9 -> 8 -> 0 -> 0 -> 0 -> 0 -> 6 -> 0 -> null
8 -> 0 -> 0 -> 0 -> 6 -> 0 -> 0 -> 0 -> 3 -> null
4 -> 0 -> 0 -> 8 -> 0 -> 3 -> 0 -> 0 -> 1 -> null
7 -> 0 -> 0 -> 0 -> 2 -> 0 -> 0 -> 0 -> 6 -> null
0 -> 6 -> 0 -> 0 -> 0 -> 0 -> 2 -> 8 -> 0 -> null
0 -> 0 -> 0 -> 4 -> 1 -> 9 -> 0 -> 0 -> 5 -> null
0 -> 0 -> 0 -> 0 -> 8 -> 0 -> 0 -> 7 -> 9 -> null

B

5 -> 3 -> 0 -> 0 -> 7 -> 0 -> 0 -> 0 -> 0 -> null
6 -> 0 -> 0 -> 1 -> 9 -> 5 -> 0 -> 0 -> 0 -> null
0 -> 9 -> 8 -> 0 -> 0 -> 0 -> 0 -> 6 -> 0 -> null
8 -> 0 -> 0 -> 0 -> 6 -> 0 -> 0 -> 0 -> 3 -> null
4 -> 0 -> 0 -> 8 -> 0 -> 3 -> 0 -> 0 -> 1 -> null
7 -> 0 -> 0 -> 0 -> 2 -> 0 -> 0 -> 0 -> 6 -> null
0 -> 6 -> 0 -> 0 -> 0 -> 0 -> 2 -> 8 -> 0 -> null
0 -> 0 -> 0 -> 4 -> 1 -> 9 -> 0 -> 0 -> 5 -> null
0 -> 0 -> 0 -> 0 -> 8 -> 0 -> 0 -> 7 -> 9 -> null

C

5 -> 3 -> 4 -> 0 -> 7 -> 0 -> 0 -> 0 -> 0 -> null
6 -> 0 -> 0 -> 1 -> 9 -> 5 -> 0 -> 0 -> 0 -> null
0 -> 9 -> 8 -> 0 -> 0 -> 0 -> 0 -> 6 -> 0 -> null
8 -> 0 -> 0 -> 0 -> 6 -> 0 -> 0 -> 0 -> 3 -> null
4 -> 0 -> 0 -> 8 -> 0 -> 3 -> 0 -> 0 -> 1 -> null
7 -> 0 -> 0 -> 0 -> 2 -> 0 -> 0 -> 0 -> 6 -> null
0 -> 6 -> 0 -> 0 -> 0 -> 0 -> 2 -> 8 -> 0 -> null
0 -> 0 -> 0 -> 4 -> 1 -> 9 -> 0 -> 0 -> 5 -> null
0 -> 0 -> 0 -> 0 -> 8 -> 0 -> 0 -> 7 -> 9 -> null

D

5 -> 3 -> 9 -> 0 -> 7 -> 0 -> 0 -> 0 -> 0 -> null
6 -> 0 -> 0 -> 1 -> 9 -> 5 -> 0 -> 0 -> 0 -> null
0 -> 9 -> 8 -> 0 -> 0 -> 0 -> 0 -> 6 -> 0 -> null
8 -> 0 -> 0 -> 0 -> 6 -> 0 -> 0 -> 0 -> 3 -> null
4 -> 0 -> 0 -> 8 -> 0 -> 3 -> 0 -> 0 -> 1 -> null
7 -> 0 -> 0 -> 0 -> 2 -> 0 -> 0 -> 0 -> 6 -> null
0 -> 6 -> 0 -> 0 -> 0 -> 0 -> 2 -> 8 -> 0 -> null
0 -> 0 -> 0 -> 4 -> 1 -> 9 -> 0 -> 0 -> 5 -> null
0 -> 0 -> 0 -> 0 -> 8 -> 0 -> 0 -> 7 -> 9 -> null

💡 Hint

Look at the first empty cell in the top-left row and what number backtracking tries first.

Backtracking fills the first empty cell (row 0, col 2) with the smallest valid number, which is 4 here. Other options show wrong numbers or unchanged board.

🧠 Conceptual

intermediate

Understanding Backtracking in Sudoku Solver

Which of the following best describes the role of backtracking in solving Sudoku puzzles?

A Backtracking removes numbers from the board until only one solution remains.

B Backtracking fills all empty cells with random numbers and then checks if the puzzle is solved.

C Backtracking solves Sudoku by sorting the numbers in each row and column.

D Backtracking tries numbers in empty cells and moves forward only if the number is valid, otherwise it goes back to try a different number.

💡 Hint

Think about how backtracking tries and undoes choices.

Backtracking is a trial and error method that tries numbers in empty cells and backtracks if a number leads to no solution.

🔧 Debug

advanced

Identify the Error in Sudoku Validity Check

What error will this code raise when checking if a number can be placed in a Sudoku cell?

DSA Python

def is_valid(board, row, col, num):
    for i in range(9):
        if board[row][i] == num:
            return False
    for j in range(9):
        if board[j][col] == num:
            return False
    start_row = row // 3 * 3
    start_col = col // 3 * 3
    for i in range(start_row, start_row + 3):
        for j in range(start_col, start_col + 3):
            if board[i][j] == num:
                return False
    return True

board = [[0]*9 for _ in range(9)]
print(is_valid(board, 0, 0, 5))

A IndexError due to wrong loop ranges

B No error, returns True

C TypeError because board is not initialized properly

D NameError because variable 'num' is undefined

💡 Hint

Check the loops and variable usage carefully.

The code correctly checks row, column, and 3x3 box for the number. The board is initialized as a 9x9 grid of zeros, so no error occurs and True is returned.

❓ Predict Output

advanced

Final Sudoku Board After Complete Backtracking Solve

What is the final printed Sudoku board after the solver completes on this puzzle?

DSA Python

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

# Assume solver fills all empty cells correctly
solved_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]
]

for row in solved_board:
    print(' -> '.join(str(num) for num in row) + ' -> null')

A

5 -> 3 -> 4 -> 6 -> 7 -> 8 -> 9 -> 1 -> 2 -> null
6 -> 7 -> 2 -> 1 -> 9 -> 5 -> 3 -> 4 -> 8 -> null
1 -> 9 -> 8 -> 3 -> 4 -> 2 -> 5 -> 6 -> 7 -> null
8 -> 5 -> 9 -> 7 -> 6 -> 1 -> 4 -> 2 -> 3 -> null
4 -> 2 -> 6 -> 8 -> 5 -> 3 -> 7 -> 9 -> 1 -> null
7 -> 1 -> 3 -> 9 -> 2 -> 4 -> 8 -> 5 -> 6 -> null
9 -> 6 -> 1 -> 5 -> 3 -> 7 -> 2 -> 8 -> 4 -> null
2 -> 8 -> 7 -> 4 -> 1 -> 9 -> 6 -> 3 -> 5 -> null
3 -> 4 -> 5 -> 2 -> 8 -> 6 -> 1 -> 7 -> 9 -> null

B

5 -> 3 -> 4 -> 6 -> 7 -> 8 -> 9 -> 1 -> 2 -> null
6 -> 7 -> 2 -> 1 -> 9 -> 5 -> 3 -> 4 -> 8 -> null
1 -> 9 -> 8 -> 3 -> 4 -> 2 -> 5 -> 6 -> 7 -> null
8 -> 5 -> 9 -> 7 -> 6 -> 1 -> 4 -> 2 -> 3 -> null
4 -> 2 -> 6 -> 8 -> 5 -> 3 -> 7 -> 9 -> 1 -> null
7 -> 1 -> 3 -> 9 -> 2 -> 4 -> 8 -> 5 -> 0 -> null
9 -> 6 -> 1 -> 5 -> 3 -> 7 -> 2 -> 8 -> 4 -> null
2 -> 8 -> 7 -> 4 -> 1 -> 9 -> 6 -> 3 -> 5 -> null
3 -> 4 -> 5 -> 2 -> 8 -> 6 -> 1 -> 7 -> 9 -> null

C

5 -> 3 -> 4 -> 6 -> 7 -> 8 -> 9 -> 1 -> 2 -> null
6 -> 7 -> 2 -> 1 -> 9 -> 5 -> 3 -> 4 -> 8 -> null
1 -> 9 -> 8 -> 3 -> 4 -> 2 -> 5 -> 6 -> 7 -> null
8 -> 5 -> 9 -> 7 -> 6 -> 1 -> 4 -> 2 -> 3 -> null
4 -> 2 -> 6 -> 8 -> 5 -> 3 -> 7 -> 9 -> 1 -> null
7 -> 1 -> 3 -> 9 -> 2 -> 4 -> 8 -> 5 -> 6 -> null
9 -> 6 -> 1 -> 5 -> 3 -> 7 -> 2 -> 8 -> 4 -> null
2 -> 8 -> 7 -> 4 -> 1 -> 9 -> 6 -> 3 -> 5 -> null
3 -> 4 -> 5 -> 2 -> 8 -> 6 -> 1 -> 7 -> 0 -> null

D

llun >- 9 >- 7 >- 1 >- 6 >- 8 >- 2 >- 5 >- 4 >- 3
llun >- 5 >- 3 >- 6 >- 9 >- 1 >- 4 >- 7 >- 8 >- 2
llun >- 4 >- 8 >- 2 >- 7 >- 3 >- 5 >- 1 >- 6 >- 9
llun >- 6 >- 5 >- 8 >- 4 >- 2 >- 9 >- 3 >- 1 >- 7
llun >- 1 >- 9 >- 7 >- 3 >- 5 >- 8 >- 6 >- 2 >- 4
llun >- 3 >- 2 >- 4 >- 1 >- 6 >- 7 >- 9 >- 5 >- 8
llun >- 7 >- 6 >- 5 >- 2 >- 4 >- 3 >- 8 >- 9 >- 1
llun >- 8 >- 4 >- 3 >- 5 >- 9 >- 1 >- 2 >- 7 >- 6
llun >- 2 >- 1 >- 9 >- 8 >- 7 >- 6 >- 4 >- 3 >- 5

💡 Hint

Check carefully for any zeros left in the final board.

Option A shows the fully solved Sudoku board with no zeros. Other options have zeros indicating incomplete or incorrect solutions.

🚀 Application

expert

Minimum Number of Backtracking Calls for a Sudoku Puzzle

If a Sudoku solver uses backtracking and the puzzle has 40 empty cells, what is the minimum number of recursive calls the solver must make to guarantee a solution?

A At least 40 calls, but possibly many more due to backtracking retries

B Exactly 40 calls, one per empty cell

C Exactly 81 calls, one per cell in the board

D At most 40 calls, because backtracking skips invalid cells

💡 Hint

Consider how backtracking explores multiple possibilities per cell.

Backtracking tries numbers and may retry multiple times per cell, so the number of calls is at least the number of empty cells but often much higher.

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