Figure 1: The map coloring problem as an example of CSP.
Constraint satisfaction problems (CSP) have a rich history in Artificial Intelligence [Davis & Rosenfeld, 1981, Dechter, Meiri, & Pearl, 1991, Dechter & Pearl, 1988, Freuder, 1989, Freuder, 1990, Mackworth, 1977, Mackworth & Freuder, 1985, Villain & Kautz, 1986, Waltz, 1975] (for a general reference, see Tsang, 1993). Constraint satisfaction provides a convenient way to represent and solve certain types of problems. In general, these are problems which can be solved by assigning mutually compatible values to a predetermined number of variables under a set of constraints. This approach has been used in a variety of disciplines including machine vision, belief maintenance, temporal reasoning, graph theory, circuit design, and diagnostic reasoning. When using a CSP approach (e.g., Figure 1), the variables are typically depicted as vertices or nodes, where each node is associated with a finite set of possible values, and the constraints imposed on the variables are depicted using arcs. An arc looping from a node to itself represents a unary constraint (a constraint on a single variable), and an arc between two nodes represents a binary constraint (a constraint on two variables). A classic example of a CSP is the map coloring problem (e.g., Figure 1), where a color must be assigned to each country such that no two neighboring countries have the same color. A variable represents a country's color, and a constraint arc between two variables indicates that the two joined countries are adjacent and should not be assigned the same color.
Figure 1: The map coloring problem as an example of CSP.
Formally, a CSP [Mackworth, 1977] is defined in Definition 1.
A CSP network contains all n-tuples in 
which
satisfy 
and 
. Since some of the labels
associated with a node may be incompatible with labels assigned to
other nodes, it is desirable, when the constraints are sufficiently
tight [van Beek, 1994], to eliminate as many of these labels as possible
by enforcing local consistency conditions before a globally consistent
solution is extracted [Dechter, 1992]. Node and arc consistency are
defined in Definitions 2 and
3, respectively. In addition, it may be
desirable to eliminate as many label pairs as possible using path
consistency, which is defined in Definition
4.
Node consistency is easily enforced by the operation 
, requiring O(nl) time (where n is the number
of variables and l is the maximum domain size). Arc consistency is
enforced by ensuring that every label for a node is supported by at
least one label for each node with which it shares a binary constraint
[Mackworth, 1977, Mackworth & Freuder, 1985, Mohr & Henderson1986]. The arc consistency
algorithm AC-4 [Mohr & Henderson1986] has an worst-case running time of
(where e is the number of constraint arcs). AC-3
[Mackworth & Freuder1985] often performs better than AC-4 in
practice, though it has a slower running time in the worst case. AC-6
[Bessière, 1994] has the same worst-case running time as AC-4 and is
faster than AC-3 and AC-4 in practice. Path consistency ensures that
any pair of labelings (i,a)-(j,b) allowed by the (i,j) arc
directly are also allowed by all arc paths from i to j. Montanari
has proven that to ensure path consistency for a complete graph, it
suffices to check every arc path of length two [Montanari, 1974]. The
path consistency algorithm PC-4 [Han & Lee, 1988] has a worst-case
running time of O( 
) time (where n is the number of
variables in the CSP).
