The Quest Begins (The "Why")
I still remember the first time I stared at a Sudoku puzzle in a coffee shop, pencil trembling, convinced I’d never crack it. I kept guessing numbers, erasing, guessing again—like a character stuck in a time loop, hoping the next try would be the lucky one. After an hour of frustration, I muttered to myself, “There has to be a smarter way.” That moment sparked a mini‑obsession: I wanted an algorithm that could systematically explore possibilities without getting lost in endless trial‑and‑error.
Around the same time, a friend threw the classic N‑Queens problem at me during a mock interview: place N queens on an N×N board so none attack each other. My naive solution? Generate every permutation and test it—obviously exponential and useless for N > 8. I felt like I was trying to defeat a final boss in Dark Souls with a wooden sword: possible, but painful and slow.
Both puzzles shared a hidden structure: you make a choice, move forward, and if you hit a dead end you backtrack to the last decision and try a different path. That insight turned my coffee‑shop despair into a coding victory. Let’s walk through why backtracking works, how to wield it, and what it means for your next interview.
The Revelation (The Insight)
At its core, backtracking is depth‑first search with a prune‑as‑you‑go strategy. Instead of generating the entire solution space up front, you build a partial solution step by step. After each step you ask: Can this partial solution still lead to a valid answer? If the answer is no, you undo the last step (backtrack) and try the next alternative. If it’s yes, you keep going.
Why does this prune so effectively? Because many constraints are local. In Sudoku, placing a ‘5’ in a cell instantly eliminates that digit from its row, column, and 3×3 box. If any of those units already contains a ‘5’, the placement is invalid and we can abandon that branch immediately—no need to explore the thousands of completions that would inevitably fail. In N‑Queens, putting a queen on a square eliminates its entire row, column, and two diagonals. As soon as a conflict appears, we backtrack.
The magic is that each recursive call does only constant‑time work to check validity (if we maintain sets or bit‑masks for rows, columns, boxes, and diagonals). The overall complexity is therefore proportional to the number of visited nodes in the search tree, not to the size of the full permutation space. In practice, the pruning cuts the tree dramatically, turning an infeasible brute force into something that solves a 9×9 Sudoku in milliseconds.
Think of it like exploring a maze: you keep walking forward, marking your path. When you hit a wall, you retreat to the last junction and try another corridor. You never need to draw the whole maze beforehand—you discover it as you go.
Wielding the Power (Code & Examples)
The Struggle: Naïve Brute Force
First, let’s see what not to do. Here’s a straightforward but terrible Sudoku solver that tries every combination:
def solve_sudoku_brute(board):
empty = find_empty(board)
if not empty:
return True # solved
r, c = empty
for num in range(1, 10):
board[r][c] = num
if is_valid(board, r, c): # O(N) scan each time → slow
if solve_sudoku_brute(board):
return True
board[r][c] = 0 # undo
return False
The is_valid function scans the whole row, column, and box each call—O(N) where N=9—so the already exponential search gets an extra multiplicative factor. For larger boards (think 16×16 Sudoku) this crawls to a halt.
The Victory: Pruned Backtracking with O(1) Checks
Now we maintain three arrays of sets (or bit‑masks) that tell us which digits are already used in each row, column, and box. Checking a placement becomes O(1).
def solve_sudoku(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
# init with given numbers
for r in range(9):
for c in range(9):
val = board[r][c]
if val:
rows[r].add(val)
cols[c].add(val)
boxes[(r//3)*3 + c//3].add(val)
def backtrack():
# find next empty cell (simple linear scan)
for r in range(9):
for c in range(9):
if board[r][c] == 0:
for num in range(1, 10):
b_idx = (r//3)*3 + c//3
if num not in rows[r] and num not in cols[c] and num not in boxes[b_idx]:
# place
board[r][c] = num
rows[r].add(num)
cols[c].add(num)
boxes[b_idx].add(num)
if backtrack():
return True
# undo
board[r][c] = 0
rows[r].remove(num)
cols[c].remove(num)
boxes[b_idx].remove(num)
return False # trigger backtracking
return True # no empty cells → solved
backtrack()
return board
What changed?
- We replaced the costly
is_validscan with three set look‑ups → O(1). - The recursion depth is at most 81 (the number of cells). Each level tries at most 9 numbers, but most branches die early thanks to the set checks.
- The algorithm now solves typical Sudoku puzzles in under a second on a laptop.
N‑Queens: Same Pattern, Different Board
The N‑Queens problem follows the exact same template. We keep three boolean arrays: one for columns, and two for the diagonals (identified by r + c and r - c).
def solve_n_queens(n):
cols = [False] * n
diag1 = [False] * (2 * n - 1) # r + c
diag2 = [False] * (2 * n - 1) # r - c + n-1
board = [-1] * n # board[row] = col of queen
solutions = []
def backtrack(r):
if r == n:
solutions.append(board.copy())
return
for c in range(n):
d1 = r + c
d2 = r - c + n - 1
if not (cols[c] or diag1[d1] or diag2[d2]):
# place queen
board[r] = c
cols[c] = diag1[d1] = diag2[d2] = True
backtrack(r + 1)
# remove queen
board[r] = -1
cols[c] = diag1[d1] = diag2[d2] = False
backtrack(0)
return solutions
Running solve_n_queens(8) yields the 92 classic solutions instantly. For n = 14 it still finishes in a few seconds—far better than the O(n!) brute force that would be impossible.
Common Traps to Avoid
- Forgetting to undo state – If you neglect to remove a number from the row/col/box sets (or reset the board cell), the recursion will pollute later branches and you’ll miss solutions or get stuck in an infinite loop.
- Scanning for validity each call – As shown, this adds an unnecessary O(N) factor and kills performance on larger instances. Pre‑computing or maintaining auxiliary structures is the key.
- Choosing a poor variable ordering – Picking the next empty cell arbitrarily works, but selecting the cell with the fewest legal options (minimum remaining values heuristic) drastically cuts the search tree. It’s a simple upgrade worth knowing for interviews.
Why This New Power Matters
Mastering backtracking gives you a universal toolkit for constraint‑satisfaction problems: Sudoku, N‑Queens, word search, graph coloring, even certain scheduling puzzles. Interviewers love these because they test recursion, state management, and the ability to reason about pruning—all signals of strong algorithmic thinking.
Beyond interviews, you’ll start seeing backtracking everywhere: configuring feature toggles, solving crossword puzzles in games, or even generating mazes for procedural content. The pattern is simple—choose, validate, recurse, undo—but its impact is huge when you apply it correctly.
You’ve now got a spell that turns seemingly impossible search spaces into manageable adventures. Go forth and tackle those puzzles with confidence!
Your Turn
Here’s a challenge: modify the Sudoku solver to use the minimum remaining values heuristic (pick the empty cell with the fewest possible digits) and watch how the solving speed changes on a tough puzzle. Or, try solving N‑Queens for n = 15 and count how many solutions you find—share your time in the comments!
Happy backtracking, and may your recursion depth always be just right! 🚀
Top comments (0)