Backtracking

The Sudoku Exchange puzzle bank holds 893,916 sudoku, and each has a rating: how cunning a technique a person will need. A computer needs no techniques. It puts into an empty cell the first digit that does not clash with its neighbours and moves to the next cell, and on hitting a cell where nothing fits, it erases the last digit and tries the next one. Below are 1606 puzzles from the bank: across, the rating for a person; up, how many digits the computer wrote before solving it. Click any dot and the search will run right here. Then switch the order in which it visits the cells.

The scene opened on a puzzle from the easy file. Its rating is 1.2, the lowest in the bank: a person solves it with the simplest techniques, without a single guess. A search that visits the cells in order wrote 10,696,818 digits and erased all but the last 57. The curve next to the board is how many digits stand on the board at each moment: it soars and falls millions of times. Now turn on “Most constrained first”. The same puzzle is solved in 57 digits, one per empty cell, without a single dead end, and the whole cloud of dots drops by one and a half to two orders of magnitude.

Almost absent from the chart is any link between difficulty for a person and for the search. The median for the easy file is 1008 digits, for the diabolical file 6847, only seven times more. And within any file the dots are scattered over more than five orders of magnitude, from forty-odd digits to millions. A person looks for patterns, the search does not see them: it struggles where bad early choices take a long time to reveal themselves.

The idea

The solution is built step by step. At each step make one choice and immediately check whether the rules are broken. If they are, undo the choice and try the next; if the options at this step have run out, undo the previous step. This way we walk depth-first through the tree of partial solutions and cut off a whole branch as soon as its beginning is already wrong.

This is backtracking. It is convenient to think of it as a walk through a search tree. At the root is an empty board. The children of a node are all the ways to make the next choice. The leaves are either finished solutions or dead ends where the next choice cannot be made. Nobody builds the tree: the search keeps in memory only the path from the root to the current node and, going down, changes one and the same board, and going back up, restores it as it was. Hence the name.

In code this walk has four moves, and they repeat in every search problem: choose an option, check that the rules hold, go deeper with a recursive call, and restore everything as it was before the choice. Only the options themselves and the check change.

The search tree: queens

The classic example is queens. On an n × n board place n queens so that no two attack each other: not along a column, a row or a diagonal. Each row will have exactly one queen, so we place them row by row from the top: the choice at level k of the tree is the column of the queen in row k. Below is the whole tree: pale lines are what the search has yet to discover. Start the walk and watch the board.

For n = 8 the tree has, level by level, 1, 8, 42, 140, 344, 568, 550, 312 and 92 nodes, 2057 in all, and the 92 bottom nodes are all the solutions of the problem. Up to the fifth level the tree widens, and after that it narrows: the more queens stand, the fewer cells are not under attack, and branches run into dead ends one after another, the red dashes where the next row is swept entirely.

Pruning decides everything here. Compare three trees for the same problem:

The rules in all three rows are the same; the only difference is when they are checked. A check at the end rejects placements one at a time. A check at each step rejects a branch at once together with everything under it: a queen placed under attack in the third row would drag along 8⁵ = 32,768 full placements without checks, all of them invalid. The earlier a mistake is noticed, the more of the tree one check cuts off.

Why the search loses nothing

A branch cannot always be cut off. An attacked queen cannot be saved by any later queen: the attack is there and will not go away. In sudoku it is the same: two fives in one row will not disappear however many digits you add. Everything rests on this property.

Code

Queens by rows. Occupied columns and diagonals are kept in three arrays of flags: all cells of one “↘” diagonal share the difference row − col, all cells of a “↙” diagonal the sum row + col. So the check “is the new cell attacked” is three array lookups, and restoring is three assignments of False. The program prints the number of nodes at each level and compares the tree with the tree without checks.

n = 8: 92 solutions, 2057 nodes of the search tree
nodes by row: 1 8 42 140 344 568 550 312 92
first solution (column of the queen in rows 1..8): 1 5 8 6 3 7 2 4

The same skeleton solves sudoku. A row, a column and a box keep their occupied digits as bit masks, and the digits allowed in a cell are one expression: nine bits minus the union of three masks. The visiting order is moved into the function choose: the first empty cell or the cell with the fewest options. The puzzles come from the same bank as in the first scene.

To keep the program within the sandbox limits, the in-order search here gives up after 100,000 digits; without the limit it would reach the same numbers as in the scene. The third puzzle is discussed below.

Hardest first

Why does the choice of cell matter so much? The search tree is not given in advance: its shape is set by the order in which we make choices. Suppose one cell allows one digit and another five. Starting with the first, we make a forced move, and the tree does not branch at all. Starting with the second, we multiply everything below fivefold, and a mistake in the first cell, if there is one, will be discovered anew in each of the five branches. Worst of all is a cell with zero options: it means the current branch is dead, and the sooner we look at it, the less work is wasted.

Hence the rule: make the next choice where there are fewest options. In the constraint literature it is called “most constrained first” (minimum remaining values), and Robert Haralick and Gordon Elliott, who studied it in 1980, put the principle this way: to succeed, try first where you are most likely to fail. A cell where one digit is allowed is one of the first techniques taught for solving sudoku, and for easy puzzles it is almost always enough: the search with this rule solves two easy puzzles out of three without ever hitting a dead end.

Over the whole bank the median drops from 4556 digits to 97. The longest for the in-order search was a puzzle from the hard file rated 3.2: 36,544,073 digits. The most constrained cell solves it in 880. The bank has 991 puzzles on which the in-order search writes more than a million digits.

The rule gives no guarantee. The listing's third puzzle is the longest for it in the whole bank: 17,979 digits against 81,641 for the in-order search. The rule wins here too, but only four and a half times. And on 3943 puzzles out of 893,916 the in-order search is faster: the first cells in order happened to be lucky. Find the “The longest for most constrained” button in the scene and compare both orders on it.

The rule has a price too: to find the most constrained cell, every node has to look at all empty cells, fifty-odd computations instead of one. But there become tens of times fewer nodes, and the deal pays off. Knuth wrote about the same thing in general: a stronger check narrows the tree but costs more in each node, and a good search is a balance found.

The next step after choosing the most constrained cell is inference: having placed a digit, immediately fill in all digits that have become the only option, and so on as long as something can be filled in. SAT solvers are built on this: the DPLL algorithm of 1962 is backtracking with unit propagation added. What this looks like on the same sudoku is shown in the course chapter on hard problems.

What it costs

The time of a search is the number of tree nodes times the work per node. The work per node is usually small and clear: three checks per column for queens, taking masks apart for sudoku. But the number of nodes is unknown in advance, and in the worst case it is exponential: the queens tree grows about five to six times with each next n. Below is the full search for n from 4 to 12 in Python and up to 15 in Go; the time axis is logarithmic, and the exponential looks like a straight line.

Memory, on the contrary, is modest: at any moment the search keeps only the path from the root, O(depth) recursion frames and one shared board. So a search runs up against time, not memory: it can run for days on a few kilobytes.

For many problems that need a search, nothing fundamentally better is known. Sudoku on an n² × n² board, three-colouring a graph, satisfiability of a formula are NP-complete problems, and a fast algorithm for any of them would answer the question “P = NP?” (course chapter). So in practice the question sounds different: will the search finish on these data, and how can we find out without waiting for the end.

Knuth's estimate: the size of the tree without walking it

In 1975 Donald Knuth published a method devised back in 1962. Go down from the root along a random branch: at each node count how many children it has, d₁, d₂, …, and go to a random one of them. If the whole tree branched the way this path does, the first level would have d₁ nodes, the second d₁d₂, the third d₁d₂d₃. The sum 1 + d₁ + d₁d₂ + … is an estimate of the number of nodes, and the last product, if the descent reached a solution, an estimate of the number of solutions. Go back to the queens scene, turn on “Knuth's estimate” and make a few descents.

One estimate can be badly off, but the mean of many descents quickly becomes decent. The listing makes a thousand descents for n = 8 and 10, where the tree is easy to walk and compare, and ten thousand for 20 and 27, where the number of solutions is known from a full search, and walking the tree would take hours and ages.

 n  walks   nodes (estimate)        exact   solutions (estimate)              exact
 8   1000               2059         2057                    104                 92
10   1000              35637        35539                    651                724
20  10000      3713131807868            ?            30688146577        39029188884
27  10000           2.84e+19            ?     217095032575214752 234907967154122528

For 27 queens the estimate, in tenths of a second, was off by 8%. The exact number of solutions, 234,907,967,154,122,528, was obtained by the Q27 project in September 2016, and the computation on special programmable chips took a little over a year. For 20 queens the estimate promises about 3.7·10¹² nodes, twenty thousand times more than at n = 15. If a Go program does 15 queens in two seconds, 20 will take it about half a day. That is worth knowing before the run, not after. Knuth recalled once waiting all night for the output of a search program, only to find out that the answer would have taken about a million centuries.

Where backtracking falls short

Identical subtrees. The search does not remember what it has already computed. In how many ways can 5000 tenge be changed? The remainder of 1000 tenge after “2000 + 2000” and after “1000 + 1000 + 1000 + 1000” is the same subproblem, but the search will solve it anew in every branch. If subproblems repeat and there are few of them, you need memoization and dynamic programming: this is how a knapsack with small weights is solved in fractions of a second where a search over subsets would never end.

No solution. To find a solution, one lucky branch is sometimes enough. To prove there is no solution, the whole tree has to be cut off or walked. A puzzle with a contradiction in its givens is the worst input for any search.

Symmetry. The queens puzzle has 92 solutions, but only 12 are essentially different: the rest are rotations and reflections of the board. The search does not know this and dutifully finds them all. The simplest cure is to forbid symmetric beginnings: for example, put the first queen only in the left half of the row and double the answer. The tree shrinks almost by half; the project that counted the solutions for 27 queens, thanks to symmetries, searched only a little over an eighth of them.

Regular expressions. Most regular expression engines, Perl, Python, Java, PCRE, match a string by backtracking, and an expression like (x+)+y on a string of x's without y makes them try exponentially many ways to cut the string. How this ends in production is taken apart in the course chapter on automata; engines built on Thompson automata do not have this trouble.

Where it is used

• SAT solvers. The Davis–Logemann–Loveland algorithm (1962) is a search over variable values with backtracking and inference. Modern solvers added learning from conflicts: each dead end yields a new constraint, and backtracking jumps many levels up at once. Chips and programs are verified with such solvers.
• Prolog. Backtracking is built into the language itself: a program describes what must hold, and the machine looks for suitable values and backs off when the next condition fails.
• Constraint solvers. Timetables, cargo packing, frequency assignment, graph colouring (colouring): a search choosing the most constrained variable, with inference and, in optimisation problems, branch and bound.
• Puzzles. Sudoku generators use a search to check that a puzzle has exactly one solution: having found the first, the search keeps looking for a second. In 2000 Knuth described “dancing links”, a way to make and undo choices quickly in exact cover problems, to which sudoku, pentominoes and many packings reduce.

History

The eight queens puzzle was published in 1848 by the chess composer Max Bezzel. In 1850 Franz Nauck found all 92 solutions, though without proving there were no others. Carl Friedrich Gauss worked on the puzzle at the same time: letters to the astronomer Heinrich Schumacher count 72 solutions, written before word came of Nauck's result. That there are exactly 92 was proved in 1874 by James Glaisher, and in the same year, independently, by Pauls.

The name of the method is older than its first description. According to Solomon Golomb and Leonard Baumert, it was called backtrack in the 1950s by Derrick Lehmer, a mathematician and one of the first to solve combinatorial problems on computing machines. The method was first described as an algorithm for a machine by R. J. Walker in 1960, and Golomb and Baumert took it through many problems in their 1965 paper “Backtrack programming”.

The queens got into textbooks through Niklaus Wirth. In the 1971 paper “Program development by stepwise refinement” Wirth used them to show how to write a program by gradual refinement, and counted how much work it does: 876 cell checks before the first solution and 15,720 before the last. Our listing makes the same number of checks: at each of the 2057 − 92 = 1965 nodes above the bottom level it looks at the eight cells of the next row, and 8 · 1965 = 15,720. A year later Edsger Dijkstra took the same example apart in “Notes on Structured Programming”.

Knuth came back to backtracking many times: in 1975 with the paper on estimating the size of the tree, dedicated to Lehmer's seventieth birthday, in 2000 with “dancing links”, and in 2022 the section on backtracking took up a sizeable part of volume 4B of “The Art of Computer Programming”.

Problems

In the first problem you solve hundreds of puzzles from the same bank, and the time limit will not forgive an in-order search. In the second the search looks for the smallest number of radio channels for transmitters in towns around Almaty: the most constrained variable, symmetry, and a lower bound to stop in time will all come in handy.