# CSCE 420 Lecture 8

« previous | Thursday, February 7, 2013 | next »

## Constraint Satisfaction Problems (CSP)

• Set of variables, say ${\displaystyle x_{1}}$ through ${\displaystyle x_{n}}$
• finite domains, say ${\displaystyle \{v_{1},\ldots ,v_{m}\}}$
• constraints: limits on combinations of choices:
• ${\displaystyle x_{1}=2x_{2}}$
• ${\displaystyle x_{i}\neq x_{j}}$
• ${\displaystyle x_{1}}$ is even, i.e. ${\displaystyle x_{1}\equiv 0{\pmod {2}}}$

Extensional definition of binary constraints

• Involves ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}}$
• Allowed combinations is a subset of dom(${\displaystyle x_{i}}$) × dom(${\displaystyle x_{j}}$)

Constraint Graph

• Nodes = edges
• Edges = binary constraints

Multivariable Constraints

• Subset of tuples from cross products of all domains: ${\displaystyle C\subset \prod _{j=1}^{m}\mathrm {dom} (x_{j})}$

### Converting Multivariable Constraints to Binary Constraints

If a constraint depends on more than two variables, we introduce a new variable whose domain consists of tuples. Each component corresponds to a variable, and the values represent consistent combinations of the domain of other variables.

Edges specify dependence of elements with their target variables.

#### Example

Given the constraint satisfaction problem among X, Y, and Z, we introduce another variable U with domain dom(U) ⊆ dom(X) × dom(Y) × dom(Z). The resulting binary constraint graph is visible at right.

Binary constraint graph for this example

domains:

• ${\displaystyle x\in \{1,2,3\}}$
• ${\displaystyle y\in \{1,2,3\}}$
• ${\displaystyle z\in \{1,2,3\}}$

constraints:

1. ${\displaystyle x+y+z=5}$
2. ${\displaystyle x
3. ${\displaystyle y

We introduce a third variable U to represent the tertiary constraint in (1), and the corresponding constraints with other variables.

1. ${\displaystyle u\in \left\{(x,y,z)~\mid ~x,y,z\in \{1,2,3\},\ x+y+z=5\right\}=\left\{(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1)\right\}}$
2. ${\displaystyle x=u_{1}}$
3. ${\displaystyle y=u_{2}}$
4. ${\displaystyle z=u_{3}}$

### Map Coloring

No adjacent regions can have the same color

Australia, for example, has the following states:

• Western Australia
• Northern Territory
• Victoria
• New South Wales
• South Australia
• Tasmania
• Queensland

Variables are states: { WA, NT, V, NSW, SA, T, Q }
Domain of each variable is colors: { R, G, B }

Extensional binary constraints:

• WA ≠ NT: { (R,G), (R,B), (G,R), (G,B), (B,R), (B,G) }

### Sudoku

No digits may be repeated in any row, column, or section

Variables are cells
Domain of each cell is digits 0–9

### Other Problems

• Crossword Puzzles
• Time scheduling

## CSP Algorithms

Search space = partial assignments. Goal is a set of complete assignments (all variables have a value) that satisfies all constraints

Operator: choose value for unassigned variable

• When generating children, we can see whether chosen assignment violates constraints and prune that part of the decision tree.

### Back Tracking

def backtrack(csp, assignment = {})
# check completeness of assignment
return assignment if assignment.size == csp.vars.size and csp.constraints.all { |c| c(assignment) }

# select variable
var = (csp.vars - assignment.keys).sample

csp.domain[var].each do |value|
if csp.constraints.all { |constraint| constraint(assignment) }
assignment[var] = value
result = bt(csp, assignment)
return result if result
assignment.delete(var)
end
end

# return failure if no assignments were found
false
end


Not very efficient

### Next Time

• Minimum remaining values (MRV)
• Least constraining value (LCV)
• Forward Checking