Notes on Chapter 6: Constraint Satisfaction Problems

Constraint satisfaction problems, or CSPs for short, are a flexible approach to searching that have proven useful in many AI-style problems

CSPs can be used to solve problems such as

  • graph-coloring: coloring a graph means assigning each of its vertices a color such that no pair of vertices connected by an edge have the same color
    • in general, this is a hard problem, e.g. determining if a graph can be colored with 3 colors is NP-hard
    • many practical problems in topics such as scheduling or logistics boil down to graph coloring, or related problems
  • job shop scheduling: e.g. suppose you need to complete a set of tasks, each of which have a duration, and constraints upon when they start and stop (e.g. task c can’t start until both task a and task b are finished)
    • CSPs are a natural way to express such problems
  • cryptarithmetic puzzles: e.g. suppose you are told that TWO + TWO = FOUR, and each letter corresponds to a different digit from 0 to 9, and that a number can’t start with 0 (so T and F are not 0); what, if any, are the possible values for the letters that make the equation true?
    • one solution: 734 + 734 = 1468
    • while these are not directly useful problems, they are a simple test case for CSP solvers

a CSP consists of three main components:

  • \(X\): a set of variables \(\{X_1, \ldots, X_n\}\); a variable can be assigned at most one value, and it is possible for a variable to be unassigned
  • \(D\): a set of domains \(\{D_1, \ldots, D_n\}\), one domain per variable
    • i.e. the domain of \(X_i\) is \(D_i\), which means that \(X_i\) can only be assigned values from \(D_i\)
    • you can certainly have CSPs with infinite domains (e.g. real numbers), but we’re only going to consider finite domains
  • \(C\) is a set of constraints that specify allowable assignments of values to variables; since our domains are all finite, constraints can be thought of as mathematical relations
    • for example, a binary constraint consists of a pair of different variables, \((X_i, X_j)\), and a set of pairs of values that \(X_i\) and \(X_j\) can take on at the same time
    • we will usually only deal with binary constraints; constraints between three or more variables are possible (e.g. \(X_i, X_j, X_k\) are all different), but they don’t occur too frequently, and can be decomposed into binary constraints

example 1: suppose we have a CSP as follows:

  • three variables \(X_1\), \(X_2\), and \(X_3\)

  • domains: \(D_1=\{1, 2, 3, 4\}\), \(D_2=\{2, 3, 4\}\), \(D_3=\{3, 7\}\)

    • so \(X_1\) can only be assigned one of the values 1, 2, 3, or 4

  • constraints: no pair of variables have the same value, i.e. \(X_1 \neq X_2\), \(X_1 \neq X_3\), and \(X_2 \neq X_3\); we can explicitly describe each of these constraints as a relation between the two variables where the pairs show the allowed values that the variables can be simultaneously assigned, i.e.

    • \(X_1 \neq X_2 = \{ (1,2), (1,3), (1,4), (2,3), (2,4), (3,2), (3,4), (4,2), (4,3) \}\)
    • \(X_1 \neq X_3 = \{ (1,3), (1,7), (2,3), (2,7), (3,7), (4,3), (4,7) \}\)
    • \(X_2 \neq X_3 = \{ (2,3), (2,7), (3,7), (4,3), (4,7) \}\)

    these three constraints are each binary constraints because they each constrain 2 variables

example 2: suppose we have the same variables and domains as in the previous example, but now the constraints are \(X_1 < X_2\) and \(X_2 + X_3 \leq 5\)

  • domains: \(D_1=\{1, 2, 3, 4\}\), \(D_2=\{2, 3, 4\}\), \(D_3=\{3, 7\}\)
  • both of the constraints are binary constraints, because they each involve two variables
  • \(X_1 < X_2 = \{ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) \}\)
  • \(X_2 + X_3 \leq 5 = \{ (2,3) \}\)

by looking at the constraints for this problem, we note the following:

  • since there is only one pair of allowable values in the constraint \(X_2 + X_3 \leq 5 = \{ (2,3) \}\), it must be that \(X_2=2\) and \(X_3=3\)
  • since \(X_2=2\), in the constraint for \(X_1 < X_2\) we can discard all pairs whose second item is not 2; this leaves just the pair \((1,2)\), which means \(X_1=1\)
  • so the final solution to this CSP is: \((X_1=1, X_2=2, X_3=3)\)

example 3: suppose we have the same variables and domains as in the previous example, but now with the two constraints \(X_1 + X_2 = X_3\), and \(X_1\) is even

  • domains: \(D_1=\{1, 2, 3, 4\}\), \(D_2=\{2, 3, 4\}\), \(D_3=\{3, 7\}\)
  • \(X_1 + X_2 = X_3\) is a ternary constraint, because it involves 3 variables
  • \(X_1 + X_2 = X_3 = \{ (1,2,3), (3,4,7), (4,3,7) \}\)
  • \(X_1\) is even is a unary constraint, because it involves one variable
  • \(X_1\) is even \(= \{ 2, 4 \}\)
  • looking at the triples in \(X_1 + X_2 = X_3\), the only one where X_1 is even is \((4,3,7)\), and so the only solution to his problem is \((X_1=4, X_2=3, X_3=7)\)

Some Terminology and Basic Facts

  • variables can be assigned, or unassigned
  • if a CSP has some assigned variables, and those assignments don’t violate any constraints, we say the CSP is consistent, or that it is satisfied
    • that partial sets of CSP variables can be satisfied is an important part of many CSP algorithms that work by satisfying one variable at a time
  • if all the variables of a CSP are assigned a value, we call that a complete assignment
  • a solution to a CSP is a complete assignment that is consistent, i.e. a complete assignment that does not violate any constraints
  • depending on the constraints, a CSP may have 0, 1, or many solutions
    • a CSP with no solutions is over-constrained
    • a CSP with many solutions is under-constrained
  • depending upon the problem being solved and its application, we may want just 1 solution, or we might want multiple solutions
    • for over-constrained CSPs, we may even be satisfied with a solution that violates the fewest constraints
  • if a domain is empty, then the CSP is no solution
  • if a domain has only one value, then that is the only possible value for the corresponding variable
  • the size of the search space for a CSP is \(|D_1| \cdot |D_2| \cdot \ldots \cdot |D_n|\)
    • this is the number of n-tuples that the CSP is searching through
    • this is often a quick and easy way to estimate the potential difficulty of a CSP: the bigger the search space, the harder the problem might be
      • this is just a rule of thumb: it’s quite possible that a problem with a large search space is easier than a problem with a small search space, perhaps because there are many more solutions to be found in the large search space

Constraint Propagation: Arc Consistency

as mentioned above, we are only considering CSPs with finite domains, and binary constraints between variables

it turns out that many such CSPs can be efficiently translated into a simpler CSP that is guaranteed to have the same solutions

the idea we will consider here is called arc consistency

the CSP variable \(X_i\) is said to be arc consistent with respect to variable \(X_j\) if for every value in \(D_i\) there is at least one corresponding value in \(D_j\) that satisfies the binary constraint on \(X_i\) and \(X_j\)

an entire CSP is said to be arc consistent if every variable is arc consistent with every other variable

if a CSP is not arc consistent, then it turns out that there are relatively efficient algorithms that will make it arc consistent

  • and the resulting arc consistent CSP will have the same solutions as the original CSP, but often a smaller search space
  • in some cases, making a CSP arc consistent may be all that is necessary to solve it

the most popular arc consistency algorithm as AC-3

  • on a CSP with \(c\) constraints a maximum domain size of \(d\), AC-3 runs in \(O(cd^3)\) time
function AC-3(csp)
  returns: false is an inconsistency is found
           true otherwise
           csp is modified to be arc-consistent
  input: CSP with components (X, D, C)
  local variables: queue of arcs (edges) in
                   the CSP graph

  queue <-- all arcs in csp
  while queue is not empty do
    (X_i, X_j) <-- queue.pop_first()
    if Revise(csp, X_i, X_j) then
      if size(D_i) == 0 then return false
      for each X_k in neighbors(X_i) - {X_j} do
        add (X_k, X_i) to queue
      end for
    end if
  end while
  return true


function Revise(csp, X_i, X_j)
  returns true iff domain D_i has been changed

  revised <-- false
  for each x in D_i do
    if no value y in D_j allows (x,y) to satisfy
         the constraint between X_i and X_j then
      delete x from D_i
      revised <-- true
  end for
  return revised

example. Consider the following CSP with variables A, B, C, and D, and:

D_A = {1, 2, 3}
D_B = {2, 4}
D_C = {1, 3, 4}
D_D = {1, 2}

A < B
A < D
B = D
B != C
C != D

it’s useful to draw the corresponding constraint graph, and then to apply AC-3 to that by hand to see how the domains change

in this particular problem, AC-3 reduces 3 of the 3 domains down to a single value

here’s an implementation using the csp.py program from the textbook:

import csp

vbls  = ['A', 'B', 'C', 'D']
doms  = {'A':[1,2,3], 'B':[2,4], 'C':[1,3,4], 'D':[1,2]}
neigh = {'A':['B','D'], 'B':['A','C','D'],
         'C':['B','D'], 'D':['A','B','C']}
cnstr = {
  ('A','B'): lambda x,y: x < y,
  ('B','A'): lambda x,y: x > y,

  ('A','D'): lambda x,y: x < y,
  ('D','A'): lambda x,y: x > y,

  ('B','D'): lambda x,y: x == y,
  ('D','B'): lambda x,y: x == y,

  ('B','C'): lambda x,y: x != y,
  ('C','B'): lambda x,y: x != y,

  ('C','D'): lambda x,y: x != y,
  ('D','C'): lambda x,y: x != y,
}

# If X=a and Y=b satisfies the constraints on X and Y, then True is returned.
# Otherwise,. False is returned.
def constraints(X, a, Y, b):
  try:
    return cnstr[(X,Y)](a,b)
  except KeyError:  # if a pair is not in the table, then there are no constraints
    return True     # on X an Y, and so X=a and Y=b is acceptable


prob = csp.CSP(vbls, doms, neigh, constraints)

if __name__ == '__main__':
  print('Problem domains before AC3 ...')
  print(prob.domains)

  csp.AC3(prob)

  print()
  print('Problem domains after AC3 ...')
  print(prob.curr_domains)

Local Search: Min-conflicts

backtracking search solves a CSP by assigning one variable at a time

another approach to solving a CSP is to assign all the variables, and then modify this assignment to make it better

this is a kind of local search on CSPs, and for some problems it can be extremely effective

example: 4-queens problem

  • place 4 queens randomly on a 4-by-4 board, one queen per column
  • pick a queen, and re-position it in its column so that it is attacking the fewest number of other queens; this is know as the min-conflicts heuristic
  • repeat the previous step until there are no possible moves that reduce conflicts; if the puzzle is solved, then you’re done; if it’s not solved, then re-start the entire process with a new initial random placement of queens

local search using min-conflicts can be applied to any CSP as follows:

function Min-Conflicts(csp, max_steps)
    returns: solution, or failure
    Inputs: csp, a constraint satisfaction problem
            max_steps, number of steps allowed before giving up

current <-- an initial complete assignment for CSP
for i = 1 to max_steps do
  if current is a solution, then return current
  var <-- randomly chosen conflicted variable from csp.VARIABLES
  value <-- the value v for var that minimizes CONFLICTS(var, v, current, csp)
  set var = value in current
end

the CONFLICTS functions returns the count of the number of variables in the rest of the assignment that violate a constraint when var=v

a tailored version of Min-Conflicts can solve the n-queens problem for n=3 million in less than a minute (on 1990s computers!)

  • this is was a surprise — it’s not obvious that min-conflicts will work so well on this problem

we will not cover anything from section 6.5