Constraint Satisfaction Problems — Section 4: Constraint Satisfaction

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

$X = \{X_1, \dots, X_n\}$ : variables.
$D = \{D_1, \dots, D_n\}$ : domains. $X_i$ takes a value from $D_i$ .
$C$ : constraints, each over some subset of variables, specifying which combinations are allowed.

A solution is an assignment of values to variables that satisfies every constraint. Sometimes you want any solution; sometimes you want a solution that minimizes a cost (constrained optimization).

Examples

Map coloring: variables = countries, domain = colors, constraints = adjacent countries differ.
Sudoku: variables = 81 cells, domain = $\{1, ..., 9\}$ , constraints = each row, column, and 3×3 block contains every digit.
N-queens: variables = columns, domain = rows, constraints = no two queens on the same row, column, or diagonal.
Scheduling: variables = jobs, domain = (machine, start_time) pairs, constraints = precedence, no-overlap, resource limits.

Why CSP is a useful framing

Many practical problems map naturally to CSP.
General-purpose CSP solvers (Choco, MiniZinc, OR-Tools CP-SAT) handle huge instances by exploiting problem structure.
Constraints can be added incrementally — what's hard in custom code is easy declaratively.

Constraint types

Unary (over 1 variable): essentially a domain restriction.
Binary (over 2 variables): map coloring's "adjacent ≠".
Global (over many variables): "all-different on these 9 variables." Specialized propagation algorithms handle these much more efficiently than decomposing into pairwise constraints.

Why CSPs are NP-hard

Generic CSP is NP-complete. The "easy" instances are easy because of structure — small treewidth, few interacting constraints, good propagation chains. The hard ones (random 3-SAT at the phase transition) can stump even the best solvers.

Modern CSP / SAT solvers

CP-SAT (Google OR-Tools), Z3, Gurobi: solve real instances with tens of thousands of variables. They combine constraint propagation, learned clauses (from conflict-driven clause learning), and restart strategies. Worth knowing they exist even if you don't write the algorithms yourself.

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

$X = \{X_1, \dots, X_n\}$ : variables.
$D = \{D_1, \dots, D_n\}$ : domains. $X_i$ takes a value from $D_i$ .
$C$ : constraints, each over some subset of variables, specifying which combinations are allowed.

Examples

Map coloring: variables = countries, domain = colors, constraints = adjacent countries differ.
Sudoku: variables = 81 cells, domain = $\{1, ..., 9\}$ , constraints = each row, column, and 3×3 block contains every digit.
N-queens: variables = columns, domain = rows, constraints = no two queens on the same row, column, or diagonal.
Scheduling: variables = jobs, domain = (machine, start_time) pairs, constraints = precedence, no-overlap, resource limits.

Why CSP is a useful framing

Many practical problems map naturally to CSP.
General-purpose CSP solvers (Choco, MiniZinc, OR-Tools CP-SAT) handle huge instances by exploiting problem structure.
Constraints can be added incrementally — what's hard in custom code is easy declaratively.

Constraint types

Unary (over 1 variable): essentially a domain restriction.
Binary (over 2 variables): map coloring's "adjacent ≠".
Global (over many variables): "all-different on these 9 variables." Specialized propagation algorithms handle these much more efficiently than decomposing into pairwise constraints.