A constraint satisfaction problem describes a solution by what it must satisfy rather than how to build it: a set of variables, a domain of allowed values for each, and constraints that restrict which combinations are legal. Scheduling, timetabling, map coloring, Sudoku, register allocation, product configuration and many layout problems fit this mold. Because the structure is explicit, generic solvers can prune enormous search spaces with inference that a blind search would never exploit.
This page is part of Search & Planning. Compare with Adversarial Search and the logical view in Logic & Inference.
A CSP is a triple (X, D, C): variables X = {X1..Xn}, domains Di, and constraints, each a relation over a subset of variables (its scope). A complete, consistent assignment is a solution. Binary constraints can be drawn as a constraint graph; its structure matters, because disconnected components can be solved independently and tree-structured graphs can be solved in time linear in the number of variables.
Constraints can be unary (SA ≠ green), binary (WA ≠ NT), or global (AllDifferent(row) in Sudoku). Global constraints have specialized propagators that are much stronger than the equivalent pile of pairwise constraints. A CSP that also has an objective to minimize becomes a constraint optimization problem (COP).
The baseline algorithm is depth-first backtracking: assign one variable at a time, check constraints against already-assigned variables, and undo the last choice when stuck. Three generic heuristics make it dramatically faster:
Forward checking removes inconsistent values from the domains of a variable's unassigned neighbors right after each assignment, so dead ends are detected one step earlier. Maintaining Arc Consistency (MAC) goes further and runs full AC-3 after each assignment. Smarter backtracking, such as conflict-directed backjumping and nogood learning, jumps back to the variable that actually caused the failure instead of the most recent one; this idea is central to modern SAT solvers.
An arc (X, Y) is arc-consistent if every value in DX has at least one supporting value in DY under their constraint. AC-3 keeps a queue of arcs, revises each one, and whenever DX shrinks it re-adds all arcs (Z, X) for neighbors Z. Its worst case is O(c·d3) for c binary constraints and domain size d.
Arc consistency alone rarely solves a problem, but it often shrinks domains enough that backtracking becomes trivial; easy Sudoku puzzles fall to propagation with almost no search. Stronger notions (path consistency, k-consistency) prune more at higher cost, which is usually not worth it outside special cases.
from collections import deque
def ac3(domains, neighbors, ok, queue=None):
queue = deque(queue or [(x, y) for x in domains for y in neighbors[x]])
while queue:
x, y = queue.popleft()
removed = {vx for vx in domains[x] if not any(ok(x, vx, y, vy) for vy in domains[y])}
if removed:
domains[x] -= removed
if not domains[x]:
return False
queue.extend((z, x) for z in neighbors[x] if z != y)
return True
def backtrack(assign, domains, neighbors, ok):
if len(assign) == len(domains):
return assign
# MRV with degree tie-break
var = min((v for v in domains if v not in assign),
key=lambda v: (len(domains[v]), -len(neighbors[v])))
# LCV: values that prune the fewest neighbor options first
def cost(val):
return sum(1 for n in neighbors[var] if n not in assign
for vn in domains[n] if not ok(var, val, n, vn))
for val in sorted(domains[var], key=cost):
trial = {v: set(d) for v, d in domains.items()}
trial[var] = {val}
if ac3(trial, neighbors, ok, [(n, var) for n in neighbors[var]]): # MAC
result = backtrack({**assign, var: val}, trial, neighbors, ok)
if result:
return result
return None
# Australia map coloring
edges = [("WA","NT"),("WA","SA"),("NT","SA"),("NT","Q"),("SA","Q"),
("SA","NSW"),("SA","V"),("Q","NSW"),("NSW","V")]
regions = ["WA","NT","SA","Q","NSW","V","T"]
neighbors = {r: set() for r in regions}
for a, b in edges:
neighbors[a].add(b); neighbors[b].add(a)
domains = {r: {"red", "green", "blue"} for r in regions}
different = lambda x, vx, y, vy: vx != vy
print(backtrack({}, domains, neighbors, different))
For production work use a real solver: Google OR-Tools CP-SAT (from ortools.sat.python import cp_model), MiniZinc, Choco, or a SAT/SMT solver such as Z3. They implement global constraints, clause learning, restarts and parallel portfolios that a hand-written solver will not match.
For very large problems where any good assignment will do, local search starts from a complete (possibly inconsistent) assignment and repairs it. The min-conflicts heuristic picks a conflicted variable and moves it to the value that violates the fewest constraints; it famously solves the n-queens problem for very large n in roughly constant iterations. Tabu search, simulated annealing and constraint weighting help it escape plateaus. Local search is incomplete: it cannot prove that no solution exists.
Modern practice blends these ideas. CP-SAT combines constraint propagation, SAT-style clause learning and LP relaxations; mixed-integer programming solvers dominate when constraints are mostly linear with a strong objective.
AllDifferent instead of O(n2) pairwise inequalities, and adding redundant implied constraints, can change runtime by orders of magnitude.The seven Australian regions must each get red, green or blue with neighbours differing. Tracing backtracking with the degree heuristic, MRV and forward checking shows why the heuristics matter:
Seven assignments, zero backtracks. Plain chronological backtracking with a fixed variable order can wander into dead ends — for instance colouring WA, NT and Q with three different colours early on leaves SA with no legal colour, a failure discovered only several levels later. On a seven-node graph that costs little; on a timetable with thousands of variables the difference is between seconds and never finishing.
Constraint-graph structure gives complexity guarantees that heuristics cannot. If the graph is a tree, a CSP with n variables and domain size d is solvable in O(n d2): order the variables from a root, make each parent arc-consistent with its children working from the leaves up, then assign values from the root down — arc consistency guarantees no backtracking.
General graphs can be pushed toward that case two ways. Cutset conditioning picks a set of c variables whose removal leaves a tree (in the map, removing SA does it), tries every assignment to them, and solves the remaining tree each time, for O(dc · (n − c) d2). Tree decomposition groups variables into overlapping clusters arranged as a tree; the cost is exponential only in the largest cluster size (the treewidth). These ideas also underpin exact inference in Bayesian networks, where the same graph structure determines tractability.
Most industrial uses are optimization problems with a few thousand to millions of variables: shift rostering, job-shop scheduling, vehicle routing, bin packing, sports schedules. A typical CP-SAT model for scheduling uses an interval variable per task (start, duration, end), a NoOverlap constraint per machine, precedence constraints between tasks of the same job, and an objective such as minimizing the makespan or total lateness. Practical guidance:
AllDifferent, Cumulative, Circuit and Table propagate far better than equivalent piles of small constraints.When the model is infeasible, ask the solver for an unsatisfiable core (or relax constraints one group at a time) to find the conflicting requirements rather than guessing.