How is a constraint satisfaction problem different from a general search problem?

A general search problem treats states as black boxes, but a CSP exposes the internal structure of a state as an assignment to variables subject to constraints. This structure lets CSP solvers use constraint propagation and ordering heuristics that generic search cannot exploit.

What does arc consistency do?

Arc consistency removes values from a variable's domain that have no compatible value in a neighboring variable, given the constraint between them. Enforcing it before and during search prunes the search space and can sometimes solve a problem outright without backtracking.

Constraint Satisfaction Problems

A constraint satisfaction problem asks for an assignment of values to a set of variables that simultaneously satisfies all constraints among them, providing a uniform representation for many combinatorial problems.

Definition

A constraint satisfaction problem consists of a set of variables, a domain of possible values for each, and a set of constraints specifying allowable combinations of values; a solution is a complete assignment that violates no constraint.

Scope

This topic covers the constraint satisfaction problem (CSP) formalism (variables, domains, constraints) and the algorithms that solve it: backtracking search with variable- and value-ordering heuristics, constraint propagation and consistency techniques (node, arc, and path consistency, such as the AC-3 algorithm), and the exploitation of problem structure (tree-structured CSPs, cutset conditioning). It connects to local search for CSPs and to the broader practice of constraint programming. The continuous-optimization and learning-based formulations of similar problems are out of scope here.

Core questions

How are diverse problems (scheduling, map coloring, puzzles) cast uniformly as variables, domains, and constraints?
How does constraint propagation prune values before and during search to reduce backtracking?
Which variable- and value-ordering heuristics make backtracking search efficient?
How can the structure of the constraint graph (for example, being tree-shaped) be exploited for efficient solving?

Key concepts

variables, domains, constraints
constraint graph
backtracking search
forward checking
arc consistency and AC-3
minimum-remaining-values heuristic
constraint propagation
tree-structured CSPs and cutset conditioning

Key theories

Arc consistency and constraint propagation: A CSP is arc consistent when every value of every variable has a consistent partner in each neighboring variable; algorithms such as AC-3 enforce this by repeatedly removing unsupported values, often drastically shrinking domains before or during search.
Backtracking search with heuristics: CSPs are solved by depth-first assignment with backtracking, made practical by heuristics such as choosing the most-constrained variable (minimum remaining values), the least-constraining value, and by interleaving forward checking or propagation to detect dead ends early.
Structure exploitation: When the constraint graph is a tree, a CSP can be solved in time linear in the number of variables, and near-tree structures can be reduced to this case via cutset conditioning or tree decomposition.

Clinical relevance

CSP techniques are the engine behind scheduling and timetabling, resource allocation, configuration of products, hardware and software verification, and puzzle solvers such as Sudoku; constraint programming languages and solvers built on these ideas are widely used in industrial planning and operations research.

History

Constraint networks emerged in the 1970s from work on scene labeling and relational consistency, with Mackworth's 1977 paper formalizing node, arc, and path consistency. Through the 1980s-90s the field matured into constraint programming, consolidated in the 2006 Handbook of Constraint Programming, and remains a standard AI topic.

Key figures

Alan K. Mackworth
Rina Dechter
Eugene C. Freuder
Ugo Montanari

Seminal works

mackworth1977
dechter2003
rossi2006

Frequently asked questions

How is a constraint satisfaction problem different from a general search problem?: A general search problem treats states as black boxes, but a CSP exposes the internal structure of a state as an assignment to variables subject to constraints. This structure lets CSP solvers use constraint propagation and ordering heuristics that generic search cannot exploit.
What does arc consistency do?: Arc consistency removes values from a variable's domain that have no compatible value in a neighboring variable, given the constraint between them. Enforcing it before and during search prunes the search space and can sometimes solve a problem outright without backtracking.