Art of Computer Programming, Volume 4, Fascicle 7, The

Volume 4 of The Art of Computer Programming is devoted to the topic of Combinatorial Algorithms. Combinatorial algorithms are the methods that allow developers 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. 4C will be the next such volume.

This fascicle, which will eventually form the first part of volume 4C, covers section 7.2.2.3 (Constraint Satisfaction Problems) of TAOCP. It follows the recently published volume 4B, which covered sections 7.2.2.1 (Dancing Links) and 7.2.2.2 (Satisfiability) of Knuth's grand project.

Sudoku is a simple example of a Contstraint Satisfaction Problem (CSP). The problem to solve is putting a number in each square, with the constraint that no row, column, or block can contain a repeating number. CSPs traverse many domains in computer science, including in AI, where tasks including resource allocation, planning, scheduling, and decision-making all are formulated as CSPs.

The latest chapter in Knuth's magnum opus!