Backtracking search with pruning

Some problems ask you to find every arrangement that satisfies a set of constraints, or to find just one. Backtracking builds a solution one piece at a time, trying each available choice, and undoes a choice the moment it stops being possible to finish.

Building solutions step by step

At each step you try every choice that is still available. Make one, move to the next step, and if you ever reach a dead end, undo the last choice and try a different one. This is exactly what recursion is built for: each call represents one partial solution, and returning from a call is the undo.

Example: permutations

The simplest backtracking problem has no constraints to check at all: generate every permutation of [1, 2, 3].

At each level of the recursion, pick an element that has not been used yet and append it to the permutation being built. Once the permutation holds every element, record it. Then remove that last element before trying the next candidate, so the next branch starts from a clean list.

That removal step matters because the list is shared and mutated in place. Build [1, 2, 3] and record it, and the list still holds [1, 2, 3] until you pop the 3 back off. Skip the pop, and the next branch inherits values it never chose.

1def permutations(elements):2    result = []3    4    def backtrack(current, remaining):5        if not remaining:6            result.append(current[:])7            return8        for i in range(len(remaining)):9            current.append(remaining[i])10            backtrack(current, remaining[:i] + remaining[i+1:])11            current.pop()12    13    backtrack([], elements)14    return result15
16
17perms = permutations([1, 2, 3])18for p in perms:19    print(p)

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Three elements give 3! = 6 permutations, matching the six lines printed. There is nothing to prune here, since every arrangement of a permutation is valid; the recursion just needs to visit each one once. Problems with real constraints are where pruning starts to matter.

Pruning the search space

Pruning means noticing early that a partial solution cannot possibly finish successfully, and skipping the rest of that branch entirely.

The n-queens problem asks for every way to place n queens on an n×n board so that no two attack each other, where queens attack along a shared row, column or diagonal. Placing one queen per row and trying all n columns for each row gives n^n raw possibilities. For 8 queens that is 8^8, about 16 million placements to check with no pruning at all.

Placing the queens row by row lets you prune as you go. Once a queen sits in a row, track which columns and which diagonals it now attacks. When you try to place the next queen, skip any column or diagonal already marked, instead of placing the queen and discovering the conflict afterward. Most of the n^n possibilities are eliminated before they are ever built.

1def solve_n_queens(n):2    result = []3    cols = set()4    diag1 = set()5    diag2 = set()6    7    def backtrack(row, board):8        if row == n:9            result.append([row[:] for row in board])10            return11        for col in range(n):12            if col in cols or (row - col) in diag1 or (row + col) in diag2:13                continue14            board[row][col] = 115            cols.add(col)16            diag1.add(row - col)17            diag2.add(row + col)18            19            backtrack(row + 1, board)20            21            board[row][col] = 022            cols.remove(col)23            diag1.remove(row - col)24            diag2.remove(row + col)25    26    board = [[0] * n for _ in range(n)]27    backtrack(0, board)28    return len(result)29
30
31print(solve_n_queens(4))32print(solve_n_queens(8))

2
92

The program counts 2 valid boards for 4 queens and 92 for 8 queens. Both numbers come from the well-known n-queens counts, and both are reached without ever constructing an attacking arrangement in full, since the column and diagonal checks reject a queen the moment it would conflict.

Recursion depth

Backtracking leans on recursion, and Python limits how deep a call chain can go, usually to around 1,000 frames. A search with a very long chain of choices can hit that limit before it hits the answer.

Raising the limit with sys.setrecursionlimit() buys some room, but it does not remove the problem, only postpones it, and a deep enough chain can still exhaust the real call stack underneath. When the depth genuinely cannot be bounded, an iterative version that keeps its own explicit stack, instead of relying on Python's call stack, sidesteps the limit entirely, at the cost of more code to write.

Subsets and combinations

Backtracking also generates subsets, not just full arrangements. To list every subset of [1, 2, 3], walk the elements in order and, at each one, branch into two choices: include it in the subset being built, or leave it out. Recording the subset happens at every level of the recursion, not only at the end, since a partial subset is already a complete answer on its own. Three elements give 2^3 = 8 subsets, one for each of the eight yes/no combinations of the three include-or-not decisions.

A combination, "choose k of n elements", is the same include/exclude recursion with one extra piece of pruning: stop a branch as soon as too few elements remain to reach k choices, since no amount of further searching can save it. That single check turns an exponential subset search into one that only visits branches that could possibly reach exactly k picks, which is usually a much smaller set than every subset.

Getting these right

The choice you make has to be undone once its branch is done exploring, or the next branch inherits state it never earned. In the permutations example, skipping the pop after a recorded permutation leaves a stale value sitting in the list for the next candidate to build on top of.

A pruning rule also has to be exactly right, not just fast. It must rule out only the branches that truly cannot lead to a solution. In n-queens, checking rows and columns but forgetting the diagonals lets attacking placements through, and the count comes out wrong.

Check constraints as you build, not after the fact. Building a complete arrangement and validating it at the end wastes all the work spent on a branch that was already doomed a few choices earlier; checking at each step prunes that branch immediately instead.

And every recursive search still needs a clear stopping point. Permutations stop once the permutation is full; n-queens stops once every row holds a queen. Without that base case, the recursion has no way to know it is finished.