Chapter 5

CSP definitions
Variables  X_{1}, X_{2},..., X_{n} each X_{i }having a nonempty domain D_{i} of possible values.
Constraints  C_{1}, C_{2},..., C_{m} consisting of some subset of variables and specifies allowable combinations of values for that subset.
State  defined by an assignment of values to some or all variables (X_{1}=v_{1}, X_{j}=v_{j}, ...)
Consistent  assignment that does not violate any constraints.
Solution  complete assignment that satisfies all constraints
CSP formulation
Initial state  empty assignment where all variables are unassigned.
Successor function  assigns value to an unassigned variable that does not conflict with previously assigned variables
Goal test  the current assignment is complete
Path cost  constant cost per step
Example: Map coloring
State  one of many but not a solution:
{WA=red, NT=red, Q=red, NSW=red, V=red, SA=red, T=red}
Solution  one of many; constraints satisfied, all variables assigned:
{WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=red}
One Solution
A complete assignment satisfying all constraints, for example:
{ WA=red, NT=green, SA=blue, Q=red, NSW=green, V=red, T=green}
 One variable is assigned at each step, how deep is the search?
 What is the number of complete assignments including those that violate constraints. These would be at leaf nodes.
 What is the total size of the state space?
 What are some of the invalid successor states of the assignment {WA=red}?
 What are some of the valid successor states of the assignment {WA=red}?
Constraint graph
Represents CSP.
 The constraint a != b in map coloring means that no adjacent Australian states are the same color.
 What is meaning of arcs from SA under the a != b constraint?
 What about the fact that there are no arcs to T.
 What is the implication of the arcs between WA, NT and SA?
Benefit of CSPs
Standard pattern  a set of variables assigned values, the successor function and goal test are generic for all CSPs
Generic heuristics  require no domainspecific knowledge
Constraint graph  structure used to simplify solution process, sometime exponential reduction over generalpurpose search (e.g. depthfirst).
CSP search formulation
Initial state: empty assignment in which all variables are unassigned
Successor function: a value can be assigned to any unassigned variable provided it does not violate problem constraints
Goal test: current assignment is complete
Path cost: constant cost for every step. Solution at depth n for n variables.
Varieties of CSPs
Varieties of constraints
Example: Cryptarithmetic
Constraints are square boxes connected to variables it constrains
Order 2  F, X_{3}
Order 3  O, R, X_{1}
Order 6  F, T, U, W, R, O
O + O = R + 10 * X_{1}
X_{1} + W + W = U + 10 * X_{2}
X_{2} + T + T = O + 10 * X_{3}
X_{3} = F
where X_{1, }X_{2} and X_{1} are auxiliary variables representing the 0 or 1 carry.
 What are some of the constraints on F?
 on X_{3} ?
 What is the domain of X_{1}, X_{2}, X_{3}?
 What are some valid successor states involving T and O for the assignment {F=0}?
Other, realworld problem examples:
Assignment: who will teach what class given qualifications and schedule
Timetabling: which class is offered when and where
Hardware configuration
Scheduling observation time on the Hubble Space Telescope
Notice that many realworld problems involve realvalued variables
Standard search formulation
def BACKTRACKING_SEARCH(csp) :
return RECURSIVE_BACKTRACKING( {}, csp)
def RECURSIVE_BACKTRACKING( assignment, csp) :
if COMPLETE(assignment, csp.VARIABLES ) : return assignment
var = SELECT_UNASSIGNED_VARIABLE( csp.VARIABLES, assignment, csp)
for value in ORDER_DOMAIN_VALUES( var, assignment, csp) :
if CONSISTENT(var, value, assignment, csp.CONSTRAINTS, csp.NEIGHBORS) :
assignment[var]=value # Add var=value
result = RECURSIVE_BACKTRACKING(assignment, csp)
if result != 'failure' : return result
del assignment[var] # Remove var=value
return 'failure'
Backtracking example
Constraints on SA will eventually cause failure when WA != Q. When not the same color (bottom right), SA cannot be assigned.
The algorithm will backtrack to a node with unexplored states.
For example, such as WA=red, NT=blue.
 Is SA in successor states after assigning {WA=red, NT=green, Q=blue}?
 What are some legal successor states after {WA=red, NT=green, Q=red}?
Python Constraint Satisfaction Problem solution (Download)
Binary CSP specified by four inputs:
 VARIABLES  A list of variables; each is atomic (e.g. int or string).
 DOMAINS  A dict of {var:[possible_value, ...]} entries.
 NEIGHBORS  A dict of {var:[var,...]} that for each variable lists
the other variables that participate in constraints. CONSTRAINTS  A binary function f(A, a, B, b) that returns true if
neighbors A, B satisfy constraint with values A=a, B=b.
# Figure 5.3 page 142
class CSP :
def __init__(self, vars, domains, neighbors, constraints):
self.VARIABLES=vars
self.DOMAINS=domains
self.NEIGHBORS=neighbors
self.CONSTRAINTS=constraints
# 
def BACKTRACKING_SEARCH(csp) :
return RECURSIVE_BACKTRACKING( {}, csp)
def RECURSIVE_BACKTRACKING( assignment, csp) :
if COMPLETE(assignment, csp.VARIABLES ) : return assignment
var = SELECT_UNASSIGNED_VARIABLE( csp.VARIABLES, assignment, csp)
for value in ORDER_DOMAIN_VALUES( var, assignment, csp) :
if CONSISTENT(var, value, assignment, csp.CONSTRAINTS, csp.NEIGHBORS) :
assignment[var]=value
result = RECURSIVE_BACKTRACKING(assignment,csp)
if result != 'failure' : return result
del assignment[var]
return 'failure'
def SELECT_UNASSIGNED_VARIABLE( vars, assignment, csp) :
for var in vars :
if not (var in assignment) : return var
def COMPLETE(assignment, vars) :
for var in vars :
if not (var in assignment) : return False
return True
def ORDER_DOMAIN_VALUES( var, assignment, csp) :
return csp.DOMAINS[var][:]
def CONSISTENT(var, value, assignment, constraints, neighbors) :
if not assignment : return True
for c in constraints.keys() :
for var2 in neighbors[var] :
if var2 in assignment and
not constraints[c](var, value, var2, assignment[var2]) :
return False
return True
def Australia() : # Return a CSP instance of the Map Coloring of Australia.
WA,Q,T,V,SA,NT,NSW = 'WA','Q','T','V','SA','NT','NSW'
values = ['R', 'G', 'B']
vars = [WA, Q, T, V, SA, NT, NSW]
domains = {SA: values[:], WA:values[:], NT:values[:],
Q:values[:], NSW:values[:], V:values[:], T:values[:]}
neighbors = {WA: [SA, NT], Q: [SA, NT, NSW], T: [],V: [SA, NSW],
SA: [WA, NT, Q, NSW, V], NT: [SA, WA, Q], NSW: [SA, Q, V]}
constraints = {SA: constraint, WA:constraint, NT:constraint, Q:constraint,
NSW:constraint, V:constraint, T:constraint}
return CSP(vars, domains, neighbors, constraints)
def constraint(A, a, B, b): # Two neighboring variables must differ in value.
return a != b
def run():
print BACKTRACKING_SEARCH(Australia())Note: Domains are copies (e.g. SA: values[:]) so that modifying one domain will not affect the domain of other variables.
 What is returned by: Australia()?
 What is returned by: BACKTRACKING_SEARCH(Australia())?
 What purpose is the assignment variable below?
 What purpose is the var variable below?
 What purpose is:
for value in ORDER_DOMAIN_VALUES( var, assignment, csp) :
 What would the following do?
if CONSISTENT(Q, red, {NT:blue, NSW:green}, csp.CONSTRAINTS, [NT,SA,NSW]) :
assignment[var]=value
 What is assignment variable now?
 What is the effect of:
del assignment[var]
def RECURSIVE_BACKTRACKING( assignment, csp) :
if COMPLETE(assignment, csp.VARIABLES ) : return assignment
var = SELECT_UNASSIGNED_VARIABLE( csp.VARIABLES, assignment, csp)
for value in ORDER_DOMAIN_VALUES( var, assignment, csp) :
if CONSISTENT(var, value, assignment, csp.CONSTRAINTS, csp.NEIGHBORS) :
assignment[var]=value
result = RECURSIVE_BACKTRACKING(assignment,csp)
if result != 'failure' : return result
del assignment[var]
return 'failure'
Improving backtracking efficiency
 What is the the number of complete assignments for n variables with d values? Australia has 7 variables and 3 values, generally d^{n }
 What is the state space size for n variables with d values?
Consider the search tree nodes produced by the successor function:
0 level  0 variables assigned branching factor is nd since any of the n variables can be assigned any of the d values;
1 level  1 variable is assigned (next level) branching factor is (n1)d, a total of n(n1)d^{2}
2 level  branching factor is (n2)d, a total of n(n1)(n2)d^{3}.
n1 level  branching factor is (n(n1))d, a total of n(n1)(n2)d^{3}*...*d.
State space size is then n!d^{n}
Australia has 7!*3^{7} or 5040*2187=11022480
Consider
 Which variable should be assigned next?
 In what order should the variables be tried?
 Can we detect inevitable failure early?
 Can we take advantage of problem structure?
Most constrained variable or minimum remaining values (MRV)
Idea is that variable with fewest choices will likely fail sooner allowing branch to be pruned early.
Choose the variable with the fewest legal values
Legal values are those that do not conflict with any already assigned to a neighbor (i.e. do not violate constrains).
After WA=red, NT and SA have only 2 remaining legal values, the other unassigned variables all have 3.
Choose between NT and SA.
 After assigning NT=red what some of the possible assignments for neighbors?
 Under MRV, pick a variable and value to assign next after NT=red assigned.
 What are the possible MRV assignments now?
Python minimum remaining values
 SELECT_UNASSIGNED_VARIABLE( vars, assignment, csp)
 Now instead of returning the first unassigned variable, returns the unassigned variable with the minimum remaining values
 num_legal_values(self, var, assignment)
 Returns the number of legal values for var (those that do not violate constraints) given current assignment
 nconflicts(self, var, value, assignment)
 Return number of conflicts for var value with neighbor's values
 countTrue( fn, list)
 Counts the number of true results from applying fn to every element in list.
class CSP :
def __init__(self, vars, domains, neighbors, constraints):
self.VARIABLES=vars
self.DOMAINS=domains
self.NEIGHBORS=neighbors
self.CONSTRAINTS=constraints
def num_legal_values(self, var, assignment): # Number of legal values
def legal(value) : # True if legal value
return self.nconflicts(var, value, assignment) == 0
return countTRUE(legal, self.DOMAINS[var])
def nconflicts(self, var, value, assignment): # Number of conflicts
"Return the number of conflicts var=val has with other variables."
def conflict(var2):
val2 = assignment.get(var2, None) # var=None if not assigned
return val2 != None and not self.CONSTRAINTS[var](var, value, var2, val2)
return countTRUE(conflict, self.NEIGHBORS[var])
def countTRUE( fn, list) : # return the number of fn(v) that are True
n=0
for v in list :
if fn(v) : n=n+1
return ndef SELECT_UNASSIGNED_VARIABLE( vars, assignment, csp) :
mrv={}
for v in vars : # Calculate number of legal values for each
if v not in assignment : # unassigned var
mrv[v]=csp.num_legal_values(v, assignment)
minimum=mrv.keys()[0] # Find var with Minimum Remaining Values
for v in mrv.keys() :
if mrv[v] < mrv[minimum] :
minimum = v
return minimum
Most constraining variable
Choose the variable that constrains the most remaining variables
SA places constrains on 5 variables; WA, NT, Q, V, NSW only on 3, T on 0.
Purpose is to prune early by reducing number of choices.
Tie breaker among minimum remaining variables (MRV)
Least constraining value
Given a variable, choose the least constraining value:
the one that rules out the fewest values in the remaining variables
Idea is to explore paths, those with most options, most likely to lead to a solution.
Forward checking
Keep only legal values in domain for unassigned variables
 Prune illegal values from domain of connected (neighbors) unassigned variables after each assignment
 Backtrack search when any variable has no legal values
 When backtracking to undo an assignment, restore pruned values to domain of connected (neighbors) unassigned variables
Reduces search tree by pruning branches destined to eventually fail due to values that violate constraints in the domains of neighbors
 How far ahead does forward checking look? That is, unassigned immediate neighbors, or unassigned neighbors of unassigned neighbors of ...
 Complete the following using forward checking.
WA NT Q NSW V SA T Domain RGB RGB RGB RGB RGB RGB RGB SA=R V=G WA=B Python forward checking
Basic idea is to prune values from domain of unassigned neighbors of X that conflict with the value just assigned to X, eliminating known inconsistent states from the search space.
assignment[var]=value
csp.forward_check(var, value, assignment)When backtracking occurs, the pruning of neighbors domain must be undone and assignment of variable deleted.
csp.undo_forward_check(var)
del assignment[var]
class CSP : def __init__(self, vars, domains, neighbors, constraints): self.VARIABLES=vars self.DOMAINS=domains self.NEIGHBORS=neighbors self.CONSTRAINTS=constraints self.PRUNED = {} for v in vars: self.PRUNED[v] = [] def forward_check(self, var, val, assignment): # Prune any B=b from unassigned neighbors domain that conflict with var=val for B in self.NEIGHBORS[var]: if B not in assignment: for b in self.DOMAINS[B][:]: if not self.CONSTRAINTS[var](var, val, B, b): self.DOMAINS[B].remove(b) self.PRUNED[var].append((B, b)) def undo_forward_check(self, var) : # Restore prunings from previous value of var for (B, b) in self.PRUNED[var]: self.DOMAINS[B].append(b) self.PRUNED[var] = [] # _____________________________________________________________ def BACKTRACKING_SEARCH(csp) : return RECURSIVE_BACKTRACKING( {}, csp) def RECURSIVE_BACKTRACKING( assignment, csp) : if COMPLETE(assignment, csp.VARIABLES ) : return assignment var = SELECT_UNASSIGNED_VARIABLE( csp.VARIABLES, assignment, csp) for value in ORDER_DOMAIN_VALUES( var, assignment, csp) : if CONSISTENT(var, value, assignment, csp.CONSTRAINTS, csp.NEIGHBORS) : assignment[var]=value csp.forward_check(var, value, assignment) result = RECURSIVE_BACKTRACKING(assignment,csp) if result != 'failure' : return result csp.undo_forward_check(var) del assignment[var] return 'failure' 
Constrain propagation
Forward checking propagates values from assigned to unassigned variables (by pruning neighbors domain) but does not provide early detection of all failures. Only looks at conflicts with immediate neighbors.
Constrain propagation propagates implication of constrains on one variable to others.
Propagating WA=red and Q=green constrains NT and SA to blue; cannot both be blue since adjacent.
Constraint propagation repeatedly enforces constraints locally
Arc consistency
Arc from SA to NSW is consistent because SA (blue) allows NSW (red)
Arc from NSW to SA is not consistent because NSW (blue) does not allow SA (blue)
Can be made consistent by removing blue from NSW domain
After removing blue from NSW, must check neighbors for consistency leading to removal of red from V.
After removing blue, SA domain is {}, pruning SA completely for the two assignments {NSW=red, Q=green} and forcing backtracking.
Is the arc (WA,NSW) consistent?
 Is the arc (NSW,WA) consistent?
 If not, what should be the domain of NSW and WA?
 Is the arc (SA,T) consistent?
 is the arc (T, SA) consistent?
The full tree contains 7!*3^{7 }nodes. With 2 variables assigned {NSW=red, Q=green} lower branches contain how many nodes?
Should any lower branches be expanded for assignment {NSW=red,Q=green}?
Arc consistency algorithm
Note:
 queue would initially be a set of (variable, neighbor) pairs for all variables and their neighbors.
 if (x, y) satisfies the constraint for some value y in DOMAIN[Xj]
means
if (x, y) is inconsistent for every value y in DOMAIN[Xj]
then delete x from DOMAIN[Xi]
removed = true
Chris raised the question: How does AC3 remove any inconsistencies when run as a preprocessing step, when all variables have domain of [R, G, B]? The answer is that there are no inconsistencies since for any x in [R, G, B] there is some y in [R, G, B] that the constraint x!=y is satisfied. AC3 does nothing!
In fact, running as a preprocessing step before backtracking search or after a variable assignment makes no difference, assuming the domains are not changed elsewhere by some other pruning heuristic. With only AC3 changing domains, inconsistencies never occur. Inconsistencies can be created by initially restricting SA=R for example (see Homework 4).
Running AC3 after assignment makes sense only if the domain is restricted to the value assigned, that is if SA=R then domain SA=R. AC3 can then remove any inconsistencies created by the assignment. But when failure occurs and the assignment is removed, the old domains for all variables must be restored. The Python code below implements the BACK_TRACKING_SEARCH with those modifications.
Interestingly, the execution time using AC3 increases BACK_TRACKING_SEARCH due to the overhead of copying the entire original domain of each variable and removing conflicts from starting at the backtracked variable. One solution, not implemented here, would be to keep track of values pruned at each level of backtracking and restore only those.
function AC3( csp ) returns the CSP possibly with reduced domains
local variables: queue, queue of arcs, initially all the arcs in csp
loop while queue is not empty do
(Xi, Xj) = REMOVEFRONT(queue)
if REMOVEINCONSISTENT(Xi, Xj) then # Neighbors may be inconsistent
for each Xk in NEIGHBORS[Xi] do # add to queue to check
add (Xk, Xi) to queuefunction REMOVEINCONSISTENT(Xi, Xj) returns True iff Xi value removed
removed = False
for each x in DOMAIN[Xi] do
if (x, y) is inconsistent for every value y in DOMAIN[Xj]
then delete x from DOMAIN[Xi]
removed = True
return removed
import copy def BACKTRACKING_SEARCH(csp) :
csp.OLD=copy.deepcopy(csp.DOMAINS) # Copy DOMAINS
return RECURSIVE_BACKTRACKING( {}, csp)
def RECURSIVE_BACKTRACKING( assignment, csp) :
if COMPLETE(assignment, csp.VARIABLES ) : return assignment
var = SELECT_UNASSIGNED_VARIABLE( csp.VARIABLES, assignment, csp)
for value in ORDER_DOMAIN_VALUES( var, assignment, csp) :
if CONSISTENT(var, value, assignment, csp.CONSTRAINTS, csp.NEIGHBORS) :
assignment[var]=value
csp.DOMAINS[var]=[value] # Restrict domain
AC3(csp)
result = RECURSIVE_BACKTRACKING(assignment,csp)
if result != 'failure' : return result
csp.DOMAINS=copy.deepcopy(csp.OLD) #Restore DOMAINS
del assignment[var]
return 'failure'
 Representing an arc from NSW to V as (NSW,V), give the starting queue in AC3.
 Restrict the domain of SA=[R] and the remaining variables to [R, G, B]. Record each variables domain while propagating the constraint using AC3 for several queue entries.
O(n^{2}d^{3}) is worst case time but cannot detect all failures in polynomial time.
AC3 checks all neighbors and removes inconsistencies, the effectiveness can be seen when applied to the Australia map coloring.
In conjunction with a backtracking search, AC3 eliminates backtracking yielding a linear search tree with no branches.
Recall that backtracking occurs when all domain values of the assigned variable have been exhausted and no solution was found.
On failure, the variable and value are removed from the list of assigned variables, necessary before backtracking to a previous node in the search tree.
In practice, AC3 can be called one time before calling the backtracking search or each time after assigning a variable a consistent value according to problem constraints.
When backtracking occurs, a branch for a value from a different variable is explored.
Since the effect of AC3 is to remove inconsistent domain values from all connected variables, this prunes search tree branches recognized to eventually lead to failure. Removed values are never explored.
A sideeffect of AC3 is that domains are modified.
Problems
Arc consistency does not reveal every possible inconsistency.
The partial assignment {WA=red, NSW=red} is inconsistent but AC3 will not find it because only considers 2 variables at a time.
 Why is the assignment {WA=red, NSW=red} inconsistent?
1consistent is node consistency, each variable is consistent. WA cannot be pink.
2consistent is arc consistency.
3consistent is path consistency, any pair of adjacent variables can be extended to a third neighboring variable. e.g. (WA,SA,NSW)
kconsistent if for k1 variables and any consistent assignment to those variables, a consistent value can be assigned to kth variable. All k variables can be assigned consistent values.
Strongly kconsistent if k, k1, k2, ..., 1 consistent. Can then solve problem with no backtracking but propagation is still exponential cost.
Iterative algorithms for CSPs
Example 4queens problem
Performance of minconflicts
MINCONFLICTS
Idea:
 Uses hillclimbing seeking values of each variable that minimize the number of conflicts.
 When no conflicts a solution is found.
 May not converge to a solution.
 assignment = initially a value assigned to each variable, could be all the same value, random, etc.
 for i=1 to max_steps
 Determine conflicted variables in assignment.
 if no conflicted variables in assignment then return assignment
 Select one conflicted variable at random
 value = the value for variable that minimizes the number of conflicts
 Change value of variable in assignment
Example: 8queens with number of pairs of conflicts with queens in other columns.
In leftmost figure, column 8 variable changed to row 3 with minimum conflicts value of 1. Since tie in row 3 and 6, choose between them at random.
In next figure, column 6 has been randomly selected and changed to row 8 with minimum conflicts value of 0.
Solution in last figure.
 What is the assignment in the leftmost figure?
 In the rightmost figure?
 What are the problem constraints?
Figure 5.8 page 151 MinConflicts
def MIN_CONFLICTS(csp, max_steps=1000000) :
current = {}; # current assignment all the same
for var in csp.VARIABLES : current[var]=csp.DOMAINS[var][0]
for i in range(max_steps) :
conflicted = csp.conflicted_vars(current) # List of conflicted vars
if not conflicted : return current # Solution
var = conflicted[int(random.uniform(0, len(conflicted)))] # Random conflicted var
val = min_conflicts_value(csp, var, current) # value with minimum conflicts
current[var]=val
return None
def min_conflicts_value(csp, var, current):
"""Return the value giving var the least number of conflicts. Random on tie."""
return argmin(csp.DOMAINS[var],
lambda val: csp.nconflicts(var, val, current))
def argmin(seq, fn) : # Return seq that evaluate to minimum fn(seq[0..n])
min = 0
minvalue = fn(seq[min])
for i in range(len(seq)) :
testvalue = fn(seq[i])
if testvalue == minvalue : # Select randomly when equal
if random.uniform(0, 1) > 0.5 : min = i
if testvalue < minvalue :
min = i
minvalue = testvalue
return seq[min]
def countTRUE( fn, list) :
n=0
for v in list :
if fn(v) : n=n+1
return n
#______________________________________________________________
class CSP :
def __init__(self, vars, domains, neighbors, constraints):
self.VARIABLES=vars
self.DOMAINS=domains
self.NEIGHBORS=neighbors
self.CONSTRAINTS=constraints
def conflicted_vars(self, current):
"Return a list of variables in current assignment that are in conflict"
return [var for var in self.VARIABLES
if self.nconflicts(var, current[var], current) > 0]
def nconflicts(self, var, value, assignment):
"Return the number of conflicts var=val has with other variables."
def conflict(var2):
val2 = assignment.get(var2, None)
return val2 != None and not self.CONSTRAINTS[var](var, value, var2, val2)
return countTRUE(conflict, self.NEIGHBORS[var])
What is the effect of initializing current={WA=R, NT=R,
Q=R, SA=R, NSW=R, V=R, T=R}? What is nconflicts(WA, R, {WA=R, NT=R, Q=R, SA=R, NSW=R, V=R, T=R})? What is conflicted_vars({WA=G, NT=B, Q=G, SA=R, NSW=B, V=G, T=R}) 
Problem structure
Treestructured CSPs
Algorithm for treestructured CSPs
Nearly treestructured CSPs
Summary