Backtracking

What you'll learn

Backtracking builds a solution incrementally and abandons a partial candidate the instant it can't possibly work — then backs up and tries something else. It's systematic brute force with early exits, and it solves puzzles that look impossibly large.

By the end you'll be able to:

• Apply the choose / explore / un-choose template
• Generate all subsets and permutations
• Solve N-Queens and understand pruning

The template

Every backtracking algorithm has the same three-beat rhythm: choose an option, explore recursively, then un-choose to restore state before trying the next option. The un-choose step is what makes it "backtracking":

def backtrack(state):
    if is_complete(state):
        record(state)
        return
    for choice in choices(state):
        if is_valid(choice, state):
            make(choice, state)      # choose
            backtrack(state)         # explore
            undo(choice, state)      # un-choose (backtrack)

Subsets & permutations

The simplest instances just enumerate. For subsets, at each element choose to include it or not. For permutations, at each position choose an unused element. Both build a partial answer, recurse, and undo — generating all 2ⁿ subsets or n! permutations respectively.

N-Queens

Place n queens on an n×n board so none attack another. Backtracking places one queen per row, trying each column; if a column is attacked it's pruned immediately, and if a whole row has no safe column it backtracks. Step through the search on a 4×4 board — watch it try, place, hit conflicts, and back up until it lands a solution:

N-Queens in code

def solve_n_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    board, solutions = [], []
    def place(r):
        if r == n:
            solutions.append(board[:]); return
        for c in range(n):
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue                       # pruned: attacked
            cols.add(c); diag1.add(r - c); diag2.add(r + c); board.append(c)
            place(r + 1)                        # explore
            cols.discard(c); diag1.discard(r - c); diag2.discard(r + c); board.pop()  # undo
    place(0)
    return solutions

Pruning

The power of backtracking is pruning — cutting off whole branches the moment they become hopeless. Naively, 4-Queens has 4⁴ = 256 placements; pruning attacked squares explores only a handful. The tighter your validity check, the more of the search tree you skip. Sudoku is the same idea: fill the next empty cell with each legal digit, recurse, and undo on failure.

Recap & quick check

Backtracking finds any valid solution. To find the best one efficiently, we add bounds. Next up: Module 22 — Branch & Bound and Pruning.