Bird
Raised Fist0
DSA Pythonprogramming

Sudoku Solver Using Backtracking in DSA Python

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Mental Model
Try placing numbers one by one in empty cells and backtrack if a number breaks Sudoku rules.
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
ā†‘ empty cells marked as _
Dry Run Walkthrough
Input: Partial Sudoku board with some empty cells (represented by 0): [[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]]
Goal: Fill all empty cells with numbers 1-9 so that each row, column, and 3x3 box contains all digits without repetition.
Step 1: Find first empty cell at position (0,2) and 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 number to see if it fits Sudoku rules in this cell
Step 2: Check if 1 is valid at (0,2); it's valid, so place 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: Number 1 fits rules, so move to next empty cell
Step 3: Move to next empty cell (0,3), try number 1
5 3 1 | [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 placing 1 in next empty cell
Step 4: Check if 1 is valid at (0,3); it's invalid (conflicts with (1,3)), so try 2
5 3 1 | [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 conflicts with Sudoku rules
Step 5: Check if 2 is valid at (0,3); it's valid, so place 2
5 3 1 | 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: Number 2 fits rules, so move forward
Step 6: Continue this process recursively, backtracking when no number fits
Final 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
Why: Backtracking ensures all possibilities are tried until solution is found
Result: 
Final solved Sudoku board:
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
Annotated Code
DSA Python
def print_board(board):
    for row in board:
        print(' '.join(str(num) if num != 0 else '_' for num in row))

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

def solve_sudoku(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1, 10):
                    if is_valid(board, row, col, num):
                        board[row][col] = num  # place num
                        if solve_sudoku(board):  # recurse
                            return True
                        board[row][col] = 0  # backtrack
                return False  # no valid number found
    return True  # solved

# Driver code
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]
]
print("Initial Sudoku board:")
print_board(board)
if solve_sudoku(board):
    print("\nSolved Sudoku board:")
    print_board(board)
else:
    print("No solution exists")
for row in range(9): for col in range(9): if board[row][col] == 0:
find next empty cell to fill
for num in range(1, 10): if is_valid(board, row, col, num):
try numbers 1 to 9 and check if valid
board[row][col] = num # place num
place number tentatively
if solve_sudoku(board): return True
recurse to solve rest of board
board[row][col] = 0 # backtrack
undo placement if leads to dead end
return False # no valid number found
trigger backtracking if no number fits
return True # solved
all cells filled correctly
OutputSuccess
Initial Sudoku board: 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 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
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) for recursion stack where n is number of empty cells
vs Alternative: Backtracking is more efficient than brute force checking all 9^81 possibilities by pruning invalid paths early
Edge Cases
Empty board (all zeros)
Solver tries many possibilities but eventually finds a valid solution or reports none
DSA Python
if board[row][col] == 0:
Board already solved
Solver quickly returns True without changes
DSA Python
return True  # solved
No valid solution exists
Solver backtracks fully and returns False
DSA Python
return False  # no valid number found
When to Use This Pattern
When you see a problem requiring filling a grid with constraints and trial/error, reach for backtracking because it tries options and undoes them if they fail.
Common Mistakes
Mistake: Not checking 3x3 box validity correctly
Fix: Calculate box start indices and check all 9 cells in the box for duplicates
Mistake: Not resetting cell to 0 when backtracking
Fix: Set board[row][col] = 0 after recursive call fails to undo placement
Mistake: Returning True too early without filling all cells
Fix: Only return True when all cells are filled (no zeros remain)
Summary
It fills empty Sudoku cells by trying numbers and backtracking on conflicts.
Use it when you need to solve puzzles with constraints by exploring possibilities.
The key insight is to try a choice, recurse, and undo if it leads to no solution.

Practice

(1/5)
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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard