4 min read
On this page

Constraint Satisfaction Problems

A CSP consists of variables, domains, and constraints. The goal is to find an assignment of values to variables that satisfies all constraints.

CSP Formulation

Variables: X₁, X₂, ..., Xₙ. Domains: D₁, D₂, ..., Dₙ (possible values for each variable). Constraints: C₁, C₂, ..., Cₘ (relationships between variables that must hold).

Examples

Map coloring: Variables = regions. Domains = {red, green, blue}. Constraints = adjacent regions have different colors.

Sudoku: Variables = 81 cells. Domains = {1-9}. Constraints = all-different per row, column, and 3×3 box.

Scheduling: Variables = tasks. Domains = time slots. Constraints = resource limits, precedences, preferences.

Constraint Types

Unary: Restricts a single variable. "X₁ ≠ red."

Binary: Restricts pairs. "X₁ ≠ X₂." Most constraints can be converted to binary.

Global: Involves multiple variables. all_different(X₁,...,Xₙ) — all must have distinct values. Specialized propagation algorithms exist.

Constraint Propagation

Reduce domains by inferring consequences of constraints before searching.

Node Consistency

Each value in a variable's domain satisfies all unary constraints on that variable. Remove values that violate unary constraints.

Arc Consistency (AC-3)

For every value in Xᵢ's domain, there exists a supporting value in Xⱼ's domain for every constraint between Xᵢ and Xⱼ. Remove unsupported values.

AC-3 Algorithm:
  Queue = all arcs (Xᵢ, Xⱼ)
  While queue not empty:
    (Xᵢ, Xⱼ) = dequeue
    If REVISE(Xᵢ, Xⱼ) removed values from Dᵢ:
      If Dᵢ is empty: return FAILURE (no solution)
      Add all arcs (Xₖ, Xᵢ) for k ≠ j to queue

REVISE(Xᵢ, Xⱼ):
  For each value v in Dᵢ:
    If no value w in Dⱼ satisfies constraint(Xᵢ=v, Xⱼ=w):
      Remove v from Dᵢ

Time: O(ed³) where e = number of arcs, d = max domain size. Typically very fast.

Path Consistency

Extends arc consistency to triples of variables. More powerful but more expensive. Rarely used directly.

Maintaining Arc Consistency (MAC)

Run AC-3 after each assignment during backtracking search. The standard combination in practice.

Systematic search through assignments. Assign one variable at a time. Backtrack when a constraint is violated.

BACKTRACKING-SEARCH(assignment):
  If assignment is complete: return assignment
  var = SELECT-UNASSIGNED-VARIABLE()
  For each value in ORDER-DOMAIN-VALUES(var):
    If value is consistent with assignment:
      Add {var = value} to assignment
      inferences = INFERENCE(var, value)  // e.g., MAC
      If inferences ≠ failure:
        result = BACKTRACKING-SEARCH(assignment)
        If result ≠ failure: return result
      Remove inferences and {var = value}
  return failure

Variable and Value Ordering

Variable Ordering (which variable to assign next?)

MRV (Minimum Remaining Values / fail-first): Choose the variable with the fewest legal values. Detects failure earlier — if a variable has 0 values, fail immediately.

Degree heuristic (tie-breaker): Among MRV ties, choose the variable involved in the most constraints on unassigned variables. Constrains the remaining problem most.

Value Ordering (which value to try first?)

LCV (Least Constraining Value): Choose the value that rules out the fewest choices for neighboring variables. Maximizes remaining flexibility. Doesn't affect completeness (all values are tried eventually).

Constraint Learning (Nogood Recording)

When backtracking, record the reason for failure as a new constraint (nogood).

If {X₁=red, X₃=blue} leads to failure:
  Add constraint: NOT(X₁=red AND X₃=blue)
  → Future search avoids this combination

Conflict-directed backjumping: Instead of backtracking to the previous variable, jump back to the variable that caused the conflict.

Local Search for CSPs

Min-Conflicts

Start with a complete (possibly invalid) assignment. Repeatedly pick a conflicting variable and change it to the value that minimizes conflicts.

INITIAL: random complete assignment
REPEAT:
  Pick a variable with constraint violations
  Set it to the value minimizing the number of violated constraints
  If no violations: return solution

Performance: Surprisingly effective. Solves the million-queens problem in ~50 steps! Works well when solutions are densely distributed in the space.

Random restart: If stuck, restart with a new random assignment.

Structured CSPs

Tree-Structured CSPs

If the constraint graph is a tree (no cycles), the CSP can be solved in O(nd²) time — linear in the number of variables!

Algorithm: Choose a root. Process variables from leaves to root (arc consistency). Then assign values from root to leaves.

Cutset Conditioning

Find a cutset — a set of variables whose removal makes the constraint graph a tree. Try all assignments for the cutset, then solve the remaining tree CSP.

Time: O(d^c · n · d²) where c = cutset size. Efficient if the cutset is small.

Tree Decomposition

Decompose the constraint graph into a tree of clusters. Solve each cluster, then combine. Efficient if the treewidth is small.

Applications in CS

  • Scheduling: University timetabling, airline crew scheduling, project management.
  • Configuration: Product configuration (which components are compatible?), network design.
  • Puzzle solving: Sudoku, crosswords, KenKen.
  • Verification: Hardware verification, model checking (bounded model checking uses SAT/CSP).
  • Resource allocation: Frequency assignment, register allocation, VLSI layout.
  • AI planning: Planning as CSP — variables = actions, constraints = preconditions and effects.