Introduction
Sudoku is a constraint satisfaction puzzle: fill a 9x9 grid, partially pre-filled, with digits 1-9 such that every row, every column, and every 3x3 sub-box contains each digit exactly once. Backtracking solves Sudoku naturally by scanning for the next empty cell, trying each digit that does not currently conflict with the row, column, or box, recursing, and undoing the assignment if no digit leads to a complete solution.
Cricket analogy: Filling a partially set fixture calendar so no ground, no time slot, and no team repeats within any week is a constraint-satisfaction puzzle much like Sudoku, and backtracking solves it by trying each candidate slot, recursing, and undoing it if it leads to a dead end.
Approach/Syntax
def solve_sudoku(board):
"""board: 9x9 list of lists, 0 represents an empty cell. Solved in place."""
def find_empty():
for r in range(9):
for c in range(9):
if board[r][c] == 0:
return r, c
return None
def is_valid(r, c, val):
if any(board[r][cc] == val for cc in range(9)):
return False
if any(board[rr][c] == val for rr in range(9)):
return False
box_r, box_c = 3 * (r // 3), 3 * (c // 3)
for rr in range(box_r, box_r + 3):
for cc in range(box_c, box_c + 3):
if board[rr][cc] == val:
return False
return True
def backtrack():
empty = find_empty()
if empty is None:
return True # solved
r, c = empty
for val in range(1, 10):
if is_valid(r, c, val):
board[r][c] = val # choose
if backtrack(): # explore
return True
board[r][c] = 0 # un-choose
return False # trigger backtracking to previous cell
backtrack()
return board
Explanation
find_empty locates the next unfilled cell in row-major order, and is_valid enforces the three Sudoku constraints (row, column, 3x3 box) before a digit is ever placed -- this is the pruning step, since it rejects an obviously conflicting digit without any recursion. When a digit passes validation, it is chosen (written into the board) and the algorithm explores by recursing on the rest of the board; if that recursive call ever returns False, meaning no digit choice deeper in the grid led to a solution, the current digit is un-chosen (reset to 0) and the loop tries the next candidate digit. The function returns True as soon as find_empty reports no empty cells remain, which propagates back up the call stack and stops further backtracking.
Cricket analogy: Scanning for the next unfilled fixture slot and checking it against the round, ground, and pool constraints before booking a team is the pruning step; if a deep recursive booking later fails, the current team is un-booked and the next candidate is tried until a full valid calendar is found.
Example
puzzle = [
[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],
]
solved = solve_sudoku(puzzle)
for row in solved:
print(row)
Complexity
In the absolute worst case, with up to 9 candidate digits tried per empty cell and up to 81 cells, the search space is bounded by O(9^(number of empty cells)), which is exponential -- there is no polynomial-time bound known for general Sudoku solving via backtracking. However, the row/column/box validity checks prune the vast majority of branches almost immediately, so well-constrained puzzles (typical human-solvable Sudoku) solve in a fraction of a second in practice. Space complexity is O(1) extra beyond the board itself, aside from the recursion stack which is bounded by the number of empty cells (at most 81).
Cricket analogy: With up to 9 possible teams tried per unfilled fixture slot across dozens of slots, the raw search space is exponential, but validity checks on ground, round, and pool constraints prune most branches immediately, so a well-formed calendar still resolves in a fraction of a second.
Key Takeaways
- Sudoku backtracking fills the next empty cell, tries digits 1-9, and prunes with row/column/box checks.
- is_valid is the pruning function; it must check all three constraint groups before a digit is placed.
- Un-choosing resets a cell to 0 when no digit at a deeper cell leads to a full solution.
- Worst-case complexity is exponential (O(9^empty cells)), but constraint pruning makes real puzzles fast.
- Returning True as soon as no empty cells remain short-circuits the entire remaining search.
Practice what you learned
1. What three constraints must be checked before placing a digit in a Sudoku backtracking solver?
2. In the sample sudoku solver, what does it mean when the recursive backtrack() call returns False for a given digit choice?
3. What is the worst-case time complexity class of a plain backtracking Sudoku solver?
4. Why does the solver call find_empty() to scan in row-major order rather than picking a random empty cell?
Was this page helpful?
You May Also Like
The Backtracking Paradigm
Learn how backtracking systematically builds candidate solutions and abandons paths that cannot possibly succeed.
N-Queens Problem
Place N queens on an N×N chessboard so none attack each other, using backtracking with column, diagonal pruning.
Generating Permutations and Combinations
Use backtracking to enumerate all permutations and combinations of a collection systematically.