Advanced Topics8 min read

Backtracking

Explore every path, retreat the moment you hit a dead end
worst case:\(O(b^d)\) — branching factor to the depthwith pruning:Problem-specific, often dramatically lesspattern:Choose → Explore → Undo

Think of solving a maze. You walk down a corridor, turn left, walk some more, and hit a wall. You don't give up — you backtrack to the last junction and try the next corridor. You keep doing this, systematically, until you either find the exit or confirm there isn't one.

That's backtracking in a nutshell: build a solution one piece at a time, and the moment a partial solution violates a rule, abandon the whole branch and try something different. No need to explore what's downstream of a dead end.

The three-step heartbeat

Every backtracking algorithm beats to the same rhythm:

1. Choose — pick a candidate value for the current slot (a queen's column, a Sudoku digit, the next item to include).

2. Explore — if the choice doesn't break any constraints, recurse into the next slot.

3. Undo — after the recursion returns (whether it found a solution or hit a dead end), un-make the choice and try the next candidate. This restore step is what gives backtracking its name.

The "undo" is crucial. Without it, choices from one branch would leak into the next, corrupting the search.

N-Queens — a classic example

Place n queens on an n×n chessboard so no two attack each other. The trick: place queens row by row. At row r, try each column c. If no previously placed queen shares column c, the left diagonal, or the right diagonal — place the queen and recurse to row r+1. When you return, remove the queen and try column c+1.

For n=8 there are \(8^8\) ≈ 16 million raw combinations, but with pruning the algorithm visits only around 15,000 nodes — a 1000× speedup.

Sudoku

For each empty cell, try digits 1–9. Skip any digit already present in the same row, column, or 3×3 box. If a digit is consistent, fill it in and recurse to the next empty cell. If no digit works, return false and let the caller backtrack.

Add constraint propagation — after placing a digit, immediately remove it as a candidate from every peer cell — and most Sudoku puzzles solve with fewer than ten backtracks total.

Permutations and subsets

Backtracking is essentially depth-first search on a decision tree built on the fly. It naturally generates all permutations (at each position, try each unused element, mark it used, recurse, unmark) and all subsets (at each element, branch on include-or-skip). Pruning conditions like "running sum already exceeds target" cut off entire branches early.

The Choose → Explore → Undo heartbeat that drives every backtracking algorithm
Note: The 'undo' step is what lets you reuse the same mutable state across all branches without ever copying it. Without it, choices from one branch leak into the next.

N-Queens — all solutions

def solve_n_queens(n):
    solutions = []
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col
    board = [-1] * n


    def backtrack(row):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if col in cols or (row-col) in diag1 or (row+col) in diag2:
                continue
            # Choose
            board[row] = col
            cols.add(col); diag1.add(row-col); diag2.add(row+col)
            # Explore
            backtrack(row + 1)
            # Undo
            cols.remove(col); diag1.remove(row-col); diag2.remove(row+col)


    backtrack(0)
    return solutions


sols = solve_n_queens(8)
print(f"{len(sols)} solutions for 8-Queens")
print("First solution (column per row):", sols[0])
Output
92 solutions for 8-Queens
First solution (column per row): [0, 4, 7, 5, 2, 6, 1, 3]

Complexity

🌳 Worst case (no pruning)b = branching factor, d = depth; for N-Queens: up to n^n without pruning
Every combination explored\(O(b^d)\)
✂️ With constraint pruning8-Queens: ~15,000 nodes visited vs 16M without pruning — 1000× faster
Branches cut at first violationProblem-specific
🔮 With constraint propagationLookahead detects empty-candidate cells before wasting recursive calls
Dead ends detected before recursingNear-instant for most Sudoku
📚 Stack spaceOnly the current path is kept in memory — not the entire search tree
One frame per level\(O(d)\)

Quick check

What's the key difference between backtracking and plain brute-force search?

Continue reading

Branch & Bound
Backtracking with a crystal ball — prune branches that can't possibly win
→
DP Pattern
Never solve the same puzzle piece twice — write it down and look it up next time
→