CSP Search and Structure

The companion lesson, Constraint Satisfaction Problems, defined the CSP as a triple $(X,D,C)$ of variables, domains, and constraints, and developed constraint propagation — node and arc consistency, and the AC-3 algorithm that shrinks domains before search. Propagation alone rarely solves the problem, though: it left Australia's $V$ and $T$ with choices still to make. This lesson supplies the search that finishes the job, the general-purpose heuristics that make it fast, and the structural facts that make whole classes of CSP easy.

Backtracking search

Inference alone rarely finishes the job, so we search. The naive move is standard depth-first search over partial assignments, adding one $var=value$ at a time — but that ignores a property every CSP has: commutativity. The order in which we assign variables never changes the resulting set of assignments, so at each node we need consider only a single variable rather than branching over which variable to assign next. That collapses the tree from $n!\cdot d^n$ leaves to the $d^n$ we actually need.¹

Backtracking search is depth-first search with this restriction: pick one unassigned variable, try its values in turn, recurse, and back up when a variable has no consistent value left. Because CSPs use a standardized representation, the algorithm needs no domain-specific initial state, action model, or goal test — the three plug-in functions $\text{Select-Unassigned-Variable}$, $\text{Order-Domain-Values}$, and $\text{Inference}$ carry all the cleverness.² This is the same structure as generic backtracking over a constraint search tree, specialized to the variable-domain-constraint frame.

The tree it explores, on the Australia map with the fixed order $WA,NT,Q,\dots$, begins by branching on $WA$'s three colors, then on $NT$'s, and so on. Most of that tree is dead weight — the figure shows the top two levels, where two of the three $NT$ branches under $WA=red$ already clash and get cut. A solver with good heuristics and forward checking never generates most of these nodes at all.

Heuristics that make it fast

A CSP is solved efficiently without any domain-specific heuristic — the structure supplies general ones instead. They answer three questions: which variable next, which value next, and what to infer after each choice.

Minimum-remaining-values (MRV). Choose the variable with the fewest legal values left. Also called the most constrained variable or fail-first heuristic: a variable near the end of its options is the most likely to fail soon, and if one has no legal values, MRV picks it and detects the dead end immediately instead of wandering. MRV routinely beats static ordering by a factor of a thousand or more.³

Degree heuristic. MRV is useless at the very first move, when every variable has all its values. The degree heuristic breaks the tie by choosing the variable involved in the most constraints on other unassigned variables — it shrinks the branching factor of future choices. On Australia, $SA$ has degree $5$ against the others' $2$ or $3$; choosing $SA$ first lets any consistent color follow with no backtracking at all.³

Least-constraining-value (LCV). Having picked a variable, order its values by how few choices they rule out for neighbors — leave the maximum flexibility for the rest. With $WA=red$, $NT=green$ already set and $Q$ next, choosing $Q=blue$ would strip $SA$ of its last option, so LCV prefers $red$. Variable selection is fail-first, but value selection is fail-last: we need only one solution, so we try the value most likely to lead to one.³

Interleaving search and inference

Inference is even stronger inside the loop than before it: every assignment is a fresh chance to prune neighbors.

Forward checking. When $X$ is assigned, delete from each unassigned neighbor's domain any value inconsistent with $X$'s choice. It establishes arc consistency for the assigned variable only. Combined with MRV, it computes exactly the remaining-value counts MRV needs. But it looks only one step out: it can leave two unassigned neighbors mutually inconsistent and not notice.

Maintaining Arc Consistency (MAC). After assigning $X_i$, run AC-3 — but seed its queue only with the arcs $(X_j,X_i)$ from unassigned neighbors $X_j$, then let propagation recurse as usual. MAC catches exactly the inconsistency forward checking misses (two unassigned neighbors forced to clash), because forward checking does only the initial-arc pass while MAC recurses through the whole graph. MAC is strictly more powerful than forward checking.⁴

Looking backward: backjumping and no-goods

When a branch dies, plain chronological backtracking just undoes the most recent decision — even when that decision is irrelevant to the failure. Fix the variable order $Q,NSW,V,T,SA,WA,NT$ and suppose search has reached $\{Q=red,NSW=green,V=blue,T=red\}$. The next variable, $SA$, borders $Q$, $NSW$, and $V$, and every color it could take clashes with one of them: it has no legal value. Chronological backtracking now backs up to $T$ and recolors Tasmania — which is absurd, because $T$ constrains nothing that touches $SA$.

The repair is to record, for each variable, a conflict set: the earlier assignments that ruled out its values. Here $SA$'s conflict set is $\{Q=red,NSW=green,V=blue\}$. Backjumping retreats not to the previous variable but to the most recent assignment in that set — $V$ — skipping $T$ entirely. The conflict set falls out of forward checking for free: whenever assigning $X=x$ deletes a value from $Y$, add $X=x$ to $Y$'s conflict set.⁵

Simple backjumping has a subtle limit — it fires only when a domain is emptied, and forward checking already prunes every such node before search reaches it, so on its own it is redundant. The idea becomes useful in the deeper form. Suppose $\{WA=red,NSW=red\}$ (already inconsistent for reasons downstream), then $T=red$, then $NT,Q,V,SA$ are tried and, after much thrashing, $NT$ runs out of values. $NT$'s direct conflicts do not include a complete set of culprits, so plain backjumping is stuck. Conflict-directed backjumping propagates conflict sets backward: when the current variable $X_j$ exhausts its domain, the variable $X_i$ it jumps to absorbs $X_j$'s conflicts,

so the reason for failure flows back through the chain $SA\to Q\to NT\to NSW$ until it reaches $NSW$, the true culprit, and Tasmania is skipped every time.⁵

Constraint learning goes one step further: extract a minimal subset of the conflict set that guarantees failure — a no-good — and record it as a new constraint (or in a side cache) so the same doomed combination is never tried again. Recording $\{WA=red,NT=green,Q=blue\}$ as a no-good is pointless if that branch is pruned once and never revisited, but if $V$ and $T$ are assigned above it in the tree, the same $\{WA,NT,Q\}$ clash recurs under every setting of $V$ and $T$, and the cached no-good kills each recurrence instantly. Constraint learning is one of the most important techniques in modern CSP and SAT solvers, and we return to its SAT incarnation below.

The structure of problems

The shape of the constraint graph controls how hard the CSP is: a problem that splits into loosely connected pieces, or has no cycles, gives search almost nothing to backtrack over. Two structural facts do most of the work.

Independent subproblems. If the constraint graph splits into connected components — Tasmania touches no mainland region — each component is solved separately and the solutions combined. Splitting $n$ variables into subproblems of $c$ variables each turns $O(d^n)$ into $O(d^c\cdot n/c)$, linear in $n$. Dividing a Boolean CSP of 80 variables into four independent pieces of 20 cuts the worst case from the age of the universe to under a second.⁶

Tree-structured CSPs. A constraint graph that is a tree — any two variables joined by exactly one path — is solvable in linear time. Pick any variable as the root and topologically sort so each variable follows its parent. Sweep from the leaves to the root making each parent-child arc consistent ($O(n{d}^2)$ over the $n-1$ arcs), then sweep root-to-leaf assigning values: because every arc is arc-consistent, each child always has a value compatible with its already-chosen parent, so no backtracking ever happens.

Cutset conditioning. Most graphs are not trees, but many are nearly trees. Choose a cycle cutset $S$ — a set of variables whose removal leaves a tree (deleting $SA$ turns Australia into a tree). For each assignment to $S$ that satisfies its own constraints, prune the neighbors' domains accordingly and solve the residual tree in linear time. With a cutset of size $c$ the total cost is $O(d^c\cdot (n-c)d^2)$: cheap when $c$ is small. Finding the smallest cutset is NP-hard, but good approximations exist, and the technique — cutset conditioning — recurs in probabilistic reasoning.⁷ A related approach, tree decomposition, collapses clusters of variables into mega-variables and solves the resulting tree of subproblems; a graph of bounded tree width is solvable in polynomial time.

Local search

Backtracking works over partial assignments. Local search takes the opposite tack: start from a complete assignment (every variable set, constraints violated) and repair it one variable at a time. The heuristic is min-conflicts — reassign a randomly chosen conflicted variable to the value that violates the fewest constraints.⁸ This connects the CSP frame to local search over complete states: no partial assignments, no backtracking, just hill-climbing on the count of violated constraints.

On $n$-queens, ignoring the initial placement, the run time of min-conflicts is roughly independent of problem size. It solves the million-queens problem in about 50 steps on average. The reason is that solutions are densely scattered through the state space, so from almost anywhere a short greedy descent finds one.⁸ The same method schedules the Hubble Space Telescope, cutting a week's scheduling from three weeks to around ten minutes, and — because it starts from a complete state — it repairs a broken schedule online with few changes, where backtracking would rebuild from scratch.

The min-conflicts landscape is dominated by plateaux: there can be millions of assignments one conflict short of a solution, all with the same score, and greedy descent stalls among them with no downhill move. Three techniques address this.⁸ Sideways moves (plateau search) allow steps to an equal-score neighbor, letting the search drift across a flat until a downhill exit appears. Tabu search keeps a short list of recently visited states and forbids returning to them, so the drift does not cycle. Constraint weighting attaches a weight $W_i$ to each constraint, all starting at $1$; each step minimizes the total weight of violated constraints, and after each step every currently violated constraint has its weight incremented. Over time the persistently hard constraints accumulate weight, which both tilts the plateau (creating a downhill direction where there was none) and steers effort toward the constraints that actually block a solution — the same idea, under the name clause weighting, drives several strong SAT solvers.

Min-conflicts also crosses the line into constraint optimization. When constraints are soft — violating one costs points rather than voiding the solution — the objective becomes the total penalty, and every technique from local search transfers directly: hill climbing on the penalty, simulated annealing to escape plateaux, genetic recombination of assignments. A constraint optimization problem (COP) is just a CSP whose goal is to minimize violation weight rather than reach zero, and it is how real schedulers encode preferences (professor R would rather not teach at 8 a.m.) alongside hard rules (no room hosts two classes at once).

SAT solvers and modern CSP systems

The CSP machinery in AIMA is the entry point to a research area that scaled to industrial size. The clearest success is Boolean satisfiability — the CSP whose variables are true/false and whose constraints are disjunctive clauses. SAT is NP-complete (Cook, 1971), yet solvers routinely dispatch instances with millions of variables, and the reason is the algorithm named in this lesson's backtracking section, industrialized.

Modern SAT solvers are built on CDCL — conflict-driven clause learning (Marques-Silva and Sakallah, 1999, in the GRASP solver; refined by Chaff, Moskewicz et al., 2001). CDCL combines backtracking search, conflict-directed backjumping, and no-good recording, specialized to clauses: when a partial assignment falsifies a clause, the solver analyzes the implication graph to derive a new learned clause (a no-good) that summarizes the conflict, adds it permanently, and backjumps to the assignment level that clause implicates.⁹ Two engineering ideas make it fast. Watched literals (Chaff) detect unit clauses in near-constant time by tracking only two literals per clause instead of scanning all of them, so unit propagation — the SAT analog of forward checking — costs almost nothing. VSIDS, the variable-state-independent-decaying-sum branching heuristic (also Chaff), scores variables by how often they appear in recent learned clauses and decays old scores, focusing the search on the currently contentious part of the formula — a dynamic cousin of MRV. The learned clauses are the no-goods of the backtracking section, kept across the whole search rather than one subtree.

Two solver families sit around CDCL. Local-search SAT solvers — WalkSAT (Selman, Kautz, Cohen, 1994) — apply the min-conflicts idea directly: from a random complete assignment, pick an unsatisfied clause and flip one of its variables, mixing a greedy min-conflict flip with random noise to escape plateaux.¹⁰ WalkSAT solves large random-3-SAT instances that stall CDCL, though it is incomplete (it never proves unsatisfiability). For hard structured problems, portfolio and parameter-tuned solvers dominate the annual SAT Competition: SATzilla (Xu, Hutter, Hoos, Leyton-Brown, 2008) picks a solver per instance from runtime predictors, and automated configuration tools tune a solver's dozens of heuristics to a problem class.

General CSP solving scaled the same way. Finite-domain constraint-programming systems — Gecode, Google OR-Tools CP-SAT, and Choco — implement specialized propagators for global constraints like Alldiff (Régin's 1994 matching-based filtering enforces Alldiff far more strongly than pairwise $\ne$) and combine backtracking, MAC-style propagation, and learned no-goods. The MiniZinc modeling language (Nethercote et al., 2007) lets a user state a CSP once and dispatch it to any of these back ends, and the MiniZinc Challenge benchmarks them yearly. CP-SAT in particular translates constraint models into a CDCL SAT core extended with integer reasoning (lazy clause generation, Ohrimenko, Stuckey, Codish, 2009), fusing the two lines above.¹¹ For practice, this means the map-coloring heuristics in this lesson are the conceptual seeds of solvers that plan factory schedules, route delivery fleets, and verify hardware — problems with variables in the millions, solved by machinery that is recognizably backtracking, inference, and no-good learning at scale.

What the structure bought

Exposing a state's internal structure pays off in three distinct ways. The factored form turns constraint violation into inference: node and arc consistency and AC-3 delete impossible values without any search. It turns variable order into heuristics: MRV, degree, and least-constraining-value are general rules a black-box searcher could never formulate, because it cannot see what most constrained means. And it turns the constraint graph into a complexity map: trees fall in linear time, cutset conditioning tames the rest, and min-conflicts exploits the density of solutions that structure creates. A generic search sees only states and a goal test; a CSP sees why a state fails, and prunes accordingly.