## Definition A **Constraint Satisfaction Problem (CSP)** is a triple $\langle X, D, C \rangle$: - $X = \{x_1, \dots, x_n\}$ — a set of variables. - $D = \{D_1, \dots, D_n\}$ — domains, one per variable, listing allowed values. - $C = \{c_1, \dots, c_m\}$ — constraints, each restricting the values some subset of variables can simultaneously take. A **solution** is an assignment $x_i \to v_i \in D_i$ for every $i$ that satisfies every constraint. ## Why CSPs Matter CSPs are a uniform formulation for combinatorial problems that admit *structural* algorithms beyond brute search. Examples: - **Map colouring** — adjacent regions must differ in colour. - **Sudoku** — 81 variables with domain $\{1,\dots,9\}$ and AllDifferent constraints. - **Scheduling** — tasks with precedence, resource, and time-window constraints. - **Cryptarithmetic** — letter-to-digit assignment. - **N-queens** — column-and-diagonal constraints. ## Constraint Types - **Unary** — restrict a single variable (e.g., $x_1 \neq 5$). - **Binary** — restrict pairs (e.g., $x_1 \neq x_2$). - **Higher-arity** — AllDifferent over $n$ variables. - **Global constraints** — semantically rich constraints with specialised propagators (AllDifferent, Cumulative, GCC). ## Solving CSPs Three families of techniques, often combined: 1. **Search** — [[Backtracking Search]] with variable / value ordering heuristics. 2. **Propagation** — [[Arc Consistency AC-3]] and [[Constraint Propagation]] reduce domains by ruling out unsupported values. 3. **Local search** — Min-conflicts hill climbing; works well on certain CSPs (especially flat ones like N-queens at scale). ## Variable and Value Ordering Heuristics - **MRV (Minimum Remaining Values):** pick the variable with the smallest domain. Fails fast. - **Degree heuristic:** tiebreaker — pick the variable with most constraints on remaining variables. - **LCV (Least Constraining Value):** when choosing a value, pick the one that rules out the fewest options for other variables. ## Complexity - General CSP is **NP-complete** (SAT is a CSP). - Tractable subclasses exist — e.g., when the constraint graph is tree-structured, CSPs are solvable in $O(nd^2)$. ## Modern Solvers - **OR-Tools** (Google), **MiniZinc** (modelling language + solvers), **Choco**, **JaCoP**, **Gecode**. - Modern hybrid solvers (CP-SAT in OR-Tools) combine constraint propagation with conflict-driven clause learning from SAT — and dominate many industrial benchmarks. ## Related - [[Backtracking Search]] - [[Arc Consistency AC-3]] - [[Constraint Propagation]] - [[Combinatorial Optimization]]