Constraint Satisfaction problems

Introduction and Definitions

 Search can be made easier in cases where the solution insted of corresponding to an optimal path, is only required to satisfy local consistency conditions. We call such problems Constraint Satisfaction (CS) Problems. For example, in a crossword puzzle it is only required that words that cross each other have the same letter in the location where they cross. It would be a general search problem if we require, say, that we use at most 15 vowels.

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.
Example 3: A cryptography problem: In the following pattern 

		S E N D
		M O R E
	      =========
	      M O N E Y
we 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:

The constraint satisfaction problem is to find, for each i from 1 to n, a value in Di for xi so that all constraints are satisfied.

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 Constraint Graph where the nodes are the variables and the edges are the binary constraints. Unary constraints can be disposed of by just redefining the domains to contain only the values that satisfy all the unary constraints. Higher order constraints are represented by hyperarcs. In the following we restrict our attention to the case of unary and binary constraints.

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:

Solution Methods

We consider three solution methods for constraint satisfaction problems, Generate-and-Test, Backtracking [possibly Dependency Directed], and Consistency Driven.

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 Chronological Backtracking, whereby variables are unbound in the inverse order to the the order used when they were bound. Dependency Directed Backtracking instead recognizes the cause of failure and backtracks to one of the causes of failure and skips over the intermediate variables that did not cause the failure.

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 2DOWN
NOTE: 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 | # |
	    +---+---+---+---+---+

Constraint Satisfaction in the Undergraduate AI Course

CS Problems, and systems intended to solve them, can be the subject of a number of assignments, laboratory exercises, and projects.

A number of programs dealing with constraints are available:

References

ingargiola@cis.temple.edu