4 Constraint Satisfaction

CS 188 — Constraint Satisfaction Problems

Search: Planning vs. Identification

Planning (search so far)

• The path to the goal is what matters
• Paths have various costs and depths
• Heuristics give problem-specific guidance
• Assumptions: single agent, deterministic actions, fully observed state, discrete state space

Identification (CSPs)

• The goal itself is what matters, not the path
• All solutions are complete assignments at the same depth
• CSPs are a specialized class of identification problems

Example: solving a Rubik's cube — we care about the final state that passes the goal test, not how we got there.

---

What is a CSP?

Standard search problems treat state as a black box — goal test and successor function can be anything.

CSPs are a special subset where:

• State is defined by variables \(X_i\) with values from a domain \(D\)
• Goal test is a set of constraints specifying allowable combinations of values for subsets of variables

This gives us a simple, formal representation language that general-purpose algorithms can exploit.

---

Examples

Map Coloring (Australia)

• Variables: 7 territories (WA, NT, Q, NSW, V, SA, T)
• Domain: {red, green, blue}
• Constraints:
  • Implicit: \(WA \neq NT\), \(WA \neq SA\), …
  • Explicit: \((WA, NT) \in {(r,g),(r,b),(g,r),(g,b),(b,r),(b,g)}\)
• Solution: any complete, constraint-satisfying coloring

N-Queens

Formulation 1 — binary domain per square:

• Variables: \(X_{ij}\) for each square
• Domain: \({0, 1}\)
• Constraints: no two queens share a row, column, or diagonal; \(\sum_{i,j} X_{ij} = N\)

Formulation 2 — one variable per column (cleaner):

• Variables: \(Q_k\) = row of queen in column \(k\)
• Domain: \({1, 2, \dots, N}\)
• Constraints: \(\forall i \neq j\), \((Q_i, Q_j)\) is non-threatening

Cryptarithmetic

  T W O
+ T W O
-------
F O U R

• Variables: \(T, W, O, F, U, R, X_1, X_2, X_3\) (carry bits)
• Domain: \({0\text{–}9}\)
• Constraints:
  • All letters take distinct digits
  • \(O + O = R + 10 \cdot X_1\)
  • \(W + W + X_1 = U + 10 \cdot X_2\)
  • \(T + T + X_2 = O + 10 \cdot X_3\)
  • \(X_3 = F\)

Sudoku, Waltz Algorithm

• Sudoku: each cell is a variable, domain \({1\text{–}9}\), constraints on rows/cols/boxes
• Waltz Algorithm: early AI CSP — interpret line drawings of polyhedra as 3D objects. Each intersection is a variable; adjacent intersections are constraints.

---

Constraint Graph

• Binary CSP: each constraint relates at most two variables
• Boolean CSP: variables are only true/false
• Binary constraint graph: nodes = variables, arcs = constraints
• General-purpose CSP algorithms use graph structure to speed up search (e.g. Tasmania is an independent subproblem → solve separately)

---

Varieties of CSPs

Discrete variables:

• Finite domains — \(O(d^n)\) complete assignments; Boolean SAT is NP-complete
• Infinite domains (integers, strings) — job scheduling; linear constraints solvable

Continuous variables:

• e.g. Hubble telescope observation scheduling
• Linear constraints solvable in polynomial time via LP

Constraint types:

• Unary — single variable: \(SA \neq \text{green}\)
• Binary — pairs: \(SA \neq WA\)
• Higher-order — 3+ variables
• Soft/preference constraints — optimization rather than hard satisfaction

Real-world CSPs: scheduling, timetabling, assignment problems, hardware configuration, transportation, medical diagnosis, …

---

Solving CSPs

Search formulation:

• State = partial assignment (values assigned so far)
• Initial state = empty assignment \({}\)
• Successor = assign a value to one unassigned variable
• Goal test = assignment is complete and satisfies all constraints

Why not BFS/DFS naively?

• BFS sweeps over all partial assignments level by level — explodes in complexity immediately
• Naive DFS assigns blindly without checking constraints until the end — takes forever

---

Backtracking Search

The standard uninformed algorithm for CSPs. Two key ideas:

1. One variable at a time — variable assignments are commutative, so fix an ordering. Only assign one variable per step.
2. Check constraints as you go — only consider values consistent with prior assignments ("incremental goal test")

function BACKTRACKING-SEARCH(csp):
    return RECURSIVE-BACKTRACKING({}, csp)

function RECURSIVE-BACKTRACKING(assignment, csp):
    if assignment is complete: return assignment
    var ← SELECT-UNASSIGNED-VARIABLE(csp, assignment)
    for value in ORDER-DOMAIN-VALUES(var, assignment, csp):
        if value is consistent with assignment:
            add {var = value} to assignment
            result ← RECURSIVE-BACKTRACKING(assignment, csp)
            if result ≠ failure: return result
            remove {var = value} from assignment
    return failure

---

Filtering

Forward Checking

• Track domains for all unassigned variables
• When a value is assigned, cross off values in neighboring variables' domains that now violate a constraint
• Detects failures early — if any domain goes empty, backtrack immediately

Arc Consistency

An arc \(X \to Y\) is consistent iff for every value \(x\) in \(X\)'s domain, there exists some value \(y\) in \(Y\)'s domain that satisfies the constraint.

REMEMBER! Always delete from the tail.

AC-3 algorithm:

• Enforce consistency on all arcs
• If \(X\) loses a value, re-check all arcs pointing into \(X\) — neighbors may now have values that are no longer supported
• Can run as a preprocessor or after each assignment
• Detects failures earlier than forward checking alone

Downside: enforcing full arc consistency is more expensive per step — \(O(n^2 d^3)\) in the worst case.