A constraint satisfaction problem (CSP) in artificial intelligence is a problem stated as a set of variables, a set of allowed values for each variable (its domain), and constraints that restrict which combinations of values may occur together. The task is to find an assignment of a value to every variable that breaks no constraint. CSPs are NP-hard in general, so practical solvers combine backtracking search with filtering rules that remove impossible values early.
Key takeaways
- A CSP has three parts: variables, domains, and constraints, and the goal is any assignment that satisfies all constraints.
- With N variables and domains of size d, there are d to the power N possible complete assignments, which is why blind enumeration fails.
- Backtracking assigns one variable at a time and retreats as soon as a constraint is violated.
- Forward checking and arc consistency delete values that cannot be part of any solution, and the minimum remaining values rule picks the most restricted variable first.
- Scheduling is a common real use, and solver libraries document employee scheduling and job shop problems as constraint programming tasks.
The three parts of a CSP
The UC Berkeley CS 188 course notes describe a CSP as an identification problem: the question is whether a state satisfies the goal, not how to reach it. Variables each take one value from their domain. Constraints may involve one variable (a unary constraint that simply prunes its domain), two variables (a binary constraint, drawn as an edge in a constraint graph), or three or more (higher-order). The standard textbook example is map coloring, where regions are variables, colors are the domain, and neighboring regions must differ. Another is the N-queens puzzle, where placing queens on a board so none attack each other can be expressed with row, column, and diagonal constraints.
A worked example: exam timetabling
This is an illustrative example, not real university data. Five exams, A to E, must be given in one of three slots: Monday, Tuesday, or Wednesday. Pairs that share students cannot sit in the same slot: A with B, A with C, B with C, C with D, and D with E. There are 3 to the power 5, or 243, complete assignments to consider if every combination were tried.
The search below uses backtracking with forward checking and the minimum remaining values rule, which picks the variable with the fewest valid options left.
- Assign A = Monday. Forward checking removes Monday from B and C, leaving each with Tuesday and Wednesday.
- B and C each have two options, fewer than D and E with three, so B is chosen next. Assign B = Tuesday. C loses Tuesday and is left with Wednesday only.
- Assign C = Wednesday. D loses Wednesday and keeps Monday and Tuesday.
- Assign D = Monday. E loses Monday and keeps Tuesday and Wednesday. Assign E = Tuesday.
The result is A on Monday, B on Tuesday, C on Wednesday, D on Monday, and E on Tuesday, and no step needed to undo an earlier choice. If the slots were reduced to two, the triangle A, B, C could not be colored, and the search would exhaust its options and report that no solution exists.
How solvers cut the search
| Technique | What it does | Effect in the example |
|---|---|---|
| Backtracking | Assigns variables in order and undoes the last choice on a conflict | Avoids trying assignments that already break a constraint |
| Forward checking | After each assignment, removes conflicting values from unassigned neighbors | Left C with one option after B was set |
| Arc consistency (AC-3) | Removes any value of one variable that has no compatible partner value in a neighbor | Catches dead ends before they are reached |
| Minimum remaining values | Chooses the variable with the fewest valid options next | Picked B before D and E |
| Least constraining value | Chooses the value that removes the fewest options from neighbors | Breaks ties among values |
The CS 188 notes define arc consistency this way: for an arc from X to Y, every remaining value of X must have at least one remaining value of Y that does not violate the constraint, and values without such a partner are deleted. AC-3 enforces this by keeping a queue of arcs and re-queuing neighbors whenever a domain shrinks. It stops when the queue is empty or when some domain becomes empty, which forces a backtrack.
Where CSPs are used
Constraint programming appears wherever many choices must satisfy fixed rules. Google's OR-Tools documentation describes constraint programming as finding feasible solutions among a very large set of candidates, and lists employee scheduling, the job shop problem, N-queens, and cryptarithmetic puzzles as example problems. Timetabling, rostering, and configuration tasks share the same structure. A CSP differs from the optimization problems covered elsewhere on the site because it asks first whether any feasible answer exists, with no score to maximize.
Limits and common misconceptions
- A CSP is not automatically fast to solve. Because the general problem is NP-hard, a badly structured instance can take exponential time even with good heuristics.
- Modeling choices matter. The same real task can be written with different variables, and a poor formulation makes the search much harder.
- Constraint solving is not machine learning. A solver needs the constraints to be written down, and it does not learn them from data.
- Soft preferences, such as a wish for no early exams, are not constraints. They require an objective or a weighted extension.
FAQ
What are the components of a constraint satisfaction problem?
Variables, a domain of possible values for each variable, and constraints that limit combinations of values. A solution assigns every variable a value without violating any constraint.
Is a constraint satisfaction problem the same as an optimization problem?
No. A CSP asks for any assignment that satisfies the constraints. An optimization problem adds a measure of quality and looks for the best assignment under it, though many solvers handle both.
Why does backtracking beat plain depth-first search on a CSP?
Plain search may assign values freely and notice a conflict only at the end. Backtracking rejects a value as soon as it clashes with earlier ones, so it retreats much sooner.
Can a CSP have no solution?
Yes. If constraints cannot all hold at once, as with three mutually conflicting exams and only two slots, the solver reports failure after exhausting its options.
Related reading
- Examples of how AI problems are formulated
- The traveling salesman problem and what AI solves today
- Robot navigation as a search problem
- AI applied to complex problems
More in AI Basics.
Last verified: October 2026
Sources
- CSPs, Introduction to Artificial Intelligence (CS 188) course notes, University of California, Berkeley, 2026
- Constraint Optimization, Google OR-Tools documentation, Google Developers, 2026