# Chapter 5 Constraint Satisfaction Problems

Modified:

## Outline

• CSP Examples
• Backtracking search for CSPs
• Problem structure and problem decomposition
• Local search for CSPs

## CSP definitions

• Variables - X1, X2,..., Xn each Xi having a non-empty domain Di of possible values.

• Constraints - C1, C2,..., Cm 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 (X1=v1, Xj=vj, ...)

• 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 domain-specific knowledge

Constraint graph - structure used to simplify solution process, sometime exponential reduction over general-purpose search (e.g. depth-first).

## 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.

## Example: Cryptarithmetic

Constraints are square boxes connected to variables it constrains

Order 2 - F, X3

Order 3 - O, R, X1

Order 6 - F, T, U, W, R, O

O + O = R + 10 * X1

X1 + W + W = U + 10 * X2

X2 + T + T = O + 10 * X3

X3 = F

where X1, X2 and X1  are auxiliary variables representing the 0 or 1 carry.

 What are some of the constraints on F? on X3 ? What is the domain of X1, X2, X3? What are some valid successor states involving T and O for the assignment {F=0}?

Other, real-world 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 real-world problems involve real-valued variables

## 5.2 BACKTRACKING SEARCH FOR CSPs

 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}?

Binary CSP specified by four inputs:

1. VARIABLES      - A list of variables; each is atomic (e.g. int or string).
2. DOMAINS         - A dict of {var:[possible_value, ...]} entries.
3. NEIGHBORS     - A dict of {var:[var,...]} that for each variable lists
the other variables that participate in constraints.
4. 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 dn

• 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 (n-1)d, a total of n(n-1)d2

2 level - branching factor is (n-2)d, a total of n(n-1)(n-2)d3.

n-1 level - branching factor is (n-(n-1))d, a total of n(n-1)(n-2)d3*...*d.

State space size is then n!dn

Australia has 7!*37 or 5040*2187=11022480

Consider

1. Which variable should be assigned next?
2. In what order should the variables be tried?
3. Can we detect inevitable failure early?
4. 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

1. SELECT_UNASSIGNED_VARIABLE( vars, assignment, csp)
• Now instead of returning the first unassigned variable, returns the unassigned variable with the minimum remaining values
2. num_legal_values(self, var, assignment)
• Returns the number of legal values for var (those that do not violate constraints) given current assignment
3. nconflicts(self, var, value, assignment)
• Return number of conflicts for var value with neighbor's values
4. 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

1. Prune illegal values from domain of connected (neighbors) unassigned variables after each assignment
2. Backtrack search when any variable has no legal values
3. 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!*37 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) = REMOVE-FRONT(queue)        if REMOVE-INCONSISTENT(Xi, Xj) then     # Neighbors may be inconsistent           for each Xk in NEIGHBORS[Xi] do          # add to queue to check              add (Xk, Xi) to queue function REMOVE-INCONSISTENT(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 copydef 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(n2d3) 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 side-effect 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?

1-consistent is node consistency, each variable is consistent. WA cannot be pink.

2-consistent is arc consistency.

3-consistent is path consistency, any pair of adjacent variables can be extended to a third neighboring variable. e.g. (WA,SA,NSW)

k-consistent if for k-1 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 k-consistent if k, k-1, k-2, ..., 1 consistent. Can then solve problem with no backtracking but propagation is still exponential cost.

## Example 4-queens problem

Performance of min-conflicts

MIN-CONFLICTS

Idea:

• Uses hill-climbing seeking values of each variable that minimize the number of conflicts.
• When no conflicts a solution is found.
• May not converge to a solution.
1. assignment = initially a value assigned to each variable, could be all the same value, random, etc.
2. for i=1 to max_steps
1. Determine conflicted variables in assignment.
2. if no conflicted variables in assignment then return assignment
3. Select one conflicted variable at random
4. value = the value for variable that minimizes the number of conflicts
5. Change value of variable in assignment

Example: 8-queens 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 Min-Conflicts

 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})