Backtracking: choose, explore, un-choose

You are in a hedge maze with no map. At each junction you pick a path you haven't tried and walk on. At a dead end you don't go back to the entrance: you retrace your steps to the most recent junction with an untried path, and take it. Remember what you have tried and you never explore the same dead end twice.

Backtracking builds answers the same way. Make one choice, carry on, and when that branch is finished, with an answer or at a dead end, undo the choice and try the next. That lists every subset or ordering of a few items, places queens on a chessboard and fills in a Sudoku. Each choice is a recursive call, and undoing it is the walk back to the junction.

partial solution

The choices made so far: cur in the subset and ordering visualisers, path in the code, the board in N-Queens.

choose, explore, un-choose

Add a choice, recurse to make the rest, then remove it so the next choice starts from the same state.

decision tree

The calls drawn as a tree: each edge is one choice, and each leaf a complete answer or a dead end.

dead end

A partial solution with no valid next choice: the search backs up to the latest choice with options left.

pruning

Abandoning a partial solution as soon as it breaks a rule, so nothing below it is ever built.

Here is every subset of a, b and c. Each level of the tree decides one item: take it (+) or leave it out (−), and the search always tries taking first. The cur row holds the partial solution, and a call that has decided all three items records it.

Watch cur on the un-choose steps: a call that has finished its take branch pops the item it pushed, so the leave-it-out branch starts from cur exactly as the call found it. The search is depth first: all of take-a is done before a is ever left out. Each item doubles the leaves, so n items give 2ⁿ subsets.

Orderings make a wider tree. Position 1 can hold any of the n items, position 2 any of the n − 1 still unused, and so on down to 1, so there are n × (n − 1) × … × 1 = n! leaves. The step is the same: choose an unused item (mark it used and push it), explore, then un-choose it (pop it and free it) and try the next.

n! soon outgrows 2ⁿ: 4 items have 16 subsets but 24 orders, and 10 items have 1,024 subsets but 3,628,800 orders.

This is not memoization: each call here carries a different partial solution, so no question comes back for a memo to answer. When the same smaller problem does come back, as in counting the subsets with a given total instead of listing them, use dynamic programming.

Four items now, a to d. Before each leaf, predict which subset is recorded; after it, predict which choice is undone next. Climb back to the nearest call that took its item: a call that left its item out has nothing to pop, so it just returns.

Here is the subset search in code, on just a and b to keep the trace short. A call that has decided every item prints path; any other call appends items[i], recurses, pops it, and recurses again without it.

def subsets(items, i, path):
    if i == len(items):
        print('{' + ', '.join(path) + '}')
        return
    path.append(items[i])
    subsets(items, i + 1, path)
    path.pop()
    subsets(items, i + 1, path)

letters = ['a', 'b']
path = []
subsets(letters, 0, path)

Each call's frame has its own i, but every path arrow points at one list: passing a list passes a reference, as the recursion lesson showed. Nothing but the pop puts it back. Try it: delete the path.pop() line and run again, or add 'c' to letters and watch 8 subsets come out.

Sharing one list also catches out code that saves its answers instead of printing them.

In subsets and orderings every leaf is an answer. Most searches aren't like that. Put 4 queens on a 4 × 4 board so that no two share a row, column or diagonal: of the 4⁴ = 256 boards with one queen per row, only 2 work. A backtracking solver checks each square before it puts a queen there and rejects any square an earlier queen attacks, so no board that starts that way is ever built. That is pruning.

On the 8 × 8 board, with 8⁸ = 16,777,216 one-per-row boards, the first solution takes 113 placements and 105 backtracks.

Sudoku works the same way: write the smallest digit that fits the first empty cell's row, column and box, and recurse. When a later cell has no digit left, come back, erase and try the next digit up.

Pruning is why these finish in a blink. Don't read too much into that.

• Backtracking builds an answer one choice at a time: choose, explore by recursing, then un-choose, so the next choice starts from the same state. The calls form a decision tree, explored depth first.
• Subsets take or leave each item: 2ⁿ leaves. Orderings fill each position from the unused items: n! leaves.
• One working list serves the whole search. A return doesn't undo a choice: pop it (and unmark it). Save a complete answer as a copy, never the list itself.
• Pruning rejects a partial solution as soon as it breaks a rule, with its whole subtree: 4 queens take 8 placements, not 256 boards. The worst case stays exponential.
• Next: breadth-first and depth-first search, where depth-first search backtracks through a graph. Practise with All Subsets, All Orderings, Combinations That Add Up and Find a Word in a Letter Grid, or try bigger boards in the N-Queens and Sudoku visualisers.