6 CONSTRAINT

SATISFACTION PROBLEMS

In which we see how treating states as more than just little black boxes leads to
the invention of a range of powerful new search methods and a deeper
understanding of problem structure and complexity.

phá các lĩnh vực cụ thể và được kiểm tra xem

chúng có phải ý kiến cần tìm hay không. Từ góc
nhìn

This chapter describes a way to solve a

wide variety of problems more efficiently. We
use a factored representation for each state: a
CONSTRAINT SATISFACTION PROBLEM
set of variables, each of which has a value. A
Chapters 3 and 4 explored the idea that problems problem is solved when each variable has a value
can be solved by searching in a space of states. that satisfies all the constraints on the variable. A
These states can be evaluated by domain-specific problem described this way is called a constraint
heuristics and tested to see whether they are goal satisfaction problem, or CSP. CSP search
states. From the point of view of the search algorithms take advantage of the structure of
algorithm, however, each state is atomic, or states and use general-purpose rather than
indivisible—a black box with no internal problem-specific heuristics to enable the solution
structure. (Phần 3 và 4 tìm hiểu về ý tưởng of complex problems. The main idea is to
những vấn đề có thể được giải quyết bằng cách eliminate large portions of the search space all at
nghiên cứu trong một không gian ý kiến. Những once by identifying variable/value
ý kiến này có thể được đánh giá bằng cách khám combinations that violate the constraints.

6.1 DEFINING CONSTRAINT SATISFACTION PROBLEMS

A constraint satisfaction problem consists of three components, X, D, and C:

X is a set of variables, {X1,... , Xn}.
D is a set of domains, {D1,... , Dn}, one for each variable.
C is a set of constraints that specify allowable combinations of values.
Each domain Di consists of a set of allowable values, {v1,... , vk} for variable Xi. Each
constraint Ci consists of a pair ⟨scope , rel ⟩, where scope is a tuple of variables that
participate in the constraint and rel is a relation that defines the values that those variables
can take on. A relation can be represented as an explicit list of all tuples of values that
satisfy the constraint, or as an abstract relation that supports two operations: testing if a
tuple is a member of the relation and enumerating the members of the relation. For
example, if X1 and X2 both have

202
Section 6.1. Defining Constraint Satisfaction 203
Problems
to a CSP is a consistent, complete assignment. A
partial assignment is one that assigns values to
only some of the variables.
ASSIGNMENT
6.1.1 Example problem: Map coloring
CONSISTENT
COMPLETE ASSIGNMENT Suppose that, having tired of Romania, we are
SOLUTION
PARTIAL ASSIGNMENT
looking at a map of Australia showing each of its
states and territories (Figure 6.1(a)). We are
the domain {A,B}, then the constraint saying the
two variables must have different values can be given the task of coloring each region either red,
written as ⟨(X1, X2), [(A, B), (B, A)]⟩ or as ⟨(X1, green, or blue in such a way that no neighboring
X2), X1 =/ X2⟩. regions have the same color. To formulate this as
To solve a CSP, we need to define a state a CSP, we define the variables to be the regions
space and the notion of a solution. Each state in a X = {WA, NT, Q, NSW , V, SA,T } .
CSP is defined by an assignment of values to
some or all of the variables, {Xi = vi, Xj = vj,.. .}. The domain of each variable is the set Di = {red
An assignment that does not violate any , green, blue}. The constraints require
constraints is called a consistent or legal neighboring regions to have distinct colors.
assignment. A complete assignment is one in Since there are nine places where regions border,
which every variable is assigned, and a solution there are nine constraints:
C = {SA /= WA, SA /= NT, SA Q, SA /= NSW , SA /= V,
WA /= NT, NT /= Q, Q NSW , NSW /= V } .
Here we are using abbreviations; SA /= WA is a
shortcut for ⟨(SA, WA), SA /= WA⟩, where
SA /= WA can be fully enumerated in turn as
{(red , green), (red , blue), (green, red ),
(green, blue), (blue, red ), (blue, green)} .

CONSTRAINT GRAPH
There are many possible solutions to this problem,
such as
{WA = red , NT = green,Q = red , NSW =
green,V = red , SA = blue,T = red }.
It can be helpful to visualize a CSP as a constraint
graph, as shown in Figure 6.1(b). The nodes of the
graph correspond to variables of the problem, and
a link connects any two vari- ables that participate
in a constraint.
Why formulate a problem as a CSP? One
reason is that the CSPs yield a natural rep-
resentation for a wide variety of problems; if you
already have a CSP-solving system, it is often
easier to solve a problem using it than to design a
custom solution using another search technique. In
addition, CSP solvers can be faster than state-space
searchers because the CSP solver can quickly
eliminate large swatches of the search space. For
example, once we have chosen {SA = blue} in the
Section 6.1. Defining Constraint Satisfaction 204
Problems
Australia problem, we can conclude that none of
the five neighbor- ing variables can take on the
value blue. Without taking advantage of constraint
propagation, a search procedure would have to
consider 35 = 243 assignments for the five
neighboring variables; with constraint propagation
we never have to consider blue as a value, so we
have only 25 = 32 assignments to look at, a
reduction of 87%.
In regular state-space search we can only ask:
is this specific state a goal? No? What about this
one? With CSPs, once we find out that a partial
assignment is not a solution, we can
Section 6.1. Defining Constraint Satisfaction 205
Problems

North
ern
Territ Queenslan
ory d
Sout
h N
Austra Western
lia ew
So Australia
uth
W
ale
s
Victoria

Tasmania

(a)

Figure 6.1 (a) The principal states and

be viewed as a constraint satisfaction prob
region so that no neighboring regions have
represented as a constraint graph.
variables violate a constraint—so we can focus
attention on the variables that matter. As a result,
many problems that are intractable for regular
state-space search can be solved quickly when
formulated as a CSP.

6.1.2 Example problem: Job-shop

scheduling
Factories have the problem of scheduling a day’s
worth of jobs, subject to various constraints. In
practice, many of these problems are solved with
CSP techniques. Consider the problem of
scheduling the assembly of a car. The whole job
is composed of tasks, and we can model each
task as a variable, where the value of each
variable is the time that the task starts, expressed
as an integer number of minutes. Constraints can
assert that one task must occur before another—
for example, a wheel must be installed before the
hubcap is put on—and that only so many tasks
can go on at once. Constraints can also specify
PRECEDENCE CONSTRAINTS
that a task takes a certain amount of time to
immediately discard further refinements of the complete.
partial assignment. Furthermore, we can see why We consider a small part of the car
the assignment is not a solution—we see which assembly, consisting of 15 tasks: install axles
Section 6.1. Defining Constraint Satisfaction 206
Problems
(front and back), affix all four wheels (right and
left, front and back), tighten nuts for each wheel,
affix hubcaps, and inspect the final assembly. We
can represent the tasks with 15 variables:
X = {AxleF , AxleB, Wheel RF , Wheel LF ,
Wheel RB, Wheel LB, NutsRF ,
NutsLF , NutsRB, NutsLB, CapRF ,
CapLF , CapRB , CapLB, Inspect } .
The value of each variable is the time that the
task starts. Next we represent precedence
constraints between individual tasks. Whenever
a task T1 must occur before task T2, and task T1
takes duration d1 to complete, we add an
arithmetic constraint of the form
T1 + d1 ≤ T2 .
Section 6.1. Defining Constraint Satisfaction 207
Problems
NutsRF +2 ≤
CapRF ;
Wheel LF +1
≤ NutsLF ;
NutsLF +2 ≤
CapLF ;
Wheel RB +1
≤ NutsRB;
NutsRB +2 ≤
CapRB ;
Wheel LB +1
≤ NutsLB;
NutsLB +2 ≤
CapLB .
DISJUNCTIVE CONSTRAINT
Suppose we have four workers to install wheels,
but they have to share one tool that helps put the
axle in place. We need a disjunctive constraint to
say that AxleF and AxleB must not overlap in time;
either one comes first or the other does:
(AxleF + 10 ≤ AxleB) or (AxleB + 10 ≤
AxleF ) .
This looks like a more complicated constraint,
combining arithmetic and logic. But it still reduces
to a set of pairs of values that AxleF and AxleF can
take on.
We also need to assert that the inspection
comes last and takes 3 minutes. For every variable
except Inspect we add a constraint of the form X +
dX ≤ Inspect . Finally, suppose there is a
requirement to get the whole assembly done in 30
DISCRETE DOMAIN minutes. We can achieve that by limiting the
domain of all variables:
In our example, the axles have to be in place
before the wheels are put on, and it takes 10 Di = {1, 2, 3,... , 27} .
minutes to install an axle, so we write This particular problem is trivial to solve, but
AxleF + 10 ≤ Wheel RF ; AxleF + 10 ≤ CSPs have been applied to job-shop schedul- ing
Wheel LF ; problems like this with thousands of variables. In
some cases, there are complicated constraints that
AxleB + 10 ≤ Wheel RB; AxleB + 10 ≤
are difficult to specify in the CSP formalism, and
Wheel LB .
more advanced planning techniques are used, as
Next we say that, for each wheel, we must affix discussed in Chapter 11.
the wheel (which takes 1 minute), then tighten the
nuts (2 minutes), and finally attach the hubcap (1 6.1.3 Variations on the CSP formalism
minute, but not represented yet): The simplest kind of CSP involves variables that
Wheel RF +1 have discrete, finite domains. Map-
≤ NutsRF ;
FINITE DOMAIN coloring problems and scheduling with time limits are both of this kind. The 8-queens
prob- lem described in Chapter 3 can also be viewed as a finite-domain CSP, where the
variables Q1,... , Q8 are the positions of each queen in columns 1,... , 8 and each variable
Section 6.1. Defining Constraint Satisfaction 208
Problems
has the domain Di = {1, 2, 3, 4, 5, 6, 7, 8}.
INFINITE

CONSTRAINT LANGUAGE

LINEAR CONSTRAINTS

NONLINEAR CONSTRAINTS
A discrete domain can be infinite, such as
the set of integers or strings. (If we didn’t put a
deadline on the job-scheduling problem, there
would be an infinite number of start times for
each variable.) With infinite domains, it is no
longer possible to describe constraints by
enumerating all allowed combinations of values.
Instead, a constraint language must be used that
understands constraints such as T1 + d1 ≤ T2
directly, without enumerating the set of pairs of
allowable values for (T1, T2). Special solution
algorithms (which we do not discuss here) exist
for linear constraints on integer variables—that
is, constraints, such as the one just given, in
which each variable appears only in linear form.
It can be shown that no algorithm exists for
solving general nonlinear constraints on integer
variables.
Section 6.1. Defining Constraint Satisfaction 209
Problems
CONTINUOUS DOMAINS variety of astronomical, precedence, and power
constraints. The best-known category of
continuous-domain CSPs is that of linear
programming problems, where con- straints must
be linear equalities or inequalities. Linear
programming problems can be solved in time
polynomial in the number of variables. Problems
with different types of constraints and objective
functions have also been studied—quadratic
programming, second-order conic programming,
and so on.
UNARY CONSTRAINT In addition to examining the types of
Constraint satisfaction problems with variables that can appear in CSPs, it is useful to
continuous domains are common in the real world look at the types of constraints. The simplest type
and are widely studied in the field of operations is the unary constraint, which restricts the value
research. For example, the scheduling of of a single variable. For example, in the map-
experiments on the Hubble Space Telescope coloring problem it could be the case that South
requires very precise timing of observations; the Australians won’t tolerate the color green; we can
start and finish of each observation and maneuver express that with the unary constraint ⟨(SA), SA /=
are continuous-valued variables that must obey a green⟩
BINARY CONSTRAINT
A binary constraint relates two NSW is a binary
variables. For example, SA
DUAL GRAPH
constraint. A binary CSP is one with only binary
constraints; it can be represented as a constraint
graph, as in Figure 6.1(b).
GLOBAL CONSTRAINT
We can also describe higher-order
constraints, such as asserting that the value of Y is
between X and Z, with the ternary constraint
Between(X, Y, Z).
A constraint involving an arbitrary number
CRYPTARITHMETIC of variables is called a global constraint. (The
name is traditional but confusing because it need
not involve all the variables in a prob- lem). One
of the most common global constraints is Alldiff ,
which says that all of the variables involved in the
constraint must have different values. In Sudoku
problems (see Section 6.2.6), all variables in a row
or column must satisfy an Alldiff constraint. An-
other example is provided by cryptarithmetic
puzzles. (See Figure 6.2(a).) Each letter in a
cryptarithmetic puzzle represents a different digit.
CONSTRAINT HYPERGRAPH For the case in Figure 6.2(a), this would be
represented as the global constraint Alldiff (F, T,
U, W, R, O). The addition constraints on the four
columns of the puzzle can be written as the
following n-ary constraints:
Section 6.1. Defining Constraint Satisfaction 210
Problems
O + O = R + 10 · C10 ·
C
C
1
1
0
0

+ 0
0

W
C
1
+
0
0
W
0

=
=
U
F
+
,
1
0 where C10, C100, and C1000 are auxiliary variables
representing the digit carried over into the tens,
· hundreds, or thousands column. These constraints
C can be represented in a constraint hypergraph,
1
such as the one shown in Figure 6.2(b). A
0 hypergraph consists of ordinary nodes (the circles
0 in the figure) and hypernodes (the squares), which
represent n-ary constraints.
C Alternatively, as Exercise 6.6 asks you to
1 prove, every finite-domain constraint can be
0
reduced to a set of binary constraints if enough
0
auxiliary variables are introduced, so we could
transform any CSP into one with only binary
+
constraints; this makes the algorithms simpler.
T Another way to convert an n-ary CSP to a binary
one is the dual graph transformation: create a
+ new graph in which there will be one variable for
each constraint in the original graph, and
T

1
0
Section 6.1. Defining Constraint Satisfaction 211
Problems

TWO F T U W R O
+TWO
FOUR
C3 C2 C1

(a) (b)
Figure 6.2 (a) A cryptarithmetic problem. Each letter stands for a distinct digit; the aim
is to find a substitution of digits for letters such that the resulting sum is arithmetically
correct, with the added restriction that no leading zeroes are allowed. (b) The constraint
hypergraph for the cryptarithmetic problem, showing the Alldiff constraint (square box at
the top) as well as the column addition constraints (four square boxes in the middle). The
variables C1, C2, and C3 represent the carry digits for the three columns.

variables {C1, C2} with the binary constraint

⟨(X, Y ), R1⟩, where (X, Y ) are the shared variables
and R1 is a new relation that defines the constraint
between the shared variables, as specified by the
original C1 and C2.
There are however two reasons why we
might prefer a global constraint such as Alldiff
rather than a set of binary constraints. First, it is
easier and less error-prone to write the problem
description using Alldiff . Second, it is possible to
design special-purpose inference algorithms for
PREFERENCE CONSTRAINTS
global constraints that are not available for a set
of more primitive constraints. We describe these
inference algorithms in Section 6.2.5.
The constraints we have described so far
have all been absolute constraints, violation of
which rules out a potential solution. Many real-
world CSPs include preference constraints
indicating which solutions are preferred. For
example, in a university class-scheduling prob-
lem there are absolute constraints that no
CONSTRAINT OPTIMIZATION PROBLEM professor can teach two classes at the same time.
one binary constraint for each pair of constraints But we also may allow preference constraints:
in the original graph that share variables. For Prof. R might prefer teaching in the morning,
example, if the original graph has variables {X, Y, whereas Prof. N prefers teaching in the
Z} and constraints ⟨(X, Y, Z), C1⟩ and afternoon. A schedule that has Prof. R teaching at
⟨(X, Y ), C2⟩ then the dual graph would have 2 p.m. would still be an allowable solution
Section 6.1. Defining Constraint Satisfaction 212
Problems
(unless Prof. R happens to be the department
chair) but would not be an optimal one.
Preference constraints can often be encoded as
costs on in- dividual variable assignments—for
example, assigning an afternoon slot for Prof. R
costs 2 points against the overall objective
function, whereas a morning slot costs 1. With
this formulation, CSPs with preferences can be
solved with optimization search methods, either
path-based or local. We call such a problem a
constraint optimization problem, or COP.
Linear programming problems do this kind of
optimization.
Section 6.1. Defining Constraint Satisfaction 213
Problems
6.2 CONSTRAINT PROPAGATION: INFERENCE IN CSPS
eliminated throughout the graph. There are
different types of local consistency, which we now
INFERENCE
cover in turn.
CONSTRAINT PROPAGATION
6.2.1 Node consistency
A single variable (corresponding to a node in the
LOCAL CONSISTENCY
CSP network) is node-consistent if all the values
in the variable’s domain satisfy the variable’s
unary constraints. For example, in the variant of
the Australia map-coloring problem (Figure 6.1)
where South Australians dislike green, the variable
SA starts with domain {red , green, blue}, and we
can make it node consistent by eliminating green,
NODE CONSISTENCY
leaving SA with the reduced domain {red , blue}.
We say that a network is node-consistent if every
variable in the network is node-consistent.
It is always possible to eliminate all the unary
constraints in a CSP by running node consistency.
It is also possible to transform all n-ary constraints
into binary ones (see Ex- ercise 6.6). Because of
this, it is common to define CSP solvers that work
with only binary constraints; we make that
assumption for the rest of this chapter, except
where noted.

ARC CONSISTENCY
6.2.2 Arc consistency
In regular state-space search, an algorithm can do A variable in a CSP is arc-consistent if every
only one thing: search. In CSPs there is a choice: value in its domain satisfies the variable’s binary
an algorithm can search (choose a new variable constraints. More formally, Xi is arc-consistent
assignment from several possibilities) or do a with respect to another variable Xj if for every
specific type of inference called constraint value in the current domain Di there is some value
propagation: using the constraints to reduce the in the domain Dj that satisfies the binary constraint
number of legal values for a variable, which in turn on the arc (Xi, Xj). A network is arc-consistent if
can reduce the legal values for another variable, every variable is arc consistent with every other
and so on. Constraint propagation may be variable. For example, consider the constraint Y =
intertwined with search, or it may be done as a X2 where the domain of both X and Y is the set of
preprocessing step, before search starts. Sometimes digits. We can write this constraint explicitly as
this preprocessing can solve the whole problem, so ⟨(X, Y ), {(0, 0), (1, 1), (2, 4), (3, 9))}⟩ .
no search is required at all.
The key idea is local consistency. If we treat To make X arc-consistent with respect to Y , we
reduce X’s domain to {0, 1, 2, 3}. If we also make
each variable as a node in a graph (see Figure
Y arc-consistent with respect to X, then Y ’s domain
6.1(b)) and each binary constraint as an arc, then
becomes {0, 1, 4, 9} and the whole CSP is arc-
the process of enforcing local con- sistency in each consistent.
part of the graph causes inconsistent values to be On the other hand, arc consistency can do
Section 6.1. Defining Constraint Satisfaction 214
Problems
nothing for the Australia map-coloring prob- lem.
Consider the following inequality constraint on
(SA, WA):
{(red , green), (red , blue), (green, red ),
(green, blue), (blue, red ), (blue, green)} .
Section 6.2. Constraint Propagation: Inference in 209
CSPs

function AC-3( csp) returns false if an inconsistency is found and true otherwise
inputs: csp, a binary CSP with components (X, D, C)
local variables: queue, a queue of arcs, initially all the arcs in csp
while queue is not empty do
(Xi, Xj) ← REMOVE-FIRST(queue)
if REVISE(csp, Xi, Xj) then
if size of Di = 0 then return false
for each Xk in Xi.NEIGHBORS - {Xj} do
add (Xk, Xi) to queue
return true

function REVISE( csp, Xi, Xj) returns true iff we revise the domain of Xi
revised ← false
for each x in Di do
if no value y in Dj allows (x ,y) to satisfy the constraint between Xi and Xj then
delete x from Di
revised ← true
return revised

Figure 6.3 The arc-consistency algorithm AC-3. After applying AC-3, either every
arc is arc-consistent, or some variable has an empty domain, indicating that the CSP
cannot be solved. The name “AC-3” was used by the algorithm’s inventor (Mackworth,
1977) because it’s the third version developed in the paper.

No matter what value you choose for SA (or for WA), there is a valid value for the other
variable. So applying arc consistency has no effect on the domains of either variable.
The most popular algorithm for arc consistency is called AC-3 (see Figure 6.3). To
make every variable arc-consistent, the AC-3 algorithm maintains a queue of arcs to
consider. (Actually, the order of consideration is not important, so the data structure is
really a set, but tradition calls it a queue.) Initially, the queue contains all the arcs in the
CSP. AC-3 then pops off an arbitrary arc (Xi, Xj) from the queue and makes Xi arc-
consistent with respect to Xj. If this leaves Di unchanged, the algorithm just moves on to the
next arc. But if this revises Di (makes the domain smaller), then we add to the queue all
arcs (Xk, Xi) where Xk is a neighbor of Xi. We need to do that because the change in Di
might enable further reductions in the domains of Dk, even if we have previously
considered Xk. If Di is revised down to nothing, then we know the whole CSP has no
consistent solution, and AC-3 can immediately return failure. Otherwise, we keep
checking, trying to remove values from the domains of variables until no more arcs are in
the queue. At that point, we are left with a CSP that is equivalent to the original CSP—they
both have the same solutions—but the arc-consistent CSP will in most cases be faster to
search because its variables have smaller domains.
The complexity of AC-3 can be analyzed as follows. Assume a CSP with n variables,
each with domain size at most d, and with c binary constraints (arcs). Each arc (Xk, Xi) can
be inserted in the queue only d times because Xi has at most d values to delete. Checking
Section 6.2. Constraint Propagation: Inference in 210
CSPs
Arc consistency can go a long way toward
reducing the domains of variables, sometimes
finding a solution (by reducing every domain to
GENERALIZED ARC CONSISTENT size 1) and sometimes finding that the CSP cannot
be solved (by reducing some domain to size 0).
But for other networks, arc consistency fails to
make enough inferences. Consider the map-
coloring problem on Australia, but with only two
colors allowed, red and blue. Arc consistency can
do nothing because every variable is already arc
consistent: each can be red with blue at the other
end of the arc (or vice versa). But clearly there is
no solution to the problem: because Western
Australia, Northern Territory and South Australia
all touch each other, we need at least three colors
for them alone.
Arc consistency tightens down the domains
(unary constraints) using the arcs (binary
constraints). To make progress on problems like
map coloring, we need a stronger notion of
consistency. Path consistency tightens the binary
constraints by using implicit constraints that are
inferred by looking at triples of variables.
A two-variable set {Xi, Xj} is path-consistent
PATH CONSISTENCY with respect to a third variable Xm if, for every
assignment {Xi = a, Xj = b} consistent with the
consistency of an arc can be done in O(d2) time, so
constraints on {Xi, Xj}, there is an assignment to
we get O(cd3) total worst-case time.1 Xm that satisfies the constraints on {Xi, Xm} and
It is possible to extend the notion of arc {Xm, Xj}. This is called path consistency because
consistency to handle n-ary rather than just binary one can think of it as looking at a path from Xi to
constraints; this is called generalized arc Xj with Xm in
consistency or sometimes hyperarc consis- tency, the middle.
depending on the author. A variable Xi is Let’s see how path consistency fares in
generalized arc consistent with respect to an n- coloring the Australia map with two colors. We
ary constraint if for every value v in the domain of will make the set {WA, SA} path consistent with
Xi there exists a tuple of values that is a member of respect to NT . We start by enumerating the
the constraint, has all its values taken from the consistent assignments to the set. In this case, there
domains of the corresponding variables, and has its are only two: {WA = red , SA = blue} and {WA =
Xi component equal to v. For example, if all blue, SA = red }. We can see that with both of
variables have the do- main {0, 1, 2, 3}, then to these assignments NT can be neither red nor blue
make the variable X consistent with the constraint (because it would conflict with either WA or SA).
X < Y < Z, we would have to eliminate 2 and 3 Because there is no valid choice for NT , we
from the domain of X because the constraint eliminate both assignments, and we end up with no
cannot be satisfied when X is 2 or 3. valid assignments for {WA, SA}. Therefore, we
know that there can be no solution to this problem.
The PC-2 algorithm (Mackworth, 1977) achieves
6.2.3 Path consistency path consistency in much the same way that AC-3
achieves arc consistency. Because it is so similar,
Section 6.2. Constraint Propagation: Inference in 211
CSPs
we do not show it here.

1
The AC-4 algorithm (Mohr and Henderson, 1986) runs in O(cd2) worst-case time but can be slower than AC-
3 on average cases. See Exercise 6.13.
Section 6.2. Constraint Propagation: Inference in 212
CSPs
6.2.4 K-consistency
K-CONSISTENCY Stronger forms of propagation can be defined
with the notion of k-consistency. A CSP is k-
consistent if, for any set of k − 1 variables and for
any consistent assignment to those variables, a
consistent value can always be assigned to any
kth variable. 1-consistency says that, given the
STRONGLY
K-CONSISTENT empty set, we can make any set of one variable
consistent: this is what we called node
consistency. 2-consistency is the same as arc
consistency. For binary constraint networks, 3-
consistency is the same as path consistency.
A CSP is strongly k-consistent if it is k-
consistent and is also (k − 1)-consistent, (k − 2)-
consistent, ... all the way down to 1-consistent.
Now suppose we have a CSP with n nodes and
make it strongly n-consistent (i.e., strongly k-
consistent for k = n). We can
then solve the problem as follows: First, we
choose a consistent value for X1. We are then
guaranteed to be able to choose a value for X2
because the graph is 2-consistent, for X3 because
it is 3-consistent, and so on. For each variable Xi,
we need only search through the d values in the
domain to find a value consistent with X1,... , Xi−1.
We are guaranteed to find a solution in time
O(n2d). Of course, there is no free lunch: any
algorithm for establishing n-consistency must
take time exponential in n in the worst case.
Worse, n-consistency also requires space that is
exponential in n. The memory issue is even more
severe than the time.
In practice, determining the appropriate level of
consistency checking is mostly an empirical
science. It can be said practitioners commonly
compute 2-consistency and less commonly 3-
consistency.

6.2.5 Global constraints

Remember that a global constraint is one
involving an arbitrary number of variables (but
not necessarily all variables). Global constraints
occur frequently in real problems and can be
handled by special-purpose algorithms that are
more efficient than the general-purpose meth- ods
Section 6.2. Constraint Propagation: Inference in 213
CSPs
described so far. For example, the Alldiff
constraint says that all the variables involved
must have distinct values (as in the
cryptarithmetic problem above and Sudoku
puzzles be- low). One simple form of
inconsistency detection for Alldiff constraints
works as follows: if m variables are involved in
the constraint, and if they have n possible distinct
values alto- gether, and m > n, then the constraint
cannot be satisfied.
This leads to the following simple
algorithm: First, remove any variable in the con-
straint that has a singleton domain, and delete that
variable’s value from the domains of the
remaining variables. Repeat as long as there are
singleton variables. If at any point an empty
domain is produced or there are more variables
than domain values left, then an inconsistency has
been detected.
This method can detect the inconsistency in
the assignment {WA = red , NSW = red } for
Figure 6.1. Notice that the variables SA, NT , and
Q are effectively connected by an Alldiff
constraint because each pair must have two
different colors. After applying AC-3 with the
partial assignment, the domain of each variable is
reduced to {green, blue}. That is, we have three
variables and only two colors, so the Alldiff
constraint is violated. Thus, a simple consistency
procedure for a higher-order constraint is
sometimes more effective than applying arc
consistency to an equivalent set of binary
constraints. There are more
Section 6.2. Constraint Propagation: Inference in 214
CSPs
enforce consistency by deleting the maximum
value of any domain if it is not consistent with
RESOURCE CONSTRAINT the minimum values of the other domains. Thus,
if each variable in our example has the domain
{2, 3, 4, 5, 6}, the values 5 and 6 can be deleted
from each domain.
For large resource-limited problems with
integer values—such as logistical problems
involving moving thousands of people in
hundreds of vehicles—it is usually not possible
to represent the domain of each variable as a
large set of integers and gradually reduce that set
by consistency-checking methods. Instead,
domains are represented by upper and lower
bounds and are managed by bounds
BOUNDS PROPAGATION propagation. For example, in an airline-
scheduling problem, let’s suppose there are two
flights, F1 and F2, for which the planes have
capacities 165 and 385, respectively. The initial
domains for the numbers of passengers on each
flight are then
D1 = [0, 165] and D2 = [0, 385] .
Now suppose we have the additional constraint
BOUNDS CONSISTENT
that the two flights together must carry 420
people: F1 + F2 = 420. Propagating bounds
constraints, we reduce the domains to
D1 = [35, 165] and D2 = [255, 385] .
We say that a CSP is bounds consistent if for
SUDOKU every variable X, and for both the lower- bound
complex inference algorithms for Alldiff (see van and upper-bound values of X, there exists some
Hoeve and Katriel, 2006) that propagate more value of Y that satisfies the constraint between X
constraints but are more computationally and Y for every variable Y . This kind of bounds
expensive to run. propagation is widely used in practical constraint
Another important higher-order constraint problems.
is the resource constraint, sometimes called the
atmost constraint. For example, in a scheduling 6.2.6 Sudoku example
problem, let P1,... , P4 denote the numbers of
personnel assigned to each of four tasks. The The popular Sudoku puzzle has introduced
constraint that no more than 10 personnel are millions of people to constraint satisfaction prob-
assigned in total is written as Atmost (10, P1, P2, lems, although they may not recognize it. A
P3, P4). We can detect an inconsistency simply Sudoku board consists of 81 squares, some of
by checking the sum of the minimum values of which are initially filled with digits from 1 to 9.
the current domains; for example, if each The puzzle is to fill in all the remaining squares
variable has the domain {3, 4, 5, 6}, the Atmost such that no digit appears twice in any row,
constraint cannot be satisfied. We can also column, or 3 × 3 box (see Figure 6.4). A row,
Section 6.2. Constraint Propagation: Inference in 215
CSPs
column, or box is called a unit.
The Sudoku puzzles that are printed in
newspapers and puzzle books have the property
that there is exactly one solution. Although some
can be tricky to solve by hand, taking tens of
minutes, even the hardest Sudoku problems yield
to a CSP solver in less than 0.1 second.
A Sudoku puzzle can be considered a CSP
with 81 variables, one for each square. We use
the variable names A1 through A9 for the top row
(left to right), down to I1 through I9 for the
bottom row. The empty squares have the domain
{1, 2, 3, 4, 5, 6, 7, 8, 9} and the pre- filled
squares have a domain consisting of a single
value. In addition, there are 27 different
Section 6.2. Constraint Propagation: Inference in 216
CSPs
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9

A A 4
B B 8
3 3
C C

D 2 D
9
E
2
E
6 1
F F
6
G G
5
H 9 H 7
I I 9
6
(a) (b)

Figure 6.4 (a) A Sudoku puzzle and (b) its solution.

Alldiff constraints: one for each row, column, and box of 9 squares.
Alldiff (A1, A2, A3, A4, A5, A6, A7, A8, A9)
Alldiff (B1, B2, B3, B4, B5, B6, B7, B8, B9)
···
Alldiff (A1, B1,C1, D1, E1,F 1, G1,H1,I1)
Alldiff (A2, B2,C2, D2, E2,F 2, G2,H2,I2)
···
Alldiff (A1, A2, A3, B1, B2, B3,C1,C2,C3)
Alldiff (A4, A5, A6, B4, B5, B6,C4,C5,C6)
···
Let us see how far arc consistency can take us. Assume that the Alldiff constraints have
been expanded into binary constraints (such as A1 /= A2 ) so that we can apply the AC-3
algorithm directly. Consider variable E6 from Figure 6.4(a)—the empty square between the
2 and the 8 in the middle box. From the constraints in the box, we can remove not only 2
and 8 but also 1 and 7 from E6 ’s domain. From the constraints in its column, we can
eliminate 5, 6, 2, 8, 9, and 3. That leaves E6 with a domain of {4}; in other words, we
know the answer for E6 . Now consider variable I6 —the square in the bottom middle box
surrounded by 1, 3, and 3. Applying arc consistency in its column, we eliminate 5, 6, 2, 4
(since we now know E6 must be 4), 8, 9, and 3. We eliminate 1 by arc consistency with I5 ,
and we are left with only the value 7 in the domain of I6 . Now there are 8 known values in
column 6, so arc consistency can infer that A6 must be 1. Inference continues along these
lines, and eventually, AC-3 can solve the entire puzzle—all the variables have their
domains reduced to a single value, as shown in Figure 6.4(b).
Of course, Sudoku would soon lose its appeal if every puzzle could be solved by a
Section 6.2. Constraint Propagation: Inference in 217
CSPs
mechanical application of AC-3, and indeed AC-3 works only for the easiest Sudoku
puzzles. Slightly harder ones can be solved by PC-2, but at a greater computational cost:
there are 255,960 different path constraints to consider in a Sudoku puzzle. To solve the
hardest puzzles and to make efficient progress, we will have to be more clever.
Indeed, the appeal of Sudoku puzzles for the human solver is the need to be
resourceful in applying more complex inference strategies. Aficionados give them colorful
names, such as “naked triples.” That strategy works as follows: in any unit (row, column or
box), find three squares that each have a domain that contains the same three numbers or a
subset of those numbers. For example, the three domains might be {1, 8}, {3, 8}, and {1,
3, 8}. From that we don’t know which square contains 1, 3, or 8, but we do know that the
three numbers must be distributed among the three squares. Therefore we can remove 1, 3,
and 8 from the domains of every other square in the unit.
It is interesting to note how far we can go without saying much that is specific to Su-
doku. We do of course have to say that there are 81 variables, that their domains are the
digits 1 to 9, and that there are 27 Alldiff constraints. But beyond that, all the strategies—arc
con- sistency, path consistency, etc.—apply generally to all CSPs, not just to Sudoku
problems. Even naked triples is really a strategy for enforcing consistency of Alldiff
constraints and has nothing to do with Sudoku per se. This is the power of the CSP
formalism: for each new problem area, we only need to define the problem in terms of
constraints; then the general constraint-solving mechanisms can take over.

6.3 BACKTRACKING SEARCH FOR CSPS

would be adding var = value to the assignment.
But for a CSP with n variables of domain size d,
we quickly notice something terrible: the
branching factor at the top level is nd because any
of d values can be assigned to any of n variables.
At the next level, the branching factor is (n −
1)d, and so on for n levels. We generate a tree
with n! · dn leaves, even though there are only dn
possible complete assignments!
Our seemingly reasonable but naive
formulation ignores crucial property common to
all CSPs: commutativity. A problem is
COMMUTATIVITY
commutative if the order of application of any
Sudoku problems are designed to be solved by given set of actions has no effect on the outcome.
inference over constraints. But many other CSPs CSPs are commutative because when assigning
cannot be solved by inference alone; there comes values to variables, we reach the same partial
a time when we must search for a solution. In this assignment regardless of order. Therefore, we
section we look at backtracking search algorithms need only consider a single variable at each node
that work on partial as- signments; in the next in the search tree. For example, at the root node
section we look at local search algorithms over of a search tree for coloring the map of Australia,
complete assignments. We could apply a standard we might make a choice between SA = red , SA =
depth-limited search (from Chapter 3). A state green, and SA = blue, but we would never choose
would be a partial assignment, and an action
between SA = red and WA = blue. With this
Section 6.2. Constraint Propagation: Inference in 218
CSPs
restriction, the number of leaves is dn, as we
would hope.
Section 6.3. Backtracking Search for 215
CSPs

function BACKTRACKING-SEARCH(csp) returns a solution, or failure

return BACKTRACK({ }, csp)
function BACKTRACK(assignment , csp) returns a solution, or failure
if assignment is complete then return
assignment var ← SELECT-UNASSIGNED-
VARIABLE(csp)
for each value in ORDER-DOMAIN-VALUES(var , assignment , csp)
do if value is consistent with assignment then
add {var = value} to assignment
inferences ← INFERENCE(csp, var ,
value) if inferences =/ failure then
add inferences to assignment
result ← BACKTRACK(assignment , csp)
if result /= failure
then return
result
remove {var = value} and inferences from assignment
return failure
Figure 6.5 A simple backtracking algorithm for constraint satisfaction problems. The al-
gorithm is modeled on the recursive depth-first search of Chapter 3. By varying the
functions SELECT-UNASSIGNED-VARIABLE and ORDER-DOMAIN-VALUES, we can
implement the general-purpose heuristics discussed in the text. The function I NFERENCE
can optionally be used to impose arc-, path-, or k-consistency, as desired. If a value
choice leads to failure (noticed either by I NFERENCE or by BACKTRACK), then value
assignments (including those made by INFERENCE) are removed from the current
assignment and a new value is tried.
BACKTRACKING SEARCH as described on page 87.
The term backtracking search is used for a In Chapter 3 we improved the poor
depth-first search that chooses values for one performance of uninformed search algorithms by
variable at a time and backtracks when a variable supplying them with domain-specific heuristic
has no legal values left to assign. The algorithm functions derived from our knowledge of the
is shown in Figure 6.5. It repeatedly chooses an problem. It turns out that we can solve CSPs
unassigned variable, and then tries all values in efficiently without such domain-specific knowl-
the domain of that variable in turn, trying to find edge. Instead, we can add some sophistication to
a solution. If an inconsistency is detected, then the unspecified functions in Figure 6.5, using
BACKTRACK returns failure, causing the previous them to address the following questions:
call to try another value. Part of the search tree 1. Which variable should be assigned next
for the Australia problem is shown in Figure 6.6, (SELECT-UNASSIGNED-VARIABLE ), and in
where we have assigned variables in the order what order should its values be tried
WA, NT, Q,. Because the representation of (ORDER-DOMAIN-VALUES )?
CSPs is standardized,
there is no need to supply B ACKTRACKING-SEARCH
with a domain-specific initial state,
action function, transition model, or goal test.
Notice that BACKTRACKING-SEARCH keeps
only a single representation of a state and alters
that representation rather than creating new ones,
Section 6.3. Backtracking Search for 216
CSPs

WA=red WA=green WA=blue

WA=red WA=red
NT=green NT=blue

WA=red WA=red
NT=green NT=green
Q=red Q=blue

Figure 6.6 Part of the search tree for the map-coloring problem in Figure 6.1.
The backtracking algorithm contains the line
var ← SELECT-UNASSIGNED-VARIABLE(csp) .
The simplest strategy for SELECT-UNASSIGNED-
VARIABLE is to choose the next unassigned
variable in order, {X1, X2,.. .}. This static variable
ordering seldom results in the most effi- cient
search. For example, after the assignments for WA
= red and NT = green in Figure 6.6, there is only
one possible value for SA, so it makes sense to
assign SA = blue next rather than assigning Q. In
fact, after SA is assigned, the choices for Q, NSW ,
and V are all forced. This intuitive idea—choosing
the variable with the fewest “legal” values—is
called the minimum- remaining-values (MRV)
heuristic. It also has been called the “most
MINIMUM- REMAINING-VALUES constrained variable” or “fail-first” heuristic, the
latter because it picks a variable that is most likely
to cause a failure soon, thereby pruning the search
tree. If some variable X has no legal values left, the
MRV heuristic will select X and failure will be
detected immediately—avoiding pointless searches
through other variables. The MRV heuristic
usually performs better than a random or static
DEGREE HEURISTIC ordering, sometimes by a factor of 1,000 or more,
2. What inferences should be performed at each although the results vary widely depending on the
step in the search (INFERENCE)? problem.
3. When the search arrives at an assignment The MRV heuristic doesn’t help at all in
that violates a constraint, can the search choosing the first region to color in Australia,
avoid repeating this failure? because initially every region has three legal
colors. In this case, the degree heuristic comes in
The subsections that follow answer each of these handy. It attempts to reduce the branching factor
questions in turn. on future choices by selecting the vari- able that is
involved in the largest number of constraints on
6.3.1 Variable and value ordering
other unassigned variables. In Figure 6.1, SA is the
Section 6.3. Backtracking Search for 217
CSPs
variable with highest degree, 5; the other variables
have degree 2 or 3, except for T , which has degree
0. In fact, once SA is chosen, applying the degree
heuris- tic solves the problem without any false
steps—you can choose any consistent color at each
choice point and still arrive at a solution with no
backtracking. The minimum-remaining-
Section 6.3. Backtracking Search for 218
CSPs
have to consider every value anyway. The same
holds if there are no solutions to the problem.
Why should variable selection be fail-first,
LEAST- CONSTRAINING- VALUE but value selection be fail-last? It turns out that,
for a wide variety of problems, a variable
ordering that chooses a variable with the
minimum number of remaining values helps
minimize the number of nodes in the search tree
by pruning larger parts of the tree earlier. For
value orderi ng, the trick is that we only need one
solution; therefore it makes sense to look for the
most likely values first. If we wanted to
enumerate all solutions rather than just find one,
then value ordering would be irrelevant.

6.3.2 Interleaving search and inference

So far we have seen how AC-3 and other
algorithms can infer reductions in the domain of
variables before we begin the search. But
inference can be even more powerful in the
course of a search: every time we make a choice
of a value for a variable, we have a brand-new
opportunity to infer new domain reductions on
the neighboring variables.
FORWARD CHECKING
One of the simplest forms of inference is
called forward checking. Whenever a vari- able
values heuristic is usually a more powerful guide,
X is assigned, the forward-checking process
but the degree heuristic can be useful as a tie-
establishes arc consistency for it: for each
breaker.
unassigned variable Y that is connected to X by a
Once a variable has been selected, the
constraint, delete from Y ’s domain any value that
algorithm must decide on the order in which to
is inconsistent with the value chosen for X.
examine its values. For this, the least-
Because forward checking only does arc
constraining-value heuristic can be effective in
consistency inferences, there is no reason to do
some cases. It prefers the value that rules out the
forward checking if we have already done arc
fewest choices for the neighboring variables in
the constraint graph. For example, suppose that in consistency as a preprocessing step.
Figure 6.1 we have generated the partial Figure 6.7 shows the progress of
backtracking search on the Australia CSP with
assignment with WA = red and NT = green and
for- ward checking. There are two important
that our next choice is for Q. Blue would be a bad
points to notice about this example. First, notice
choice because it eliminates the last legal value
that after WA = red and Q = green are assigned,
left for Q’s neighbor, SA. The least-constraining-
the domains of NT and SA are reduced to a single
value heuristic therefore prefers red to blue. In
value; we have eliminated branching on these
general, the heuristic is trying to leave the
variables altogether by propagat- ing information
maximum flexibility for subsequent variable
from WA and Q. A second point to notice is that
assignments. Of course, if we are trying to find all
after V = blue, the do- main of SA is empty.
the solutions to a problem, not just the first one,
Hence, forward checking has detected that the
then the ordering does not matter because we
Section 6.3. Backtracking Search for 219
CSPs
partial assignment
{WA = red ,Q = green,V = blue} is inconsistent
with the constraints of the problem, and
the algorithm will therefore backtrack
immediately.
For many problems the search will be more
effective if we combine the MRV heuris- tic with
forward checking. Consider Figure 6.7 after
assigning {WA = red }. Intuitively, it seems that
that assignment constrains its neighbors, NT and
SA, so we should handle those
Section 6.3. Backtracking Search for 220
CSPs WA NT Q

Initial domains
R
G
B R GB R GB R GB R GBAfter R WA=red
G
B R B
G
R B R B R B R BAfter B R B
G G G G G G
R B R B R BQ=green R B
B After
G G G
R B R B V=blue R B
Figure 6.7 The progress of a map-colorin
is assigned first; then forward checking dele
variables NT and SA. After Q = green is as
NT , SA, and NSW . After V = blue is assign
and SA, leaving SA with no legal values.

variables next, and then all the other variables will

fall into place. That’s exactly what hap- pens with
MRV: NT and SA have two values, so one of them
is chosen first, then the other, then Q, NSW , and V
in order. Finally T still has three values, and any
one of them works. We can view forward checking
as an efficient way to incrementally compute the
information that the MRV heuristic needs to do its
job.
Although forward checking detects many
inconsistencies, it does not detect all of them. The
MAINTAINING ARC CONSISTENCY (MAC) problem is that it makes the current variable arc-
consistent, but doesn’t look ahead and make all the
other variables arc-consistent. For example,
consider the third row of Figure 6.7. It shows that
when WA is red and Q is green, both NT and SA are
forced to be blue. Forward checking does not look
far enough ahead to notice that this is an
inconsistency: NT and SA are adjacent and so
cannot have the same value.
The algorithm called MAC (for Maintaining
Arc Consistency (MAC)) detects this
inconsistency. After a variable Xi is assigned a
value, the INFERENCE procedure calls AC-3, but
CHRONOLOGICAL BACKTRACKING instead of a queue of all arcs in the CSP, we start
with only the arcs (Xj, Xi) for all Xj that are
unassigned variables that are neighbors of Xi. From
there, AC-3 does constraint propagation in the
usual way, and if any variable has its domain
reduced to the empty set, the call to AC-3 fails and
we know to backtrack immediately. We can see
that MAC is strictly more powerful than forward
checking because forward checking does the same
thing as MAC on the initial arcs in MAC’s queue;
but unlike MAC, forward checking does not
Section 6.3. Backtracking Search for 221
CSPs
recursively propagate constraints when changes are
made to the domains of variables.

6.3.3 Intelligent backtracking: Looking

backward
The BACKTRACKING-SEARCH algorithm in Figure
6.5 has a very simple policy for what to do when a
branch of the search fails: back up to the preceding
variable and try a different value for it. This is
called chronological backtracking because the
most recent decision point is revisited. In this
subsection, we consider better possibilities.
Consider what happens when we apply
simple backtracking in Figure 6.1 with a fixed
variable ordering Q, NSW , V , T , SA, WA, NT .
Suppose we have generated the partial assignment
{Q = red , NSW = green,V = blue,T = red }.
When we try the next variable, SA, we see that
every value violates a constraint. We back up to T
and try a new color for
Section 6.3. Backtracking Search for 222
CSPs
A more intelligent approach to
backtracking is to backtrack to a variable that
might fix the problem—a variable that was
responsible for making one of the possible values
of SA impossible. To do this, we will keep track
of a set of assignments that are in conflict with
some value for SA. The set (in this case {Q = red
CONFLICT SET
, NSW = green,V = blue, }), is called the conflict
Tasmania! Obviously this is silly—recoloring set for SA. The backjumping method backtracks
Tasmania cannot possibly resolve the problem to the most recent assignment in
with South Australia.
BACKJUMPING the conflict set; in this case, backjumping would jump over Tasmania and try a new value
for V . This method is easily implemented by a modification to B ACKTRACK such that it
accumulates the conflict set while checking for a legal value to assign. If no legal value is
found, the algorithm should return the most recent element of the conflict set along with the
failure indicator.
The sharp-eyed reader will have noticed that forward checking can supply the conflict
set with no extra work: whenever forward checking based on an assignment X = x deletes a
value from Y ’s domain, it should add X = x to Y ’s conflict set. If the last value is deleted
from Y ’s domain, then the assignments in the conflict set of Y are added to the conflict set
of X. Then, when we get to Y , we know immediately where to backtrack if needed.
The eagle-eyed reader will have noticed something odd: backjumping occurs when
every value in a domain is in conflict with the current assignment; but forward checking
detects this event and prevents the search from ever reaching such a node! In fact, it can be
shown that every branch pruned by backjumping is also pruned by forward checking.
Hence, simple backjumping is redundant in a forward-checking search or, indeed, in a
search that uses stronger consistency checking, such as MAC.
Despite the observations of the preceding paragraph, the idea behind backjumping re-
mains a good one: to backtrack based on the reasons for failure. Backjumping notices
failure when a variable’s domain becomes empty, but in many cases a branch is doomed
long before this occurs. Consider again the partial assignment {WA = red , NSW = red }
(which, from our earlier discussion, is inconsistent). Suppose we try T = red next and then
assign NT , Q, V , SA. We know that no assignment can work for these last four variables,
so eventually we run out of values to try at NT . Now, the question is, where to backtrack?
Backjumping cannot work, because NT does have values consistent with the preceding
assigned variables—NT doesn’t have a complete conflict set of preceding variables that
caused it to fail. We know, however, that the four variables NT , Q, V , and SA, taken
together, failed because of a set of preceding variables, which must be those variables that
directly conflict with the four. This leads to a deeper notion of the conflict set for a variable
such as NT : it is that set of preced- ing variables that caused NT , together with any
subsequent variables, to have no consistent solution. In this case, the set is WA and NSW ,
so the algorithm should backtrack to NSW and skip over Tasmania. A backjumping
algorithm that uses conflict sets defined in this way
CONFLICT-DIRECTED BACKJUMPING
is called conflict-directed backjumping.
We must now explain how these new conflict
sets are computed. The method is in fact quite
simple. The “terminal” failure of a branch of the
Section 6.3. Backtracking Search for 223
CSPs
search always occurs because a variable’s domain
becomes empty; that variable has a standard
conflict set. In our example, SA fails, and its
conflict set is (say) {WA, NT, Q}. We backjump to
Q, and Q absorbs
Section 6.3. Backtracking Search for 220
CSPs
can tell us how far to back up, so we don’t waste
time changing variables that won’t fix the
problem. But we would also like to avoid
running into the same problem again. When the
search arrives at a contradiction, we know that
some subset of the conflict set is responsible for
the problem. Constraint learning is the idea of
finding a minimum set of variables from the
conflict set that causes the problem. This set of
variables, along with their corresponding values,
is called a no-good. We then record the no-good,
either by adding a new constraint to the CSP or
by keeping a separate cache of no-goods.
CONSTRAINT LEARNING For example, consider the state {WA = red
, NT = green,Q = blue} in the bottom row of
NO-GOOD
Figure 6.6. Forward checking can tell us this
the conflict set from SA (minus Q itself, of course) state is a no-good because there is no valid
into its own direct conflict set, which is assignment to SA. In this particular case,
{NT, NSW }; the new conflict set is {WA, NT, recording the no-good would not help, because
NSW }. That is, there is no solution from Q once we prune this branch from the search tree,
onward, given the preceding assignment to {WA, we will never encounter this combination again.
NT, NSW }. Therefore, we backtrack to NT , the But suppose that the search tree in Figure 6.6
most recent of these. NT absorbs {WA, NT, NSW were actually part of a larger search tree that
}− {NT } into its own direct conflict set {WA}, started by first assigning values for V and T .
giving {WA, NSW } (as stated in the previous Then it would be worthwhile to record
paragraph). Now the algorithm backjumps to {WA = red , NT = green,Q = blue} as a no-good
NSW , as we would hope. To summarize: let Xj because we are going to run into the
be the current variable, and let conf (Xj) be its same problem again for each possible set of
conflict set. If every possible value for Xj fails, assignments to V and T .
backjump to the most recent variable Xi in conf No-goods can be effectively used by
(Xj ), and set
forward checking or by backjumping. Constraint
conf (Xi) ← conf (Xi) ∪ conf (Xj) − {Xi} . learning is one of the most important techniques
When we reach a contradiction, backjumping used by modern CSP solvers to achieve
efficiency on complex problems.

6.4 LOCAL SEARCH FOR CSPS

to be effective in solving many CSPs. They use a
complete-state formulation: the initial state
assigns a value to every variable, and the search
changes the value of one variable at a time. For
example, in the 8-queens problem (see Figure
4.3), the initial state might be a random
configuration of 8 queens in 8 columns, and each
MIN-CONFLICTS
step moves a single queen to a new position in its
column. Typically, the initial guess violates
Local search algorithms (see Section 4.1) turn out
several constraints. The point of local search is to
Section 6.3. Backtracking Search for 221
CSPs
eliminate the violated constraints.2 In choosing a
new value for a variable, the most obvious
heuristic is to select the value
that results in the minimum number of conflicts
with other variables—the min-conflicts
2
Local search can easily be extended to constraint
optimization problems (COPs). In that case, all the techniques
for hill climbing and simulated annealing can be applied to
optimize the objective function.
Section 6.4. Local Search for CSPs 221

function MIN-CONFLICTS(csp, max steps) returns a solution or failure

inputs: csp, a constraint satisfaction problem
max steps, the number of steps allowed before giving up
current ← an initial complete assignment for csp
for i = 1 to max steps do
if current is a solution for csp then return current
var ← a randomly chosen conflicted variable from csp.VARIABLES
value ← the value v for var that minimizes CONFLICTS(var , v , current ,
csp) set var = value in current
return failure

Figure 6.8 The MIN-CONFLICTS algorithm for solving CSPs by local search. The initial
state may be chosen randomly or by a greedy assignment process that chooses a
minimal- conflict value for each variable in turn. The C ONFLICTS function counts the
number of constraints violated by a particular value, given the rest of the current
assignment.

Figure 6.9 A two-step solution using min-conflicts for an 8-queens problem. At each
stage, a queen is chosen for reassignment in its column. The number of conflicts (in this
case, the number of attacking queens) is shown in each square. The algorithm moves the
queen to the min-conflicts square, breaking ties randomly.

heuristic. The algorithm is shown in Figure 6.8 and its application to an 8-queens problem
is diagrammed in Figure 6.9.
Min-conflicts is surprisingly effective for many CSPs. Amazingly, on the n-queens
problem, if you don’t count the initial placement of queens, the run time of min-conflicts is
roughly independent of problem size. It solves even the million-queens problem in an aver-
age of 50 steps (after the initial assignment). This remarkable observation was the stimulus
leading to a great deal of research in the 1990s on local search and the distinction between
easy and hard problems, which we take up in Chapter 7. Roughly speaking, n-queens is
easy for local search because solutions are densely distributed throughout the state space.
Min-conflicts also works well for hard problems. For example, it has been used to schedule
observations for the Hubble Space Telescope, reducing the time taken to schedule a week
of observations from three weeks (!) to around 10 minutes.
 Section 6.5. The Structure of 222
Problems
the important constraints. Each constraint is
given a numeric weight, Wi, initially all 1. At
each step of the search, the algorithm chooses a
variable/value pair to change that will result in
the lowest total weight of all violated constraints.
The weights are then adjusted by incrementing
the weight of each constraint that is violated by
the current assignment. This has two benefits: it
CONSTRAINT WEIGHTING adds topography to plateaux, making sure that it
All the local search techniques from is possible to improve from the current state, and
Section 4.1 are candidates for application to it also, over time, adds weight to the constraints
CSPs, and some of those have proved especially that are proving difficult to solve.
effective. The landscape of a CSP under the min- Another advantage of local search is that it
conflicts heuristic usually has a series of can be used in an online setting when the
plateaux. There may be millions of variable as- problem changes. This is particularly important
signments that are only one conflict away from a in scheduling problems. A week’s airline
solution. Plateau search—allowing side- ways schedule may involve thousands of flights and
moves to another state with the same score—can tens of thousands of personnel assignments, but
help local search find its way off this plateau. bad weather at one airport can render the
This wandering on the plateau can be directed schedule infeasible. We would like to repair the
with tabu search: keeping a small list of schedule with a minimum number of changes.
recently visited states and forbidding the This can be easily done with a local search
algorithm to return to those states. Simulated algorithm starting from the current schedule. A
annealing can also be used to escape from backtracking search with the new set of
plateaux. constraints usually requires much more time and
Another technique, called constraint might find a solution with many changes from
weighting, can help concentrate the search on the current schedule.

6.5 THE STRUCTURE OF PROBLEMS

probabilistic reasoning. After all, the only way
we can possibly hope to deal with the real world
is to decompose it into many subproblems.
Looking again at the constraint graph for
Australia (Figure 6.1(b), repeated as Figure
6.12(a)), one fact stands out: Tasmania is not
INDEPENDENT SUBPROBLEMS connected to the mainland.3 Intuitively, it is
obvious that coloring Tasmania and coloring the
CONNECTED COMPONENT
mainland are independent subproblems—any
In this section, we examine ways in which the solution for the mainland combined with any
structure of the problem, as represented by the solution for Tasmania yields a solution for the
constraint graph, can be used to find solutions whole map. Independence can be ascertained
quickly. Most of the approaches here also apply simply by finding connected components of the
to other problems besides CSPs, such as constraint graph. Each component corresponds to a
subproblem CSPi. If assignment Si is
a solution of CSP , then S is a solution of CSP . Why is this important? Consider
i
i i i i
Section 6.5. The Structure of 223
Problems
the following: suppose each CSPi has c variables from the total of n variables, where c is a
constant. Then there are n/c subproblems, each of which takes at most dc work to solve,
3
A careful cartographer or patriotic Tasmanian might object that Tasmania should not be colored the same as
its nearest mainland neighbor, to avoid the impression that it might be part of that state.
 Section 6.5. The Structure of 224
Problems
remaining value. Since each link from a parent to
its child is arc consistent, we know that for any
value we choose for the parent, there will be a
valid value left to choose for the child. That means
we won’t have to backtrack; we can move linearly
through the variables. The complete algorithm is
shown in Figure 6.11.

DIRECTED ARC CONSISTENCY

A E
B D A B C
FC F
(a)
TOPOLOGICAL SORT

where d is the size of the domain. Hence, the total

work is O(dcn/c), which is linear in n; without the Figure 6.10 (a) The constraint graph of a tree-structured C
decomposition, the total work is O(dn), which is the variables consistent with the tree with A as the root. Th
exponential in n. Let’s make this more concrete: sort of the variables.
dividing a Boolean CSP with 80 variables into four
subproblems reduces the worst-case solution time Now that we have an efficient algorithm for
from the lifetime of the universe down to less than trees, we can consider whether more general
a second. constraint graphs can be reduced to trees
Completely independent subproblems are somehow. There are two primary ways to do this,
delicious, then, but rare. Fortunately, some other one based on removing nodes and one based on
graph structures are also easy to solve. For collapsing nodes together.
example, a constraint graph is a tree when any two The first approach involves assigning values
variables are connected by only one path. We to some variables so that the remaining variables
show that any tree-structured CSP can be solved form a tree. Consider the constraint graph for
in time linear in the number of variables. 4 The key Australia, shown again in Fig- ure 6.12(a). If we
is a new notion of consistency, called directed arc could delete South Australia, the graph would
consistency or DAC. A CSP is defined to be become a tree, as in (b). Fortunately, we can do
directed arc-consistent under an ordering of this (in the graph, not the continent) by fixing a
variables X1, X2,... , Xn if and only if every Xi is arc- value for SA and
consistent with each Xj for j > i.
4
To solve a tree-structured CSP, first pick any Sadly, very few regions of the world have tree-structured
maps, although Sulawesi comes close.
variable to be the root of the tree, and choose an
ordering of the variables such that each variable
appears after its parent in the tree. Such an
ordering is called a topological sort. Figure
6.10(a) shows a sample tree and (b) shows one
possible ordering. Any tree with n nodes has n− 1
arcs, so we can make this graph directed arc-
consistent in O(n) steps, each of which must
compare up to d possible domain values for two
variables, for a total time of O(nd2). Once we have
a directed arc-consistent graph, we can just march
down the list of variables and choose any
Section 6.5. The Structure of 225
Problems

function TREE-CSP-SOLVER( csp) returns a solution, or failure

inputs: csp, a CSP with components X, D, C
n ← number of variables in X
assignment ← an empty
assignment root ← any variable
in X
X ← TOPOLOGICALSORT(X , root )
for j = n down to 2 do
MAKE-ARC-CONSISTENT(PARENT(Xj ), Xj )
if it cannot be made consistent then return failure
for i = 1 to n do
assignment [Xi] ← any consistent value from Di
if there is no consistent value then return failure
return assignment
Figure 6.11 The TREE-CSP-SOLVER algorithm for solving tree-structured CSPs. If
the CSP has a solution, we will find it in linear time; if not, we will detect a
contradiction.

NT NT
Q Q
WA WA

SA NSW
NSW

V V

T T

(a) (b)
Figure 6.12 (a) The original constraint graph from Figure 6.1. (b) The constraint
graph after the removal of SA.

deleting from the domains of the other variables any values that are inconsistent with the
value chosen for SA.
Now, any solution for the CSP after SA and its constraints are removed will be con-
sistent with the value chosen for SA. (This works for binary CSPs; the situation is more
complicated with higher-order constraints.) Therefore, we can solve the remaining tree with
the algorithm given above and thus solve the whole problem. Of course, in the general case
(as opposed to map coloring), the value chosen for SA could be the wrong one, so we would
need to try each possible value. The general algorithm is as follows:
 Section 6.5. The Structure of 226
Problems
2. For each possible assignment to the variables
CYCLE CUTSET
in S that satisfies all constraints on S,
(a) remove from the domains of the
remaining variables any values that are
inconsis- tent with the assignment for
S, and
(b) If the remaining CSP has a solution,
return it together with the assignment for
S.
If the cycle cutset has size c, then the total run
time is O(dc · (n − c)d2): we have to try each of
the dc combinations of values for the variables in
CUTSET CONDITIONING
S, and for each combination we must solve a tree
TREE DECOMPOSITION problem of size n − c. If the graph is “nearly a
tree,” then c will be small and the savings over
straight backtracking will be huge. In the worst
case, however, c can be as large as (n − 2).
Finding the smallest cycle cutset is NP-hard, but
several efficient approximation algorithms are
known. The overall algorithmic approach is called
cutset conditioning; it comes up again in Chapter
14, where it is used for reasoning about
probabilities.
The second approach is based on
constructing a tree decomposition of the
constraint graph into a set of connected
subproblems. Each subproblem is solved
independently, and the resulting solutions are then
combined. Like most divide-and-conquer
algorithms, this works well if no subproblem is
too large. Figure 6.13 shows a tree decomposition
of the map- coloring problem into five
subproblems. A tree decomposition must satisfy
the following three requirements:
• Every variable in the original problem
appears in at least one of the subproblems.
• If two variables are connected by a
constraint in the original problem, they must
appear together (along with the constraint)
in at least one of the subproblems.
• If a variable appears in two subproblems in
the tree, it must appear in every subproblem
along the path connecting those
TREE WIDTH
subproblems.
1. Choose a subset S of the CSP’s variables
The first two conditions ensure that all the
such that the constraint graph becomes a
variables and constraints are represented in the
tree after removal of S. S is called a cycle
decomposition. The third condition seems rather
cutset.
 Section 6.5. The Structure of 227
Problems
technical, but simply reflects the constraint that
any given variable must have the same value in
every subproblem in which it appears; the links
joining subproblems in the tree enforce this
constraint. For example, SA appears in all four of
the connected subproblems in Figure 6.13. You
can verify from Figure 6.12 that this
decomposition makes sense.
We solve each subproblem independently; if
any one has no solution, we know the en- tire
problem has no solution. If we can solve all the
subproblems, then we attempt to construct a
global solution as follows. First, we view each
subproblem as a “mega-variable” whose do- main
is the set of all solutions for the subproblem. For
example, the leftmost subproblem in Figure 6.13
is a map-coloring problem with three variables
and hence has six solutions—one is {WA = red ,
SA = blue, NT = green}. Then, we solve the
constraints connecting the subproblems, using the
efficient algorithm for trees given earlier. The
constraints between subproblems simply insist
that the subproblem solutions agree on their
shared variables. For example, given the solution
{WA = red , SA = blue, NT = green} for the first
subproblem, the only consistent solution for the
next subproblem is {SA = blue, NT = green,Q =
red }. A given constraint graph admits many tree
decompositions; in choosing a decompo- sition,
the aim is to make the subproblems as small as
possible. The tree width of a tree
Section 6.5. The Structure of 228
Problems

NT NT
Q
WA

SA SA

SA NSW

SA NSW
T
V

Figure 6.13 A tree decomposition of the constraint graph in Figure 6.12(a).

Section 6.5. The Structure of 229
Problems

VALUE SYMMETRY SYMMETRY- BREAKING CONSTRAINT

decomposition of a graph is one less than the size of the largest subproblem; the tree
width of the graph itself is defined to be the minimum tree width among all its tree
decompositions. If a graph has tree width w and we are given the corresponding tree
decomposition, then the problem can be solved in O(ndw+1) time. Hence, CSPs with
constraint graphs of bounded tree width are solvable in polynomial time. Unfortunately,
finding the decomposition with minimal tree width is NP-hard, but there are heuristic
methods that work well in practice.
So far, we have looked at the structure of the constraint graph. There can be
important structure in the values of variables as well. Consider the map-coloring
problem with n colors. For every consistent solution, there is actually a set of n!
solutions formed by permuting the color names. For example, on the Australia map we
know that WA, NT , and SA must all have different colors, but there are 3! = 6 ways to
assign the three colors to these three regions. This is called value symmetry. We would
like to reduce the search space by a factor of n! by breaking the symmetry. We do this
by introducing a symmetry-breaking constraint. For our example, we might impose
an arbitrary ordering constraint, NT < SA < WA, that requires the three values to be in
alphabetical order. This constraint ensures that only one of the n! solutions is possible:
{NT = blue, SA = green, WA = red }.
For map coloring, it was easy to find a constraint that eliminates the symmetry,
and in general it is possible to find constraints that eliminate all but one symmetric
solution in polynomial time, but it is NP-hard to eliminate all symmetry among
intermediate sets of values during search. In practice, breaking value symmetry has
proved to be important and effective on a wide range of problems.