A constraint is a restriction on a space of possibilities; it is a piece of knowledge that narrows the scope of this space. Because constraints arise naturally in most areas of human endeavor, they are the most general means for formulating regularities that govern our computational, physical, biological, and social worlds. Some examples: the angles of a triangle must sum to 180 degrees; the four nucleotides that make up DNA strands can only combine in particular sequences; the sum of the currents flowing into a node must equal zero; Susan cannot be married to both John and Bill at the same time. Although observable in diverse disciplines, they all share one feature in common: they identify the impossible, narrow down the realm of possibilities, and thus permit us to focus more effectively on the possible.

Formulating problems in terms of constraints has proven useful for modeling fundamental cognitive activities such as vision, language comprehension, default reasoning, diagnosis, scheduling, and temporal and spatial reasoning, as well as having application for engineering tasks, biological modeling, and electronic com merce. Formulating problems in terms of constraints enables a natural, declarative formulation of what must be satisfied, without having to say how it should be satisfied.

This book provides comprehensive, in-depth coverage of the theory that under lies constraint processing algorithms as they have emerged in the last three decades, primarily in the area of artificial intelligence. The intended audience is readers in diverse areas of computer science, including artificial intelligence, databases, pro gramming languages, and systems, as well as practitioners of related fields such as operations research, management science, and applied mathematics.

This book focuses on the fundamental tools and principles that underlie reason ing with constraints, with special emphasis on the representation and analysis of constraint satisfaction algorithms that operate over discrete and finite domains. We first describe the basic principles underlying relational representation and then present processing algorithms across two main categories: search based and inference based. Search algorithms are characterized by backtracking search and its various enhancements, while inference algorithms are presented through a variety of constraint propagation methods (also known as consistencv-enforcine methods).