Preface to The Art of Computer Programming, Volume 4B
Don Knuth introduces his last volume to The Art of Computer Programming—4B "Combinatorial Algorithms."
From the book
From the book
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)
Combinatorial algorithms are the methods that allow us to cope with problems that involve zillions of cases. The explosive growth in the knowledge of such techniques has meant that several volumes are needed to describe them. Thus my original plan to devote Volume 4 of The Art of Computer Programming to combinatorial algorithms has morphed into a plan to prepare Volumes 4A, 4B, and so on. This book is the second of that series, a sequel to Volume 4A. In the preface to Volume 4A I explained why I was captivated by combinatorial algorithms soon after I fell in love with computers. "The art of writing such programs is especially important and appealing because a single good idea can save years or even centuries of computer time." Chapter 7 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 the opening parts of Section 7.2.2, "Backtrack Programming."
Backtracking is the name for an important body of techniques that have been a mainstay of combinatorial algorithms since the beginning. More than a third of this book is devoted to Section 7.2.2.1, 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 I've 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 minimum cost.
If you turn to a random page of Section 7.2.2.1, chances are good that you'll find some sort of puzzle being discussed. The reason is that puzzles are by far the best means I know to illustrate the algorithms and techniques that are being introduced here. The point of a puzzle is easily grasped; and the fact that an extraordinary number of quite different puzzles all turn out to be special cases of XCC and MCC is significant in itself. Indeed, it becomes clear that the same ideas will solve many complex and harder-to-explain problems of the "real world."
The new tools provided by dancing links allow me to emphasize the process of creating new puzzles, rather than simply to explain how to resolve puzzles that have already been posed. I've also tried my best to discuss the history of each puzzle type, and to give credit to the brilliant innovators who created them. As a result, I'm pleased that this book now contains, as a side-product of my attempts to teach computer methods, a treasure trove of information about recreational mathematics—from popular classics like edge-matching puzzles, or queen placement, or polyominoes, or the Soma cube, or rectangle dissections, or intriguing patterns of interlocking words, to more recent crazes like sudoku, slitherlink, masyu, and hitori.
I've had loads of fun writing other parts of these volumes, but without doubt Section 7.2.2.1 has been the funnest. And I know that my delight in good puzzles is shared by a significant number of leading computer scientists and mathematicians, who have told me that they chose their careers after having been inspired by such intellectual challenges.