- Introduction and Definitions
- Solution Methods
- Constraint Satisfaction in the Undergraduate AI Course
- References

Many problems can be stated as constraints satisfaction problems. The CS approach has been used in a variety of situations, for example, in Sketchpad[Sutherland,64], an old and seminal graphical system, in Garnet[Myers,89], a recent graphical user interface, in ThingLab[Freeman-Benson,90], an object-oriented simulation system, in picture understanding [Waltz], in cryptography, temporal reasoning, in active data bases.

Here are some simple examples of constraint satisfaction problems:

**Example 1: The n-Queen problem:** The local condition is that no two
queens attack each other, i.e. are on the same row, or column, or diagonal.

**Example 2: A crossword puzzle:** We are to complete the puzzle

1 2 3 4 5 +---+---+---+---+---+ Given the list of words: 1 | 1 | | 2 | | 3 | AFT LASER +---+---+---+---+---+ ALE LEE 2 | # | # | | # | | EEL LINE +---+---+---+---+---+ HEEL SAILS 3 | # | 4 | | 5 | | HIKE SHEET +---+---+---+---+---+ HOSES STEER 4 | 6 | # | 7 | | | KEEL TIE +---+---+---+---+---+ KNOT 5 | 8 | | | | | +---+---+---+---+---+ 6 | | # | # | | # | The numbers 1,2,3,4,5,6,7,8 in the crossword +---+---+---+---+---+ puzzle correspond to the words that will start at those locations.

S E N D M O R E ========= M O N E Ywe have to replace each letter by a distinct digit so that the resulting sum is correct.

**Example 4: A map coloring problem:** We are given a map, i.e. a planar
graph, and we are told to color it using three colors, green, red, and blue,
so that no two neighboring countries have the same color.

All these examples are instances of the same pattern, captured by the following definition:

A ** Constraint Satisfaction Problem** is characterized by:

- a
*set of variables*{x1, x2, .., xn}, - for each variable xi a
*domain*Di with the possible values for that variable, and - a set of
*constraints*, i.e. relations, that are assumed to hold between the values of the variables. [These relations can be given intentionally, i.e. as a formula, or extensionally, i.e. as a set, or procedurally, i.e. with an appropriate generating or recognising function.] We will only consider constraints involving one or two variables.

A CS problem can easily be stated [Freuder] as a sentence in first order logic, of the form:

(exist x1)..(exist xn) (D1(x1) & .. Dn(xn) => C1..Cm)A CS problem is usually represented as an undirected graph, called

**Example 2 revisited:** We introduce a variable to represent each
word in the puzzle. So we have the variables:

VARIABLE | STARTING CELL | DOMAIN ================================================ 1ACROSS | 1 | {HOSES, LASER, SAILS, SHEET, STEER} 4ACROSS | 4 | {HEEL, HIKE, KEEL, KNOT, LINE} 7ACROSS | 7 | {AFT, ALE, EEL, LEE, TIE} 8ACROSS | 8 | {HOSES, LASER, SAILS, SHEET, STEER} 2DOWN | 2 | {HOSES, LASER, SAILS, SHEET, STEER} 3DOWN | 3 | {HOSES, LASER, SAILS, SHEET, STEER} 5DOWN | 5 | {HEEL, HIKE, KEEL, KNOT, LINE} 6DOWN | 6 | {AFT, ALE, EEL, LEE, TIE}The domain of each variable is the list of words that may be the value of that variable. So, variable 1ACROSS requires words with five letters, 2DOWN requires words with five letters, 3DOWN requires words with four letters, etc. Note that since each domain has 5 elements and there are 8 variables, the total number of states to consider in a naive approach is 5**8 = 390,625.

The constraints are all binary constraints:

1ACROSS[3] = 2DOWN[1] i.e. the third letter of 1ACROSS must be equal to the first letter of 2DOWN 1ACROSS[5] = 3DOWN[1] 4ACROSS[2] = 2DOWN[3] 4ACROSS[3] = 5DOWN[1] 4ACROSS[4] = 3DOWN[3] 7ACROSS[1] = 2DOWN[4] 7ACROSS[2] = 5DOWN[2] 7ACROSS[3] = 3DOWN[4] 8ACROSS[1] = 6DOWN[2] 8ACROSS[3] = 2DOWN[5] 8ACROSS[4] = 5DOWN[3] 8ACROSS[5] = 3DOWN[5]The corresponding graph is:

**Generate and Test**

We generate one by one all possible complete variable assignments and for each
we test if it satisfies all constraints. The corresponding program structure
is very simple, just nested loops, one per variable. In the innermost
loop we test each constraint.

In most situation this method is intolerably slow.

**Backtracking**

We order the variables in some fashion, trying to place first the variables that are more highly constrained or with smaller ranges. This order has a great impact on the efficiency of solution algorithms and is examined elsewhere. We start assigning values to variables. We check constraint satisfaction at the earliest possible time and extend an assignment if the constraints involving the currently bound variables are satisfied.

**Example 2 Revisited:** In our crossword puzzle we may order
the variables as follows: 1ACROSS, 2DOWN, 3DOWN, 4ACROSS, 7ACROSS,
5DOWN, 8ACROSS, 6DOWN. Then we start the assignments:

1ACROSS <- HOSES 2DOWN <- HOSES => failure, 1ACROSS[3] not equal to 2DOWN[1] <- LASER => failure <- SAILS 3DOWN <- HOSES => failure <- LASER => failure <- SAILS 4ACROSS <- HEEL => failure <- HIKE => failure <- KEEL => failure <- KNOT => failure <- LINE => failure, backtrack 3DOWN <- SHEET 4ACROSS <- HEEL 7ACROSS <- AFT => failure ................................What we have shown is called

The following is an easy way to do dependency directed backtracking. We keep track at each variable of the variables that precede it in the backtracking order and to which it is connected directly in the constraint graph. Then, when instantiation fails at a variable, backtracking goes in order to these variables skipping over all other intermediate variables.

Notice then that we will backtrack at a variable up to
as many times as there are
preceding neighbors. [This number is called the *width* of the
variable.]
The time complexity of the backtracking algorithm
grows when it has to backtrack often. Consequently there is a real gain when
the variables are ordered so as to minimize their largest width.

**Consistency Driven**

**Consistency Based Algorithms** use information from
the constraints to reduce the search space as early in the search as
it is possible. Here is a useful definition:

A CS problem is **i-consistent** iff for any choice of domains
Dj1, Dj2, .., Dji and for any choice of values in the first i-1 domains
there is a value in Dji such that the i-tuple consisting of all
these value will not violate any constraint, i.e. it is
**consistent**.

When a CS problem is i-consistent for i equal to one, we say that the
problem is **Node-Consistent**;
when i is two, we say the graph is **Arc-Consistent**.

Our crossword example is node consistent since there are no unary constraints,
but it is not arc-consistent. This can be seen by example: for the
value *LASER* for 1ACROSS we are unable to find a consistent
value for 2DOWN.

A solution to a CS problem gives a value ui to each variable xi of the problem. These values satisfy all the constraints of the problem. That is, the CS problem with domains

D1' = {u1}, D2' = {u2}, .., Dn' = {un}

is i-consistent for all values of i.

If in a CS problem with only unary and binary constraints we reduce the domains of the variables so that the resulting CS problem is 1-consistent and 2-consistent, the resulting domains contain all the solutions to the original CS problem. This is the foundation for an efficient and simple Consistency Based Algorithm, AC-3, due to Mackworth, that solves CS problems with only unary and binary constraints.

Function AC-3 (CS-Problem) is Let Q be a set initialized to contain all the arcs of CS-Problem; NOTE: since the constraint graph is undirected, each of its edges is represented by two directed arcs. begin Reduce all the domains of CS-Problem so that they satisfy the unary constraints; While Q is not empty Remove an arc (xi xj) from Q; If arc-reduce(xi, xj) then If the domain of xi is empty Return with failure; else Add to Q all arcs (xk xi), with k different than i and j, that are in the CS-Problem; Return with success; end AC-3; Function arc-reduce (xi, xj: problem variables) is Let Change be a boolean variable initialized to false; begin For each value u in the domain of xi find a value v in the domain of variable xj such that u and v satisfy all the binary constraints of the problem. If there is no such v, remove u from the domain of xi and set Change to true; Return the value of Change; end arc-reduce;

Upon completion of the AC-3 algorithm we usually have to run some form of the backtracking algorithm to find the solutions, if any. In example 3 the AC-3 algorithm does not reduce any domain, yet the problem has no solution.

**Example 3**: We are given the crossword puzzle

+--+--+ |1 |2 | with domains: {aa,bb} for 1ACROSS +--+--+ {ac,bd} for 1DOWN |3 | | {cc,dd} for 3ACROSS +--+--+ {ad,bc} for 2DOWNNOTE: Usually in crossword puzzles we have a single domain for all the variables. Then the length of words associated to variables partitions the domain. In our case we have changed the rules and specified apriori the domains of the variables.

For brevity we will write the
variable 1ACROSS as just 1A, 2DOWN as 2D, etc.

The AC-3 algorithm proceeds as follows:

(xi,xj) | NEW Di, if changed | ADDED {xk,xi} =================================================================== (1A 1D) | | (1D,1A) | | (1A,2D) | | (2D,1A) | | (1D,3A) | | (3A,1D) | | (3A,2D) | | (2D,3A) | | ===================================================================

**Example 2 re-Revisited:**
Here are the steps of the AC-3 algorithm in the crossword example.

(xi,xj) | NEW Di, if changed | ADDED {xk,xi} =================================================================== (1A 2D) | HOSES,LASER | (3D 1A) (3D,1A) | SAILS,SHEET,STEER | (4A,3D) (7A,3D) (8A,3D) (4A,3D) | HEEL,HIKE,KEEL | (2D,4A) (5D,4A) (7A,3D) | ALE,EEL,LEE,TIE | (2D,7A) (5D,7A) (8A,3D) | | (2D,4A) | SAILS,SHEET,STEER | (1A,2D) (7A,2D) (8A,2D) (5D,4A) | KEEL,KNOT | (7A,5D) (8A,5D) (2D,7A) | | (5D,7A) | KEEL | (4A,5D) (1A,2D) | | (7A,2D) | EEL,LEE | (3D,7A) (5D,7A) (8A,2D) | HOSES,LASER | (3D,8A) (5D,8A) (6D,8A) (7A,5D) | | (8A,5D) | | (4A,5D) | HIKE | (2D,4A) (3D,4A) (3D,7A) | | (5D,7A) | | (3D,8A) | SAILS,STEER | (1A,3D) (4A,3D) (7A,3D) (5D,8A) | | (6D,8A) | ALE | (2D,4A) | SAILS | (1A,2D) (7A,2D) (8A,2D) (3D,4A) | STEER | (8A,3D) (1A,3D) | HOSES | (2D,1A) (4A,3D) | | (7A,3D) | LEE | (2D,7A) (5D,7A) (1A,2D) | | (7A,2D) | | (8A,2D) | | (8A,3D) | LASER | (2D,8A) (5D,8A) (6D,8A) (2D,1A) | | (2D,8A) | | (5D,8A) | | (6D,8A) | | =============================================================== Thus the solution is: 1 2 3 4 5 +---+---+---+---+---+ 1 | H | O | S | E | S | +---+---+---+---+---+ 2 | # | # | A | # | T | +---+---+---+---+---+ 3 | # | H | I | K | E | +---+---+---+---+---+ 4 | A | # | L | E | E | +---+---+---+---+---+ 5 | L | A | S | E | R | +---+---+---+---+---+ 6 | E | # | # | L | # | +---+---+---+---+---+

- Crossword puzzles, cryptography, map coloring are good for simple assignments.
- Waltz procedure for labeling the junctions and edges of line drawings is with intermediate difficulty.

- An uncommented prolog program by Shoham for AC-3as described in Section 6.3 of Shoham
- Norvig's version of Waltz line labeling program and its data
- Pail's CSP Module
- Forbus and deKleer Lisp Symbolic Relaxation program
- SCREAMER, a non-deterministic Lisp which supports constraints where variables can have ranges that are either discrete or continuous.

- Forbus,K.,deKleer,J.: Building Problem Solvers

The MIT Press, 1993 - Freuder,e.: Synthesizing Constraint Expressions

CACM, Nov.1978, 21(11) - Norvig,P.: Artificial Intelligence Programming

Morgan-Kauffman, 1992 - Shoham,Y.: Artificial Intelligence - Techniques in Prolog

Morgan-Kauffman,1994 - Waltz,D.: Understanding Line Drawings of Scenes with Shadows.

in Psychology of Computer Vision, ed. P.Winston, MIP Press, 1975

*ingargiola@cis.temple.edu*