Chapter 5
Constraint Satisfaction Problems

Outline

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

5.1 CONSTRAINT SATISFACTION PROBLEMS

CSP definitions

Variables - X₁, X₂,..., X_n each X_ihaving a non-empty domain D_i of possible values.

Constraints - C₁, C₂,..., 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₁=v₁, 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 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.

Varieties of CSPs

Varieties of constraints

Example: Cryptarithmetic

Constraints are square boxes connected to variables it constrains

Order 2 - F, X₃

Order 3 - O, R, X₁

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

O + O = R + 10 * X₁

X₁ + W + W = U + 10 * X₂

X₂ + T + T = O + 10 * X₃

X₃ = F

where X_1,X₂ and X₁ are auxiliary variables representing the 0 or 1 carry.

What are some of the constraints on F?

on X₃ ?

What is the domain of X₁, X₂, X₃?

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

Standard search formulation

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

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ⁿ

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)d²

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

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

State space size is then n!dⁿ

Australia has 7!*3⁷ 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 n
def 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⁷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 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²d³) 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.

5.3 LOCAL SEARCH FOR CONSTRAINT SATISFACTION PROBLEMS

Iterative algorithms for CSPs

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.

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

5.4 THE STRUCTURE OF PROBLEMS

Problem structure

Tree-structured CSPs

Algorithm for tree-structured CSPs

Nearly tree-structured CSPs

Summary

Chapter 5 Constraint Satisfaction Problems

Outline

5.1 CONSTRAINT SATISFACTION PROBLEMS

CSP definitions

CSP formulation

Example: Map coloring

One Solution

Constraint graph

Benefit of CSPs

CSP search formulation

Varieties of CSPs

Varieties of constraints

Example: Cryptarithmetic

Standard search formulation

5.2 BACKTRACKING SEARCH FOR CSPs

Backtracking example

Python Constraint Satisfaction Problem solution (Download)

Improving backtracking efficiency

Most constrained variable or minimum remaining values (MRV)

Most constraining variable

Least constraining value

Forward checking

Constrain propagation

Arc consistency

Arc consistency algorithm

5.3 LOCAL SEARCH FOR CONSTRAINT SATISFACTION PROBLEMS

Iterative algorithms for CSPs

Example 4-queens problem

Figure 5.8 page 151 Min-Conflicts

5.4 THE STRUCTURE OF PROBLEMS

Problem structure

Tree-structured CSPs

Algorithm for tree-structured CSPs

Nearly tree-structured CSPs

Summary

Chapter 5
Constraint Satisfaction Problems