CSP Formulation and Examples

What is a CSP?

A Constraint Satisfaction Problem (CSP) replaces the atomic state of classical search with a factored representation: a set of variables, each with a domain of possible values, subject to constraints. This structure lets general-purpose inference algorithms exploit the problem’s internal anatomy rather than treating it as a black box.

Formal definition: A CSP is a triple (X, D, C):

A solution is a complete, consistent assignment: every variable has a value from its domain and every constraint is satisfied.

Key Definitions

• Assignment: a mapping from some subset of variables to values.
• Partial assignment: assigns only some variables.
• Complete assignment: assigns all variables.
• Consistent (legal) assignment: no constraint is violated.
• Solution: a complete, consistent assignment.

Constraint Types

By Arity

By Hardness

• Hard constraints: must be satisfied.
• Soft constraints (preferences): should be satisfied; violations incur a cost. Used in constraint optimization problems (COPs).

The Constraint Graph

For binary CSPs, a constraint graph has: - Nodes: variables - Edges: binary constraints between pairs

    WA ── NT ── Q
    |  ╲  |  ╱  |
    SA   SA   SA
    |  ╱  |  ╲  |
    V  ── NSW ── T  (Tasmania is isolated)

The graph structure encodes independence and guides decomposition algorithms (tree-structured CSPs, cutset conditioning, tree decomposition).

Five Standard Examples

1. Map Coloring (Australia)

• Variables: WA, NT, Q, NSW, V, SA, T
• Domains: {red, green, blue}
• Constraints: Adjacent regions must differ — 9 binary constraints
• Insight: SA is adjacent to every mainland region → very constrained → good candidate for MRV heuristic

2. Cryptarithmetic (SEND + MORE = MONEY)

• Variables: S, E, N, D, M, O, R, Y, X₁, X₂, X₃ (carry bits)
• Domains: {0–9} for letters; {0,1} for carries
• Constraints: Column arithmetic equations + Alldiff(S,E,N,D,M,O,R,Y) + S≠0, M≠0
• Insight: Auxiliary carry variables convert a non-binary problem into a binary-ish one

3. N-Queens

• Variables: Q₁, …, Qₙ (queen in column i)
• Domains: {1, …, n} (row positions)
• Constraints: No two queens on same row: Qᵢ ≠ Qⱼ; no diagonal: |Qᵢ − Qⱼ| ≠ |i − j|
• Insight: Dense constraints; local search (min-conflicts) works remarkably well

4. Sudoku

• Variables: 81 cells
• Domains: {1–9}
• Constraints: Alldiff over each row, column, 3×3 box (27 Alldiff constraints)
• Insight: Constraint propagation alone solves most published puzzles

5. Job-Shop Scheduling

• Variables: start times for each job/machine step
• Domains: integer time slots
• Constraints: Precedence (job ordering), no-overlap (one machine at a time), deadlines
• Insight: Practical industrial application; hybrid CP + OR solvers dominate

Why CSP Formulation is Powerful

Classical search treats a state as atomic. CSP formulation: 1. Enables inference — arc consistency, MAC prune domains before and during search 2. Enables smart ordering — MRV, degree heuristic exploit structure 3. Enables decomposition — tree-structured subproblems solvable in polynomial time 4. Generalizes — planning, scheduling, design configuration all map naturally to CSPs

Relation to Other AI Topics