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. ...
Get The Art of Computer Programming, Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
