# Catalogue of Artificial Intelligence Techniques

## Constraint Satisfaction and Propagation

**Aliases:**
CSP, Consistent-labelling, Satisfaction Assignment

**Keywords:**
backjumping, backtracking, databases, graph isomorphism, matching

### Categories: Inference and Reasoning , Problem Solving

Author(s): **Rina Dechter**

Constraint satisfaction is a class of problems in which knowledge is
expressed declaratively as a collection of explicit, categorical
constraints over a set of possibilities. These include, for example,
scene labelling, scene matching, space planning
problems, database consistency-maintenance,
query-answering, graph isomorphism
detection, the Graph Colouring problem, and many puzzles such as
crypto-arithmetic.
The *Constraint-Satisfaction Problem* consists of
a set of $n$
variables,${V}_{1}^{}\dots {V}_{n}^{}$

, each represented by its domain values (not necessarily numerical),${D}_{1}^{}\dots {D}_{n}^{}$

, and a set of constraints. A constraint ${C}_{i}^{}({V}_{{i}_{1}^{}}^{},\dots {V}_{{i}_{j}^{}}^{})$ is a subset of the Cartesian product${D}_{{i}_{1}^{}}^{}\times \mathrm{...}\times {D}_{{i}_{j}^{}}^{}$

that specifies which values of the
variables are compatible with each other.
A solution is an assignment of
values to all the variables which simultaneously satisfy
all the constraints, and the most common task associated with
these problems is to find one or all solutions.
In practice, the constraints may be specified either
as truth-tables, or as lists of the satisfying tuples or, more
concisely, in analytic form as expressions (such as $V+{V}_{}^{5}\le 9$
) in some `constraint languages', algebraic or
otherwise. See also the entry on Relaxation Labelling.
The common algorithm for solving CSPs is the
backtrack search algorithm. In its primitive
version, called Chronological Backtracking, the
algorithm traverses the variables in a predetermined order,
provisionally assigning consistent values to a subsequence (${V}_{1}^{},\mathrm{...},{V}_{i}^{}$
) of variables and attempting to append to it a new instantiation
of ${V}_{i+1}^{}$
such that the whole set is consistent. If no consistent
assignment can be found for the next variable ${V}_{i+1}^{}$
, a dead-end
situation occurs, the algorithm `backtracks' to the most recent
variable, changes its assignment and continues from there.
Chronological backtracking suffers from many maladies and several
cures have been offered and analysed in the AI literature. These can
be classified into *look-ahead schemes*, and *look-back
schemes*. The former are concerned with the decision of what variable
to instantiate (e.g., dynamic search rearrangement, max-cardinality
search, minimum width), or what value to assign next among all the
consistent choices available (e.g., forward-checking, full-lookahead,
partial look-ahead, constraint propagation). Look-back schemes
concern the decision of where and how to backtrack in case of a
dead-end situation. The two fundamental ideas in look-back schemes are
*go-back to source of failure*, and *constraint recording* or
learning. The former detect and change decisions that caused the
dead-end while skipping irrelevant decisions (e.g., selective
backtracking, backjumping), while
constraint-recording schemes identify the conflict-sets representing
the reasons for the dead-end and record them as explicit constraints
to disable the same conflicts from occurring in the future (e.g.,
Dependency Directed Backtracking).

### References:

- Kumar, V.,
*Algorithms for constraint-satisfaction problems: a survey*AI Magazine**13**(1992) no.1, 32--44.

### Comments:

No comments.