Constraint satisfaction problem

A constraint satisfaction problem (CSP) is the generalization of the satisfiability problem to arbitrary variable domains and constraint relations. Where Boolean satisfiability restricts variables to {true, false} and constraints to logical clauses, CSP permits variables ranging over discrete or continuous domains and constraints expressed as arbitrary relations among subsets of variables. The question remains the same: does there exist an assignment of values to variables such that all constraints are simultaneously satisfied?

CSPs are solved through a combination of backtracking search and constraint propagation, where local consistency conditions are enforced to prune the search space before committing to assignments. The AC-3 algorithm enforces arc consistency; stronger forms include path consistency and generalized arc consistency. The interplay between search and inference is the central algorithmic question in CSPs: more propagation reduces search but costs more per node.

CSP is the right level of abstraction for understanding real-world constraint problems, not SAT. The Boolean restriction of SAT is elegant for theory but wasteful for practice. Most scheduling, routing, and configuration problems have natural non-Boolean structure that SAT encodings destroy. The field's obsession with SAT solvers has slowed progress on generalized constraint satisfaction by a decade.