# 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

## Preface

• Begin at the beginning, and do not allow yourself to gratify

• a mere idle curiosity by dipping into the book, here and there.

• 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:

• `http://www-cs-faculty.stanford.edu/~knuth/programs.html`

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

• `http://www-cs-faculty.stanford.edu/~knuth/wordlists.tgz`

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:−)

• 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,#`123` means (123)16.

• The “monus” operation xy, sometimes called dot-minus or saturating subtraction, yields max(0, xy).

• 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, CmCn denotes an m × n torus, because Cn denotes a cycle of n vertices.

### InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.

## Overview

Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

## Collection and Use of Information

To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

### Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

### Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.

### Surveys

Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

### Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.

If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

### Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

### Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

## Other Collection and Use of Information

### Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

### Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

### Do Not Track

This site currently does not respond to Do Not Track signals.

## Security

Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.

## Children

This site is not directed to children under the age of 13.

## Marketing

Pearson may send or direct marketing communications to users, provided that

• Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
• Such marketing is consistent with applicable law and Pearson's legal obligations.
• Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
• Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

## Correcting/Updating Personal Information

If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.

## Choice/Opt-out

Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

## Sale of Personal Information

Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

## Supplemental Privacy Statement for California Residents

California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

## Sharing and Disclosure

Pearson may disclose personal information, as follows:

• As required by law.
• With the consent of the individual (or their parent, if the individual is a minor)
• In response to a subpoena, court order or legal process, to the extent permitted or required by law
• To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
• In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
• To investigate or address actual or suspected fraud or other illegal activities
• To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
• To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
• To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.

This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.