Backtracking and Search

Some problems have no clever formula, only a huge space of candidate answers and a rule for checking one: fill in a sudoku, build a school timetable, pick package versions that all agree with each other. Backtracking builds an answer one choice at a time, undoes the latest choice the moment a rule breaks, and in doing so discards whole regions of the space without ever visiting them.

Everything backtracking gains comes from that discarding. It is the difference between a space of about 5 followed by 47 zeros and a search that finishes in a fraction of a second. It is also why backtracking has no guarantee: the same search that finishes instantly on one input can run for longer than anyone will wait on another.

The Search Tree

Picture the choices as a tree. The root is the empty grid. Each branch fills one cell with one digit, so a node's nine children are the digits 1 to 9 in the next blank cell, and each complete path from the root to a leaf is one candidate filling. A sudoku with 50 blank cells has 9 to the power 50 complete fillings, a 48-digit number, about 5 followed by 47 zeros.

The figure draws only the top three levels, following one branch down: 9 paths after one cell, 81 after two, 729 after three. No computer will ever list all the leaves, so "try every filling and check it" is not a plan. It is the definition of the problem.

Try, Fail, Undo

Backtracking walks this tree without building it. Make a choice, check every rule that can already be checked, and if one breaks, undo the choice and try the next. When a cell has no legal digit left, back up to the previous cell and change its digit instead. This is the depth-first search of Chapter 8 over a tree generated on demand, the kind of graph that is never stored, and it holds in memory only the current path: at most 50 choices deep.

def solve(grid):
    cell = next_empty(grid)
    if cell is None:
        return True                    # every cell filled: a solution
    for digit in legal_digits(grid, cell):
        grid[cell] = digit             # try
        if solve(grid):
            return True
        grid[cell] = 0                  # undo
    return False                       # nothing fits: back up

The function above picks the next empty cell, and if there is none the grid is solved. Otherwise it tries each digit that breaks no rule, recurses, and on failure clears the cell before trying the next digit. If no digit works, it returns false, and its caller undoes its own choice. Try, check, undo, back up: every backtracking search, from sudoku to version resolution, has this shape.

Pruning

Checking early is where the savings come from. A digit that repeats in its row, column or box kills every completion below it, so one failed check at the first cell discards up to 9 to the 49th leaves at once. The earlier a rule rejects a partial answer, the more of the tree is never built.

The figure runs the search on a real puzzle with 50 blanks and a single solution. At the first blank, in row 1 column 1, only 1, 3 and 5 break no rule; six of the nine branches are cut before anything under them exists. With 1 placed, the next blank has exactly one legal digit, 3, and the one after that has exactly one, 5. Most of the tree in the previous figure is never drawn at all.

Choosing What to Try First

The order of choices changes the size of the search, not its answer. Filling the most constrained cell first, the one with the fewest legal digits left, costs nothing when that cell has only one option, and makes any mistake surface near the root, where undoing it is cheap. Trying the most promising value first helps for the same reason.

On the puzzle in the figure, measured in Python, filling cells in reading order places 2,657 digits before reaching the solution. Filling the most constrained cell first places 173. The answer is the same and the worst case is unchanged, but the work dropped fifteenfold, and on harder puzzles and larger problems the gap commonly reaches orders of magnitude.

Constraint Problems at Work

Timetables are backtracking problems: no teacher in two rooms at once, no room double-booked, no class with two subjects in one slot. So are staff rosters and seating plans. So is package version resolution: when two requirements disagree about a shared dependency, Python's installer backtracks through candidate versions, and has done so by default since pip 20.3 in November 2020. Its documentation warns that this can look like pip downloading several versions of the same package.

A resolver's tree has one level per package and one branch per candidate version. Choosing version 2 of one library may rule out every version of another library the project also needs, and the resolver discovers the conflict only several levels further down, then backs up to try version 1. Each level it backs through can mean fetching the metadata of more candidates, which is where the minutes of a slow install go.

Industrial SAT and constraint solvers are backtracking plus learning. Each time a branch fails they record why, as a new rule, so that the same dead end is never entered twice anywhere else in the tree. Chapter 14 returns to them as the tools engineers reach for when a problem is hard in general.

What Backtracking Costs

The worst case stays exponential, because these problems are hard in general, which is the subject of Chapter 14. Pruning improves the typical case and promises nothing about the worst one. A regular expression engine that backtracks is the same machine: a pattern that forces it to try every way of splitting its input produces the catastrophic backtracking of Chapter 14's first topic, on a string only a few dozen characters long.

So a search that runs in production needs a budget, in time or in nodes visited, and a defined answer for when the budget runs out: a fallback timetable, an error that names the conflicting requirements, a rejected input. A search without a budget is a denial-of-service bug waiting for its input.