Backtracking

Backtracking lists every solution to a problem, or finds one, by making a choice, searching everything that follows it, and undoing the choice before trying the next, all on one shared path. The topic opens on those three steps and the tree of partial solutions they walk, then traces every ordering of three items through the path's growth and shrinkage. A gotcha shows what forgetting the undo does to the output, and a code card gives subsets and permutations in three languages, copying the path only when a solution is recorded. A concept card costs a search by counting its leaves. Pruning follows, first on four queens placed row by row, then on dishes chosen to fit a budget exactly, and an exercise counts and prunes the seatings of four guests.