# CSCE 420 Lecture 8

Jump to navigation Jump to search

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

## Constraint Satisfaction Problems (CSP)

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

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

Constraint Graph

• Nodes = edges
• Edges = binary constraints

Multivariable Constraints

• Subset of tuples from cross products of all domains: $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.

domains:

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

1. $x+y+z=5$ 2. $x 3. $y We introduce a third variable U to represent the tertiary constraint in (1), and the corresponding constraints with other variables.

1. $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. $x=u_{1}$ 3. $y=u_{2}$ 4. $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