The Art of Computer Programming
Combinatorial algorithms are the methods that allow us to cope with problems that involve zillions of cases. β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.β
This chapter is from the book
This chapter is from the book
This chapter is from the book
Preface
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.
Knuth likes to include in those books [The Art of Computer Programming]
as much recreational material as he can cram in.
— MARTIN GARDNER, Undiluted Hocus-Pocus (2013)
The second half of this book is devoted to Section 7.2.2.2, “Satisfiability,” which addresses one of the most fundamental problems in all of computer science: Given a Boolean function, can its variables be set to at least one pattern of 0s and 1s that will make the function true? This problem arises so often, people have given it a nickname, ‘SAT’.
Satisfiability might seem like an abstract exercise in understanding formal systems, but the truth is far different: Revolutionary methods for solving SAT problems emerged at the beginning of the twenty-first century, and they’ve led to game-changing applications in industry. These so-called “SAT solvers” can now routinely find solutions to practical problems that involve millions of variables and were thought until very recently to be hopelessly difficult.
Satisfiability is important chiefly because Boolean algebra is so versatile. Almost any problem can be formulated in terms of basic logical operations, and the formulation is particularly simple in a great many cases. Section 7.2.2.2 therefore begins with ten typical examples of widely different applications, and closes with detailed empirical results for a hundred different benchmarks. The great variety of these problems — all of which are special cases of SAT —is illustrated on pages 300 and 301 (which are my favorite pages in this book).
The story of satisfiability is the tale of a triumph of software engineering, blended with rich doses of beautiful mathematics. Section 7.2.2.2 explains how such a miracle occurred, by presenting complete details of seven SAT solvers, ranging from the small-footprint methods of Algorithms A and B to the industrial strength, state-of-the-art methods of Algorithms W, L, and C. (Well I have to hedge a little: New techniques are continually being discovered; hence SAT technology is ever-growing and the story is ongoing. But I do think that Algorithms W, L, and C compare reasonably well with the best algorithms of their class that were known in 2010. They’re no longer at the cutting edge, but they still are amazingly good.)
Wow — Sections 7.2.2.1 and 7.2.2.2 have turned out to be the longest sections, by far, in The Art of Computer Programming — especially Section 7.2.2.2. The SAT problem is evidently a killer app, because it is key to the solution of so many other problems. Consequently I can only hope that my lengthy treatment does not also kill off my faithful readers! As I wrote this material, one topic always seemed to flow naturally into another, so there was no neat way to break either section up into separate subsections. (And anyway the format of TAOCP doesn’t allow for a Section 7.2.2.1.3 or a Section 7.2.2.2.6.)
I’ve tried to ameliorate the reader’s navigation problem by adding sub-headings at the top of each right-hand page. Furthermore, as always, the exercises appear in an order that roughly parallels the order in which corresponding topics are taken up in the text. Numerous cross-references are provided between text, exercises, and illustrations, so that you have a fairly good chance of keeping in sync. I’ve also tried to make the index as comprehensive as possible.
Look, for example, at a “random” page — say page 264, which is part of the subsection about Monte Carlo algorithms. On that page you’ll see that exercises 302, 303, 299, and 306 are mentioned. So you can guess that the main exercises about Monte Carlo algorithms are numbered in the early 300s. (Indeed, exercise 306 deals with the important special case of “Las Vegas algorithms”; and the next exercises explore a fascinating concept called “reluctant doubling.”) This entire book is full of surprises and tie-ins to other aspects of computer science.
As in previous volumes, sections and subsections of the text are occasionally preceded by an asterisk (*), meaning that the topics discussed there are “advanced” and skippable on a first reading.
You might think that a 700-page book has probably been padded with peripheral material. But I constantly had to “cut, cut, cut” while writing it, because a great deal more is known! I found that new and potentially interesting-yet-unexplored topics kept popping up, more than enough to fill a lifetime; yet I knew that I must move on. So I hope that I’ve selected for treatment here a significant fraction of the concepts that will be the most important as time passes.
Every week I’ve been coming across fascinating new things
that simply cry out to be part of The Art.
— DONALD E. KNUTH (2008)
Most of this book is self-contained, although there are frequent tie-ins with the topics discussed in previous volumes. Low-level details of machine language programming have already been covered extensively; so the algorithms in the present book are usually specified only at an abstract level, independent of any machine. However, some aspects of combinatorial programming are heavily dependent on low-level details that didn’t arise before; in such cases, all examples in this book are based on the MMIX computer, which supersedes the MIX machine that was defined in early editions of Volume 1. Details about MMIX appear in a paperback supplement to that volume called The Art of Computer Programming, Volume 1, Fascicle 1, containing Sections 1.3.1´, 1.3.2´, etc.; they’re also available on the Internet, together with downloadable assemblers and simulators.
Another downloadable resource, a collection of programs and data called The Stanford GraphBase, is cited extensively in the examples of this book. Readers are encouraged to play with it, in order to learn about combinatorial algorithms in what I think will be the most efficient and most enjoyable way.
I wrote nearly a thousand computer programs while preparing this material, because I find that I don’t understand things unless I try to program them. Most of those programs were quite short, of course; but several of them are rather substantial, and possibly of interest to others. Therefore I’ve made a selection available by listing some of them on the following webpage:
In particular you can download the programs DLX1, DLX2, DLX3, DLX5, DLX6, and DLX-PRE, which are the experimental versions of Algorithms X, C, M, C$, Z, and P, respectively, that were my constant companions while writing Section 7.2.2.1. Similarly, SAT0, SAT0W, SAT8, SAT9, SAT10, SAT11, SAT11K, SAT13 are the equivalents of Algorithms A, B, W, S, D, L, L′, C, respectively, in Section 7.2.2.2. Such programs will be useful for solving many of the exercises, if you don’t have access to other XCC solvers or SAT solvers. You can also download SATexamples.tgz from that page; it’s a collection of programs that generate data for all 100 of the benchmark examples discussed in the text, and many more.
Several exercises involve the lists of English words that I’ve used in preparing examples. You’ll need the data from
if you have the courage to work the exercises that use such lists.
Special Note: During the years that I’ve been preparing Volume 4, I’ve often run across basic techniques of probability theory that I would have put into Section 1.2 of Volume 1 if I’d been clairvoyant enough to anticipate them in the 1960s. Finally I realized that I ought to collect most of them together in one place, because the story of those developments is too interesting to be broken up into little pieces scattered here and there.
Therefore this book begins with a special tutorial and review of probability theory, in an unnumbered section entitled “Mathematical Preliminaries Redux.” References to its equations and exercises use the abbreviation ‘MPR’. (Think of the word “improvement.”)
Incidentally, just after the special MPR section, Section 7.2.2 begins intentionally on a left-hand page; and its illustrations are numbered beginning with Fig. 68. The reason is that Section 7.2.1 ended in Volume 4A on a right-hand page, and its final illustration was Fig. 67. My editor has decided to treat Chapter 7 as a single unit, even though it is being split into several physical volumes.
Special thanks are due to Nikolai Beluhov, Armin Biere, Niklas Eén, Marijn Heule, Holger Hoos, Wei-Hwa Huang, Svante Janson, Ernst Schulte-Geers, George Sicherman, Filip Stappers, and Udo Wermuth, for their detailed comments on my early attempts at exposition, as well as to dozens and dozens of other correspondents who have contributed crucial corrections. My editor at Addison–Wesley, Mark Taub, has expertly shepherded this series of books into the 21st century; and Julie Nahil, as senior content producer, has meticulously ensured that the highest publication standards have continued to be maintained. Thanks also to Tomas Rokicki for keeping my Dell workstation in shipshape order, as well as to Stanford’s InfoLab for providing extra computer power when that machine had reached its limits.
I happily offer a “finder’s fee” of $2.56 for each error in this book when it is first reported to me, whether that error be typographical, technical, or historical. The same reward holds for items that I forgot to put in the index. And valuable suggestions for improvements to the text are worth 32/c each. (Furthermore, if you find a better solution to an exercise, I’ll actually do my best to give you immortal glory, by publishing your name in subsequent printings:−)
Happy reading!
D. E. K.
Stanford, California
June 2022
A note on references
Several oft-cited journals and conference proceedings have special code names, which appear in the Index and Glossary at the close of this book. But the various kinds of IEEE Transactions are cited by including a letter code for the type of transactions, in boldface preceding the volume number. For example, ‘IEEE Trans. C-35’ means the IEEE Transactions on Computers, volume 35. The IEEE no longer uses these convenient letter codes, but the codes aren’t too hard to decipher: ‘EC’ once stood for “Electronic Computers,” ‘IT’ for “Information Theory,” ‘PAMI’ for “Pattern Analysis and Machine Intelligence,” and ‘SE’ for “Software Engineering,” etc.; ‘CAD’ meant “Computer-Aided Design of Integrated Circuits and Systems.”
A cross-reference such as ‘exercise 7.10–00’ points to a future exercise in Section 7.10 whose number is not yet known.
A note on notations
Simple and intuitive conventions for the algebraic representation of mathematical concepts have always been a boon to progress, especially when most of the world’s researchers share a common symbolic language. The current state of affairs in combinatorial mathematics is unfortunately a bit of a mess in this regard, because the same symbols are occasionally used with completely different meanings by different groups of people; some specialists who work in comparatively narrow subfields have unintentionally spawned conflicting symbolisms. Computer science — which interacts with large swaths of mathematics — needs to steer clear of this danger by adopting internally consistent notations whenever possible. Therefore I’ve often had to choose among a number of competing schemes, knowing that it will be impossible to please everyone. I have tried my best to come up with notations that I believe will be best for the future, often after many years of experimentation and discussion with colleagues, often flip-flopping between alternatives until finding something that works well. Usually it has been possible to find convenient conventions that other people have not already coopted in contradictory ways.
Appendix B is a comprehensive index to all of the principal notations that are used in the present book, inevitably including several that are not (yet?) standard. If you run across a formula that looks weird and/or incomprehensible, chances are fairly good that Appendix B will direct you to a page where my intentions are clarified. But I might as well list here a few instances that you might wish to watch for when you read this book for the first time:
Hexadecimal constants are preceded by a number sign or hash mark. For example,#
123means (123)16.The “monus” operation x ∸ y, sometimes called dot-minus or saturating subtraction, yields max(0, x − y).
The median of three numbers {x, y, z} is denoted by 〈xyz〉.
The “two dots” notations (x..y), (x..y], [x..y), and [x..y] are used to denote intervals.
A set such as {x}, which consists of a single element, is often denoted simply by x in contexts such as X ∪ x or X \ x.
If n is a nonnegative integer, the number of 1-bits in n’s binary representation is νn. Furthermore, if n > 0, the leftmost and rightmost 1-bits of n are respectively 2λn and 2ρn. For example, ν 10 = 2, λ10 = 3, ρ10 = 1.
The Cartesian product of graphs G and H is denoted by G □ H. For example, Cm □ Cn denotes an m × n torus, because Cn denotes a cycle of n vertices.