Constraint-Satisfaction Problems

A constraint-satisfaction problem (CSP) is defined, following Russell and Norvig's standard formalization, as a triple of a finite set of variables X1, X2, ..., Xn, a domain Di of possible values for each variable, and a set of constraints C1, C2, ..., Cm that restrict which combinations of values are jointly allowed. This factored representation is the key departure from ordinary state-space search: instead of treating a state as an opaque, atomic object that a problem-specific heuristic must evaluate from the outside, a CSP exposes its internal structure — which variables exist, what values they may take, and how they constrain one another — so that a single general-purpose algorithm can reason about any CSP at all, from Sudoku to timetabling to circuit-layout problems. The classic illustrative example is map-coloring: assign a color to each of several regions so that no two adjacent regions share a color, a structure that scales directly to problems like register allocation in compilers, where the 'regions' are program variables and 'adjacency' means two variables are live at the same time.

Concretely, consider coloring the mainland regions of Australia with three colors {red, green, blue} so that neighboring territories differ. The variables are Western Australia (WA), Northern Territory (NT), South Australia (SA), Queensland (Q), New South Wales (NSW), and Victoria (V); every variable's domain is {red, green, blue}; and the constraints are binary — WA ≠ NT, WA ≠ SA, NT ≠ SA, NT ≠ Q, SA ≠ Q, SA ≠ NSW, SA ≠ V, Q ≠ NSW, NSW ≠ V — one inequality constraint for every pair of regions that share a border. Because SA borders five of the other regions, it is the most heavily constrained variable in the graph, a fact that later becomes the basis of a powerful search heuristic. Notice, too, that SA, NT, and Queensland are mutually adjacent to one another, forming a triangle in the constraint graph; since three mutually adjacent variables can never share fewer than three distinct values between them, this triangle alone proves that two colors would be insufficient to color the whole map, and any correct assignment must use all three available colors somewhere. Solving this six-variable instance by brute-force enumeration would mean checking as many as 3^6 = 729 possible color assignments, only a small fraction of which satisfy every constraint — precisely the kind of blind search that backtracking, introduced next, avoids by abandoning inconsistent partial assignments the moment they are detected.

This variable-domain-constraint structure is naturally visualized as a constraint graph: nodes represent variables and edges connect variables that participate together in a binary constraint. Constraints involving three or more variables (higher-order constraints, such as an Alldiff constraint requiring an entire set of variables to take pairwise-distinct values — the constraint governing every row, column, and 3-by-3 box in Sudoku, each Alldiff spanning nine variables at once) appear as hyperedges in the constraint graph rather than simple lines between pairs of nodes, though any higher-order constraint can in principle be converted into an equivalent set of binary constraints through what is sometimes called the constraint's dual representation, at the cost of a larger, less intuitive graph. Unary constraints, which restrict a single variable's domain outright without reference to any other variable (for instance, ruling out a particular color before search even begins because of some external requirement), are typically preprocessed away before search starts, since they can be resolved immediately by simply shrinking that one variable's domain rather than being carried forward as constraints to be rechecked repeatedly during search. This preprocessing step, small as it sounds, is often the first and cheapest form of constraint propagation applied to any CSP.

The default algorithm for solving a CSP is backtracking search: a depth-first search over partial assignments that, at each step, assigns a value to one unassigned variable, checks that the assignment is consistent with all constraints involving only assigned variables, and — if consistent — recurses to assign the next variable; if no value is consistent, the algorithm backtracks to the previous variable and tries a different value. Trace this on the WA–NT–SA fragment of the Australia map: assign WA = red (no constraints yet, so any value is consistent); assign NT next — the constraint NT ≠ WA forbids red, so NT = green is chosen; assign SA last — the constraints SA ≠ WA and SA ≠ NT together forbid both red and green, forcing SA = blue. This branch succeeds without ever needing to backtrack, but had NT instead been assigned red at the second step, SA would have had no legal value at all, and the search would backtrack to try NT = green or NT = blue instead.

Which variable to assign next, and in what order to try its values, dramatically affects how much backtracking occurs. The minimum-remaining-values (MRV) heuristic — sometimes called the 'fail-first' heuristic — selects whichever unassigned variable has the fewest legal values left in its domain, on the reasoning that a variable likely to fail should be tested as early as possible so failure is detected before wasted work accumulates. When several variables tie on MRV, the degree heuristic breaks the tie by choosing the variable that participates in the most constraints with other unassigned variables — in the Australia example, SA's five borders make it an excellent early choice by this measure. For assigning a chosen variable's value, the least-constraining-value heuristic prefers whichever value rules out the fewest options for the variable's neighbors, preserving flexibility for the rest of the search. Together, MRV and degree act like an efficient interviewer who asks the hardest questions first, while least-constraining-value leaves as many doors open as possible for whoever answers next; combined, these heuristics are what let backtracking search scale to CSPs with thousands of variables that plain, unordered backtracking could never finish in a reasonable time.

Beyond ordering, constraint propagation prunes the search space before failures are even reached, by inferring which values are still possible without having to try them inside a full recursive branch. Forward checking, whenever a variable is assigned, immediately removes now-inconsistent values from the domains of its unassigned neighbors, so an empty domain signals failure right away rather than several assignments later, saving the wasted work of assigning further variables down what is already a doomed branch. Arc consistency goes further still: an arc from variable X to variable Y is consistent if, for every remaining value of X, some value of Y satisfies the constraint between them; the AC-3 algorithm repeatedly removes values of X that violate this until every arc in the constraint graph is consistent, propagating the effect of each removal outward to every other arc touching the affected variable. Because enforcing full arc consistency does more inference than forward checking (which only checks arcs to a newly assigned variable's immediate neighbors), it typically prunes more of the search tree per unit of propagation effort, at the price of more computation performed at every single assignment — a trade-off real solvers must balance based on how expensive each individual constraint check happens to be.

The structure of a CSP's constraint graph directly determines how hard it is to solve. If the constraint graph is a tree — no cycles at all — the problem can be solved in time linear in the number of variables and only quadratic in domain size: order the variables so each one's parent appears before it (a topological sort rooted anywhere), make the graph directed arc-consistent from leaves toward the root, and then assign values top-down, since arc consistency along a tree guarantees each assignment can always be extended without ever needing to backtrack. This is a striking result — most general CSPs are NP-hard in the worst case, meaning no known algorithm solves every instance in time that scales gently with problem size, yet tree-structured instances are provably easy and solvable this efficiently every single time. This gap between the general and tree-structured cases is precisely what motivates trying to reduce arbitrary, cyclic CSPs toward tree-like form before falling back on full backtracking search.

Cutset conditioning is the general technique for doing so: pick a small cycle cutset — a set of variables whose removal turns the constraint graph into a tree — and enumerate every possible value assignment for just that cutset. For each cutset assignment, the remaining variables form a tree-structured CSP solvable in linear time as above, so the overall complexity is governed mainly by how small a cutset can be found, a trade-off between search over the cutset and the guaranteed efficiency of the tree-structured remainder. For example, if the Australia map-coloring graph had one extra region creating a single cycle, removing just that one region as the cutset would leave a genuine tree solvable in linear time, so the total cost becomes the number of colors tried for that single region multiplied by the cost of the linear-time tree solution — far cheaper than searching the full cyclic graph directly. Related tree-decomposition methods generalize this idea by grouping variables into overlapping clusters that themselves form a tree, letting a solver combine cluster-local solutions systematically.

A complementary strategy abandons systematic backtracking altogether in favor of local search: start with a complete assignment of every variable (chosen arbitrarily, or greedily, and typically inconsistent), then repeatedly select some variable involved in a violated constraint and reassign it to whichever value minimizes the number of constraints it now violates — the min-conflicts heuristic. Applied to the classic n-queens puzzle (place n queens on an n×n board so none attacks another), min-conflicts starting from a random placement of one queen per column, then repeatedly moving the most-conflicted queen to its least-conflicted row, is famously effective, letting local search reach a solution in roughly constant time even for boards with hundreds of thousands of queens, illustrating how local search can outperform systematic backtracking when a good complete-assignment starting point exists. Unlike backtracking search, however, min-conflicts and other local search methods are typically incomplete: they might wander for a long time on a hard instance without ever finding a satisfying assignment, and they offer no way to prove that no solution exists at all, a guarantee only systematic methods like backtracking combined with propagation can provide, which makes local search attractive for large, loosely constrained problems but less suitable when a definitive 'no solution' answer matters as much as finding one when it exists.