A constraint satisfaction problem (CSP) is a problem defined by a set of variables, a domain of possible values for each variable and a set of constraints that restrict which combinations of values are allowed; a solution is a complete assignment that satisfies every constraint at once. In artificial intelligence, the CSP is one of the classic formalisms of AI fundamentals because it separates the description of a problem from the general algorithms that solve it.
Scheduling, timetabling, configuration, map coloring and puzzles such as Sudoku all fit the same template. Once a task is expressed as a CSP, a domain-independent solver can exploit the structure of the constraints, which is far more efficient than blind enumeration of every possible assignment.
The formal structure of a CSP
A CSP is written as a triple (X, D, C): X is the list of variables, D gives the domain of each variable and C lists the constraints. Each constraint names its scope, the variables it involves, and a relation that defines the permitted value combinations, either as an explicit list of tuples or as a test such as x1 != x2.
Constraints are classified by arity, the number of variables they touch. Any higher-order constraint can in principle be converted into binary ones through auxiliary variables, which is why much of the theory concentrates on binary constraint networks drawn as a constraint graph with variables as nodes and constraints as edges.
The following table lists the building blocks and gives a map coloring illustration for each.
| Component | Meaning | Map coloring illustration |
|---|---|---|
| Variables | Unknowns to be assigned | One variable per region |
| Domains | Allowed values per variable | Red, green, blue |
| Unary constraint | Restricts one variable | A coastal region may not be blue |
| Binary constraint | Relates two variables | Neighboring regions differ in color |
| Global constraint | Relates many variables at once | All regions in a group differ |
| Solution | Complete, consistent assignment | A valid coloring of the whole map |
Domains may be finite and discrete, such as colors or time slots, or continuous, such as start times in seconds. Finite-domain CSPs are the main subject of classic AI search, while continuous problems with linear constraints usually belong to linear programming.
How CSP solvers search for a solution
The standard complete method is backtracking search, a depth-first search that assigns one variable at a time and undoes the latest choice as soon as a constraint is violated. Plain backtracking is exponential in the worst case, so practical solvers add variable ordering, value ordering and constraint propagation.
Propagation removes values that cannot appear in any solution. Forward checking prunes the domains of unassigned neighbors after each assignment, and arc consistency, enforced by algorithms such as AC-3, ensures that every remaining value has a supporting value in each related variable. If a domain becomes empty, the solver backtracks immediately instead of discovering the dead end many levels deeper.
The table below summarizes the main techniques and the effect each one has on the search.
| Technique | What it does | Typical benefit |
|---|---|---|
| Minimum remaining values | Chooses the variable with the fewest legal values | Detects failure early |
| Degree heuristic | Prefers variables in the most constraints | Breaks ties and shrinks the tree |
| Least constraining value | Tries values that leave neighbors most options | Finds a solution sooner |
| Forward checking | Prunes neighbor domains after each step | Cheap early pruning |
| Arc consistency (AC-3) | Removes unsupported values across all arcs | Stronger pruning before search |
| Conflict-directed backjumping | Jumps back to the variable that caused failure | Avoids repeating the same conflict |
Incomplete methods also matter. Local search algorithms such as min-conflicts start from a full but inconsistent assignment and repeatedly change the variable involved in the most violations. Min-conflicts can solve the million-queens problem in a small number of steps, yet it cannot prove that no solution exists.
Complexity and problem structure
Deciding whether a general finite-domain CSP has a solution is NP-complete, because Boolean satisfiability (SAT) and graph coloring are special cases. Hardness is not uniform, however: random instances show a phase transition, where problems become hardest near the ratio of constraints to variables at which solutions stop existing.
Structure can make problems tractable. A CSP whose constraint graph is a tree can be solved in linear time in the number of variables by enforcing directional arc consistency and assigning values from the root. Graphs that are nearly trees can be handled through cutset conditioning or tree decomposition, with cost exponential only in the treewidth rather than in the total number of variables.
CSP compared with related formalisms
A CSP is one member of a family of declarative problem formulations, and the choice among them depends on whether the task needs optimization, logic or numerical reasoning.
| Formalism | Variables and constraints | Goal |
|---|---|---|
| Constraint satisfaction problem | Arbitrary finite domains and relations | Any consistent assignment |
| Constraint optimization problem | CSP plus an objective function | Best consistent assignment |
| Boolean satisfiability (SAT) | Boolean variables and clauses | Satisfying truth assignment |
| Integer linear programming | Integer variables and linear inequalities | Optimal objective value |
| Heuristic search in a state space | States and actions, no factored structure | Path to a goal state |
The key difference from ordinary heuristic search is the factored representation: because a CSP state is a set of variable values, the solver can reason about individual variables and constraints. In the history of symbolic AI, this made CSPs a bridge between knowledge representation and automated reasoning, and modern constraint programming languages and solvers grew directly from this line of work.
Modeling choices and common mistakes
Solver performance depends heavily on how the problem is modeled. The same timetable can be encoded with one variable per lesson and time slots as values, or with Boolean variables for every lesson and slot pair, and the two encodings can differ by orders of magnitude in solving time.
- Ignoring global constraints: writing many pairwise inequalities instead of an
alldifferentconstraint loses the stronger propagation that dedicated global algorithms provide. - Missing symmetry breaking: interchangeable values, such as identical rooms, multiply the search space; adding ordering constraints removes equivalent solutions.
- Overconstrained models: mixing soft preferences with hard rules often leaves no solution; preferences belong in an objective or in weighted soft constraints.
- Domains that are too large: fine-grained time units inflate domains; a coarser granularity that still meets requirements speeds up the search.
Understanding it simply
A constraint satisfaction problem is a puzzle with blanks to fill and rules to obey. Each blank has a list of allowed answers, and the rules say which answers can sit together. The task is to fill every blank so that no rule is broken.
Seating guests at a wedding is a good comparison. Every guest needs a table, some guests must sit together and others must be kept apart. A computer solves this by placing guests one at a time, crossing out seats that would cause trouble later and stepping back when it reaches a dead end. That careful crossing out is what makes solvers fast.
Applied in practice
A university registrar must schedule 420 exams into 30 time slots across 25 rooms. Each exam becomes a variable whose domain is the set of slot and room pairs. Hard constraints state that no student may have two exams in the same slot, that room capacity must cover enrollment and that some exams require laboratories.
The scheduling team models student overlaps as binary inequality constraints, adds capacity as unary constraints and uses minimum remaining values with arc consistency. The first model with every soft preference treated as a hard rule had no solution. After the team moved preferences, such as avoiding two exams on one day, into a weighted objective, the solver produced a conflict-free timetable within a few minutes and reduced same-day exam pairs compared with the previous manual schedule.