Backtracking: N-Queens, subsets, permutations

What this chapter covers

Some problems can't be filled into a table or solved by a locally-best choice — you have to search the space of possibilities. Backtracking is the disciplined way to do it: build a candidate solution one choice at a time, and the instant a partial candidate can't possibly lead to a valid answer, abandon it and back up. It's depth-first search over a tree of choices with one decisive addition — pruning — that lets it skip astronomically large regions of the space without ever examining them. This chapter builds the paradigm on the N-Queens puzzle (place N queens so none attacks another), where brute force would test more candidates than there are atoms in a room but backtracking solves a 12×12 board while examining a fraction of a percent of the space. It also builds the two other canonical backtracking routines — generating all subsets and all permutations — and shows the pruning payoff: at N=12, backtracking examines nearly a million times fewer candidates than brute force.

A bit of history

The word "backtracking" was coined by D. H. Lehmer in the 1950s, but the technique is far older — it's the formalization of how anyone solves a maze or a puzzle by trial and error, systematically. The N-Queens problem itself dates to 1848, when the chess composer Max Bezzel posed the eight-queens puzzle; Gauss studied it, and it became a favorite test case for search algorithms because its structure is so clear. Backtracking's theoretical treatment matured in the 1960s and 70s: Golomb and Baumert's 1965 paper gave a general framework, and Knuth's later work (including his "Dancing Links" technique for exact-cover problems like Sudoku) refined it into an art. Its importance is that it's the general-purpose tool for constraint satisfaction — problems defined by "find an assignment satisfying these rules" — which appear everywhere from scheduling to circuit design to AI planning. Modern SAT solvers and constraint-programming systems are, at their core, very sophisticated backtracking with learned pruning; the humble try-recurse-undo of this chapter is their ancestor.

The intuition

N-Queens makes the paradigm vivid. You must place N queens on an N×N board with none attacking another — no two in the same row, column, or diagonal. The brute-force idea is to try every way to place N queens and check each for conflicts, but that's hopeless: even restricting to one queen per column, that's Nᴺ complete arrangements to generate and test. Backtracking's insight is to check as you build. Place a queen in column 0. Move to column 1 and try each row; skip any row attacked by the queen already placed (that's the prune), and place the queen on the first safe row. Move to column 2 and do the same. If you ever reach a column where every row is attacked, the partial placement is a dead end — no completion can work — so you back up to the previous column, remove its queen, and try the next safe row there. Continue until all N columns are filled (a solution) or every possibility is exhausted (no solution).

The power is that a conflict detected early kills an entire subtree. If placing a queen in column 3 conflicts, backtracking never explores any of the arrangements of columns 4 through N that would have followed — it prunes them all at once, unexamined. Brute force would have generated and tested every one. The code shape is the essence of the paradigm and recurs everywhere: try a choice, recurse to make the next choice, and undo the choice if the recursion fails. That try-recurse-undo is exactly how you generate all subsets (for each element, try including it, recurse, then try excluding it) and all permutations (for each position, try each unused element, recurse, then unpick it). Backtracking is depth-first search where the tree is the space of partial solutions and pruning cuts the branches that can't bear fruit.

Complexity: how it scales

Backtracking is, in the worst case, still exponential — it's search, and some problems (like N-Queens for large N, or SAT) have no known polynomial algorithm. But its practical cost is far below the brute-force space because pruning eliminates most of it. The face-off measures exactly that: the number of nodes backtracking actually examines against the size of the naive brute-force space (Nᴺ), as N grows:

Both lines climb — this is still exponential search — but they diverge enormously. At a 12×12 board, the brute-force space is about 8.9 trillion one-queen-per-column arrangements; backtracking examined about 10 million nodes to enumerate every solution — roughly 880,000 times fewer. That gap is entirely pruning: every time a partial placement conflicts, backtracking discards the whole subtree of completions that brute force would have generated and tested. The lesson isn't that backtracking makes the problem easy — N-Queens is genuinely hard, and the backtracking line is still exponential — it's that pruning recovers the brute force only where the problem demands it, exploring the fraction of the space that isn't obviously hopeless. For many practical constraint problems, that fraction is small enough to make an intractable search tractable.

What it's good at, what it isn't

Backtracking is the right tool for constraint-satisfaction and combinatorial-generation problems — find an assignment satisfying a set of rules, or enumerate all valid configurations. It solves puzzles and games (N-Queens, Sudoku, crosswords, peg solitaire), generates combinatorial objects (all subsets, permutations, combinations, valid parenthesizations), powers parsers and regular-expression engines (which backtrack through alternative matches), and underlies AI planning and scheduling. It's the natural approach whenever the solution is built from a sequence of choices and you can test partial solutions — because that testability is what enables pruning, and pruning is what makes backtracking beat brute force. When you can prune early and often, an exponential space becomes searchable.

Where it struggles is problems with weak pruning or enormous solution counts. If partial candidates can't be rejected until they're nearly complete, backtracking degenerates toward brute force. If the problem has overlapping subproblems (the same partial state reached many ways), backtracking re-explores them — that's dynamic programming's territory, and sometimes the two combine (memoized backtracking). And backtracking finds a solution or all solutions but gives no optimality guarantee for optimization problems without extra machinery (branch-and-bound adds bounds to prune suboptimal branches). For problems where a greedy or DP approach applies, those are far faster; backtracking is for the genuinely combinatorial search that resists them. Even then it's exponential in the worst case — it makes hard problems tractable in practice, not polynomial.

The data, or the inputs

The face-off counts the nodes backtracking examines to enumerate all N-Queens solutions against the brute-force space Nᴺ, for boards up to 12×12 — the pruning ratio. Correctness is checked hard: the solver's placement must be genuinely conflict-free for every N, the count of all solutions must match the known N-Queens sequence (1, 0, 0, 2, 10, 4, 40, 92, 352, 724 for N = 1…10), and the subset and permutation generators must exactly match Python's itertools. The animation runs backtracking on a 5×5 board, showing each attempt: a queen placed on a safe square (green), a square pruned because it's attacked (red), and a backtrack when a column runs out of safe rows (undo and retreat).

Build it, one function at a time

N-Queens — place one queen per column, prune attacked squares, undo on a dead end:

def solve_nqueens(n, trace=None):
    """Place N non-attacking queens, one per column, by backtracking. Track occupied rows and both
    diagonals (c-r and c+r are constant along the two diagonal directions) so conflict checks are
    O(1). At each column try every row; skip attacked squares (prune), place on a free one and
    recurse; if the recursion fails, UNDO the placement and try the next row. Returns (first
    solution or None, nodes_examined). `trace` optionally records every place/attack/backtrack step
    for the animation."""
    cols, diag1, diag2 = set(), set(), set()
    placement = [-1] * n
    nodes = [0]

    def place(c):
        if c == n:                               # all columns filled → a complete solution
            return True
        for r in range(n):
            nodes[0] += 1
            if r in cols or (c - r) in diag1 or (c + r) in diag2:
                if trace is not None:
                    trace.append((c, r, "attack", placement[:]))
                continue                          # pruned: this square is attacked, skip it
            placement[c] = r
            cols.add(r); diag1.add(c - r); diag2.add(c + r)
            if trace is not None:
                trace.append((c, r, "place", placement[:]))
            if place(c + 1):                      # recurse into the next column
                return True
            placement[c] = -1                     # undo — backtrack and try the next row
            cols.discard(r); diag1.discard(c - r); diag2.discard(c + r)
            if trace is not None:
                trace.append((c, r, "backtrack", placement[:]))
        return False

    found = place(0)
    return (placement[:] if found else None), nodes[0]


def count_nqueens(n):
    """Count ALL solutions (and nodes examined) — used to compare backtracking's search size against
    the brute-force space. Same algorithm, but never stops at the first solution."""
    cols, diag1, diag2 = set(), set(), set()
    total, nodes = [0], [0]

    def place(c):
        if c == n:
            total[0] += 1
            return
        for r in range(n):
            nodes[0] += 1
            if r in cols or (c - r) in diag1 or (c + r) in diag2:
                continue
            cols.add(r); diag1.add(c - r); diag2.add(c + r)
            place(c + 1)
            cols.discard(r); diag1.discard(c - r); diag2.discard(c + r)

    place(0)
    return total[0], nodes[0]

The two canonical generators — subsets and permutations, both pure try-recurse-undo:

def subsets(items):
    """All subsets, by backtracking: at each element choose to include it or not, recursing on the
    rest. 2^n subsets, built incrementally with a try-recurse-undo on the 'current' list."""
    out, cur = [], []

    def choose(i):
        if i == len(items):
            out.append(cur[:])
            return
        choose(i + 1)                            # branch 1: skip items[i]
        cur.append(items[i])                     # branch 2: include items[i]
        choose(i + 1)
        cur.pop()                                # undo

    choose(0)
    return out


def permutations(items):
    """All permutations, by backtracking: pick each unused element for the next position, recurse,
    then unpick it. n! permutations."""
    out, cur, used = [], [], [False] * len(items)

    def build():
        if len(cur) == len(items):
            out.append(cur[:])
            return
        for i in range(len(items)):
            if used[i]:
                continue
            used[i] = True
            cur.append(items[i])
            build()
            cur.pop()                            # undo
            used[i] = False

    build()
    return out

Watch it work

Here's backtracking solving the 5-Queens puzzle, placing one queen per column from left to right. A queen (♛, green) goes on the first safe row of each column. When a candidate square is attacked by an already-placed queen — same row or diagonal — it flashes red and is pruned, skipped without further thought. And when a column runs out of safe rows entirely, watch the algorithm backtrack: the orange square marks a queen being removed as the search retreats to the previous column to try a higher row. Follow the queens march across the board, occasionally backing up when they paint themselves into a corner, until all five columns hold a queen and none attacks another. Every red square is a whole branch of possibilities dismissed at a glance; every backtrack is the search admitting a dead end and trying again:

The complete code

The from-scratch tab is N-Queens (solve and count) plus the subset and permutation generators; the library tab is the brute-force space size (what pruning shrinks) and the itertools references the generators reproduce. Flip between them — itertools.permutations is what you'd use in practice, but seeing the backtracking version shows that it's the same try-recurse-undo, and that the constraint version (N-Queens) is that skeleton plus a pruning test.

"""Backtracking — search the space of possibilities by building a candidate one choice at a time,
and ABANDONING it the moment it can't lead to a solution. It's depth-first search over a tree of
choices with one crucial addition: pruning. Instead of generating every complete candidate and
testing it (brute force), backtracking checks partial candidates as it builds them and cuts off
entire branches early, so it explores a tiny fraction of the full space.

The showcase is the N-Queens puzzle: place N queens on an N×N board so none attacks another (no two
share a row, column, or diagonal). Brute force would try every way to drop N queens on the board and
check each — astronomically many. Backtracking places one queen per column, and the instant a
partial placement has a conflict it stops extending that branch and backs up. The same shape solves
Sudoku, generates all subsets and permutations, and searches any space of incremental choices: try a
choice, recurse, and undo it if it fails ("try — recurse — undo"). Pruning is what turns an
intractable search into a fast one.
"""


# region: nqueens
def solve_nqueens(n, trace=None):
    """Place N non-attacking queens, one per column, by backtracking. Track occupied rows and both
    diagonals (c-r and c+r are constant along the two diagonal directions) so conflict checks are
    O(1). At each column try every row; skip attacked squares (prune), place on a free one and
    recurse; if the recursion fails, UNDO the placement and try the next row. Returns (first
    solution or None, nodes_examined). `trace` optionally records every place/attack/backtrack step
    for the animation."""
    cols, diag1, diag2 = set(), set(), set()
    placement = [-1] * n
    nodes = [0]

    def place(c):
        if c == n:                               # all columns filled → a complete solution
            return True
        for r in range(n):
            nodes[0] += 1
            if r in cols or (c - r) in diag1 or (c + r) in diag2:
                if trace is not None:
                    trace.append((c, r, "attack", placement[:]))
                continue                          # pruned: this square is attacked, skip it
            placement[c] = r
            cols.add(r); diag1.add(c - r); diag2.add(c + r)
            if trace is not None:
                trace.append((c, r, "place", placement[:]))
            if place(c + 1):                      # recurse into the next column
                return True
            placement[c] = -1                     # undo — backtrack and try the next row
            cols.discard(r); diag1.discard(c - r); diag2.discard(c + r)
            if trace is not None:
                trace.append((c, r, "backtrack", placement[:]))
        return False

    found = place(0)
    return (placement[:] if found else None), nodes[0]


def count_nqueens(n):
    """Count ALL solutions (and nodes examined) — used to compare backtracking's search size against
    the brute-force space. Same algorithm, but never stops at the first solution."""
    cols, diag1, diag2 = set(), set(), set()
    total, nodes = [0], [0]

    def place(c):
        if c == n:
            total[0] += 1
            return
        for r in range(n):
            nodes[0] += 1
            if r in cols or (c - r) in diag1 or (c + r) in diag2:
                continue
            cols.add(r); diag1.add(c - r); diag2.add(c + r)
            place(c + 1)
            cols.discard(r); diag1.discard(c - r); diag2.discard(c + r)

    place(0)
    return total[0], nodes[0]
# endregion


# region: subsets_perms
def subsets(items):
    """All subsets, by backtracking: at each element choose to include it or not, recursing on the
    rest. 2^n subsets, built incrementally with a try-recurse-undo on the 'current' list."""
    out, cur = [], []

    def choose(i):
        if i == len(items):
            out.append(cur[:])
            return
        choose(i + 1)                            # branch 1: skip items[i]
        cur.append(items[i])                     # branch 2: include items[i]
        choose(i + 1)
        cur.pop()                                # undo

    choose(0)
    return out


def permutations(items):
    """All permutations, by backtracking: pick each unused element for the next position, recurse,
    then unpick it. n! permutations."""
    out, cur, used = [], [], [False] * len(items)

    def build():
        if len(cur) == len(items):
            out.append(cur[:])
            return
        for i in range(len(items)):
            if used[i]:
                continue
            used[i] = True
            cur.append(items[i])
            build()
            cur.pop()                            # undo
            used[i] = False

    build()
    return out
# endregion

"""The contrast and the reference. Two things:

- `brute_force_nqueens_space` reports the size of the naive search space — every way to place one
  queen per column with NO pruning, which is n^n complete candidates to generate and test. It's the
  baseline backtracking's pruning shrinks; we compute its size rather than actually enumerate it
  (n^n is astronomically large).
- Python's `itertools` provides the standard-library generators that backtracking reproduces:
  `itertools.permutations`, `itertools.combinations`, `product`. They're the correctness reference
  for the subset/permutation builders (and what you'd actually use for those).

    from itertools import permutations, combinations
    list(permutations(items))                 # all n! orderings
    [c for r in range(len(items)+1) for c in combinations(items, r)]   # all subsets
"""
from itertools import combinations, permutations as iperms


# region: bruteforce
def brute_force_nqueens_space(n):
    """The number of complete candidates a no-pruning brute force would generate: one row choice per
    column, independently, = n^n. Backtracking examines far fewer NODES because it prunes attacked
    partial placements before completing them."""
    return n ** n
# endregion


# region: references
def all_permutations(items):
    """itertools reference for the permutation builder."""
    return [list(p) for p in iperms(items)]


def all_subsets(items):
    """itertools reference for the subset builder (every size of combination)."""
    out = []
    for r in range(len(items) + 1):
        out.extend(list(c) for c in combinations(items, r))
    return out
# endregion

Scratch vs library

Backtracking's lesson is that pruning is the algorithm. The skeleton — try, recurse, undo — is trivial and identical across N-Queens, subsets, and permutations; what makes N-Queens tractable where brute force is hopeless is the one extra line that rejects an attacked square before recursing. The face-off's 880,000-fold gap is entirely that line. This reframes how to approach a combinatorial search: don't ask "how do I generate all candidates," ask "how early can I detect that a partial candidate is doomed," because every early rejection prunes an exponential subtree. It's the same insight that scales all the way to industrial SAT and constraint-programming solvers — they're this chapter's skeleton with progressively smarter pruning (propagation, clause learning) and variable ordering. And it connects to the other paradigms: backtracking is divide-and-conquer's recursion without the independence (branches share the growing partial state), and it meets dynamic programming when partial states overlap (memoized backtracking). For pure generation you'd use itertools; building N-Queens yourself is what makes "pruning turns an intractable search tractable" a number you've measured, not a claim.

Where you'll actually meet it

Backtracking runs wherever a solution is searched for among combinatorial possibilities. Constraint solvers and SAT solvers — behind hardware verification, software model-checking, scheduling, and automated planning — are backtracking with sophisticated pruning. Sudoku, crossword, and puzzle solvers are direct applications. Regular- expression engines (the backtracking kind, like Perl's and Python's re) match by trying alternatives and backing up — which is also why pathological regexes can blow up exponentially. Parsers for ambiguous grammars backtrack through parse alternatives. Compilers use it in register allocation and instruction scheduling. Combinatorial generation — enumerating permutations, combinations, partitions, valid configurations — is backtracking, as is much of AI game-playing (minimax is a backtracking search over game trees). Theorem provers, type inference, and program synthesis all search with it. Anywhere the task is "find (or enumerate) assignments satisfying constraints," backtracking, plus good pruning, is the engine.

Takeaways

Backtracking searches a space of possibilities by building candidates one choice at a time and pruning — abandoning a partial candidate the instant it can't lead to a solution — a depth-first "try, recurse, undo" over the tree of choices. Pruning is what distinguishes it from brute force and what makes it powerful: a conflict detected early discards an entire exponential subtree unexamined, letting backtracking solve N-Queens while examining 880,000× fewer candidates than brute force at N=12. It remains exponential in the worst case — it makes hard search tractable in practice, not polynomial — and its speed lives entirely in how early and cleverly you can prune, the design dimension that scales it up to modern constraint and SAT solvers.

The paradigms tier has two chapters left, both on a different kind of cleverness — not searching a space but exploiting structure to avoid recomputation. The two-pointer and sliding-window techniques (next) turn many O(n²) scans into O(n) single passes by maintaining a moving window's state incrementally, the same "reuse what you computed" spirit as the rolling hash. Then binary search on the answer applies binary search not to an array but to the space of possible answers, solving optimization problems by repeatedly asking a yes/no feasibility question.