Donald Knuth - The Art of Computer Programming

Begin at the beginning, and do not allow yourself to gratify a mere idle curiosity by dipping into the book, here and there.

This would very likely lead to your throwing it aside, with the remark This is much too hard for me!, and thus losing the chance of adding a very large item to your stock of mental delights.

LEWIS CARROLL, in Symbolic Logic (1896)

This booklet is Fascicle 5 of The Art of Computer Programming, Volume 4: Combinatorial Algorithms. As explained in the preface to Fascicle 1 of Volume 1, Im circulating the material in this preliminary form because I know that the task of completing Volume 4 will take many years; I cant wait for people to begin reading what Ive written so far and to provide valuable feedback.

To put the material in context, this lengthy fascicle contains what is destined to become the first third of Volume 4B. More precisely, it contains the opening pages of will eventually fill at least four volumes (namely Volumes 4A, 4B, 4C, and 4D), assuming that Im able to remain healthy. It began in Volume 4A with a short review of graph theory and a longer discussion of Zeros and Ones (Section 7.1); that volume concluded with Section 7.2.1, Generating Basic Combinatorial Patterns, which was the first part of Section 7.2, Generating All Possibilities.

Now the story continues, with an introduction to the general principles of efficient backtrackingan important body of techniques that have been a mainstay of combinatorial algorithms since the beginning. (I fell in love with backtrack programming during my undergraduate days, and this love affair has now continued for more than sixty years.)

Most of this fascicle is devoted to , which explores data structures whose links perform delightful dances. Such structures are ideally suited to backtrack programming in general, and to the exact cover problem (XC) in particular. The XC problem, also known as set partitioning, essentially asks for all ways to cover a set of items, by choosing appropriate subsets of items called options. Dozens of important applications turn out to be special cases of XC, and the method of choice for such problems is often to use dancing links.

While writing this material I learned to my surprise that an apparently innocuous extension of the classical XC problem leads to an enormous increase in the number of significant special cases. This extended problem, called XCC (for exact covering with colors), allows some of the items to receive various colors. Colored items are allowed to be covered by many different options, as long as the colors are compatible.

Spoiler alert: With dancing links, we can solve XCC problems almost as easily as XC problems! Therefore I believe that the study of XCC solvers, now in its infancy, is destined to become quite important, and Ive done my best to introduce the subject here. There also are related methods for an even more general class of problems called MCC (multiple covering with colors), and for finding XCC solutions of