# CSCE 420 Lecture 8

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

## Contents

## Constraint Satisfaction Problems (CSP)

- Set of variables, say through
- finite domains, say
- constraints: limits on combinations of choices:
- is even, i.e.

Extensional definition of binary constraints

- Involves and
- Allowed combinations is a subset of dom() × dom()

Constraint Graph

- Nodes = edges
- Edges = binary constraints

Multivariable Constraints

- Subset of tuples from cross products of all domains:

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

constraints:

We introduce a third variable `U`

to represent the tertiary constraint in (1), and the corresponding constraints with other variables.

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