Backtracking: grow the tree, prune the hopeless

How to read this

State-space tree. The root is the empty partial solution. Each level fixes one more component: the column of the next queen, whether the next number is in or out of the subset, or the next vertex of the circuit. Nodes appear in the order a Depth-First Search (DFS) generates them; the small number above a node is that order (as in Levitin's figures).

Promising vs. nonpromising. A node is promising if the partial solution could still be completed. A red × (n-Queens) is a square that is attacked, so the node is never expanded. A red circle is a dead end: nothing below it can work, so the algorithm backtracks to the parent and tries the next option.

Counters. Compare the nodes the search actually generated with the size of the brute-force space (nⁿ boards, 2ⁿ subsets, (n−1)! vertex orders). That gap is what pruning buys you; the worst case is still exponential.

Big trees. When a tree has hundreds of nodes it is drawn as dots so the whole shape fits. Press ⤢ Full size to see it at readable size and scroll sideways.

Try this

1. 4-Queens, first solution. Before playing, guess how many queen placements succeed before a solution appears. The search places queens in 8 squares (nodes 1–8, root is node 0) and ends with columns (2, 4, 1, 3), exactly the tree in Levitin Fig. 12.2.
2. 4-Queens, all solutions. You get two answers, (2, 4, 1, 3) and (3, 1, 4, 2): mirror images. Why must a solution with queen 1 in column i have a twin with queen 1 in column n − i + 1?
3. 8-Queens, all solutions. Jump to the last step: 92 solutions from 2,057 tree nodes, versus 8⁸ = 16,777,216 boards for brute force. Now switch to first solution: how many nodes does it take?
4. Subset-sum, A = {3, 5, 6, 7}, d = 15. The complete tree has 15 nodes and one solution {3, 5, 7}. Change d to 14, then to 8: which pruning test (too big or too small) does most of the work each time?
5. Hamiltonian circuit. On the book graph the search finds a, b, f, e, c, d, a after generating 12 nodes below the root. Click b then f on the graph to delete edge bf and replay: is there still a circuit?