The Art of Computer Programming, Volume 4B: Combinatorial Algorithms

Chapter 7—Combinatorial Searching

Nowhere to go but out,

Nowhere to come but back.

— BEN KING, in The Sum of Life (c. 1893)

Lewis back-tracked the original route up the Missouri.

— LEWIS R. FREEMAN, in National Geographic Magazine (1928)

When you come to one legal road that’s blocked,

you back up and try another.

— PERRY MASON, in The Case of the Black-Eyed Blonde (1944)

7.2.2. Backtrack Programming

Now that we know how to generate simple combinatorial patterns such as tuples, permutations, combinations, partitions, and trees, we’re ready to tackle more exotic patterns that have subtler and less uniform structure. Instances of almost any desired pattern can be generated systematically, at least in principle, if we organize the search carefully. ...