Backtracking is a systematic approach to solving constraint satisfaction problems by incrementally building solutions and abandoning partial solutions that cannot lead to a complete answer.
The core idea is simple: try a choice, recursively explore where it leads, and if it doesn't work out, undo that choice and try the next one. This "try, recurse, undo" pattern makes backtracking incredibly powerful for problems with complex constraints.
Backtracking follows a depth-first search pattern through the solution space. At each step, you:
The key insight is that backtracking prunes large portions of the search space early when constraints are violated, making it much more efficient than brute force.
Effective backtracking requires careful state management. You need to:
Using sets or hash tables to track conflicts (like occupied columns or diagonals) makes constraint checking O(1) instead of scanning the entire state.
Backtracking excels at:
The technique works best when you can detect invalid partial solutions early and when the constraint structure allows significant pruning of the search space.
1def solve_sudoku(board):
2 def is_valid(board, row, col, num):
3 # Check row constraint
4 for c in range(9):
5 if board[row][c] == num:
6 return False
7
8 # Check column constraint
9 for r in range(9):
10 if board[r][col] == num:
11 return False
12
13 # Check 3x3 box constraint
14 box_row, box_col = 3 * (row // 3), 3 * (col // 3)
15 for r in range(box_row, box_row + 3):
16 for c in range(box_col, box_col + 3):
17 if board[r][c] == num:
18 return False
19 return True
20
21 def backtrack():
22 for row in range(9):
23 for col in range(9):
24 if board[row][col] == 0: # Empty cell
25 for num in range(1, 10): # Try digits 1-9
26 if is_valid(board, row, col, num):
27 board[row][col] = num # Make choice
28 if backtrack(): # Recurse
29 return True
30 board[row][col] = 0 # Backtrack
31 return False
32 return True # All cells filled
33
34 return backtrack()