Every constraint satisfaction problem (a problem where you must assign values to variables without violating any rule) has the same two-phase structure: figure out what is possible, then search through what is possible to find something good. The second phase is expensive. The first phase is where arc consistency lives.
Before arc consistency, solvers relied on two strategies, both of which fail in characteristic ways when constraints are tight:
Try a complete assignment of all variables, then check whether it satisfies every constraint. Repeat until one works.
Assign variables one at a time and backtrack when a constraint is violated, without doing any look-ahead to detect future conflicts.
The hard problem both approaches share: a value in one variable’s domain (the set of allowed values) can be locally valid in isolation yet globally impossible because no compatible value exists in the domain of a variable it must co-exist with. Neither generate-and-test nor backtracking-only prune these values before branching.
The solver assigns X=3, builds a partial solution, then discovers later that Y has no compatible value. It backtracks, but the wasted work is already done.
✗The solver generates a complete solution, finds it violates a constraint between X and Y, and discards the solution. The constraint was visible from the start.
✗Arc consistency resolves this by examining every constraint between every pair of variables before and during search, permanently deleting values that can never participate in any feasible solution.
Arc consistency is a propagation algorithm (a method that spreads the consequences of each constraint through the variable network). It has three pieces: a constraint graph (a map of which variables are connected by which rules), a domain for each variable (the set of values it is still allowed to take), and a propagation queue (a worklist of constraints that may still be able to prune values). The algorithm repeatedly drains the queue until no more values can be removed.
- Initialise: place every constraint in the propagation queue.
- Take a constraint from the queue. For each value in the first variable’s domain, check whether there is at least one compatible value in the second variable’s domain. If not, remove the value from the first variable’s domain.
- If any value was removed, add to the queue every constraint involving the first variable (because its neighbours may now have values that lost their only compatible partner).
- Repeat until the queue is empty. The result is an arc-consistent network: every remaining value in every domain has at least one compatible partner in every directly constrained neighbour.
- If any domain becomes empty during this process, the problem has no feasible solution under the current partial assignment: backtrack immediately.
Why propagation cascades. Removing a value from X’s domain may leave a value in Y’s domain with no compatible partner in X. That triggers removal from Y’s domain, which may trigger removal from Z’s domain, and so on. One constraint can ripple pruning through the entire problem. This cascade is why arc consistency catches conflicts that are invisible when each constraint is checked in isolation.
A constraint network is arc consistent if and only if, for every constraint C(X, Y) (a rule involving two variables X and Y), and for every value x in X’s domain D(X):
there exists at least one value y in D(Y) such that the assignment X=x, Y=y satisfies C(X, Y).
In the notation above: D(X) is X’s domain (the values X is allowed to take); D(Y) is Y’s domain; C(X, Y) is the constraint (the rule that X and Y must together satisfy). A value x with no compatible partner y is not arc consistent and is permanently deleted from D(X).
In plain English: every value a variable can take must have at least one compatible value in every variable it shares a constraint with. If even one compatible partner is missing, the value is deleted. Not tentatively set aside; permanently deleted. No trial assignment, no backtracking: just removal.
The standard algorithm that enforces this property is AC-3 (Arc Consistency Algorithm 3, the third in a series of algorithms developed by Alan Mackworth in 1977, which became the practical standard because of its simplicity and efficiency). AC-3 runs in time proportional to the number of constraints multiplied by the square of the largest domain size, a cost that is negligible compared with the search savings it produces on typical industrial instances.
Binary vs. n-ary: where GAC enters. The definition above covers binary constraints (two variables). Real CP models use global constraints involving many variables at once: AllDifferent, NoOverlap, Cumulative. For these, solvers enforce Generalized Arc Consistency (GAC), also called Hyper-Arc Consistency: a value in variable Xi is GAC-supported if a complete tuple satisfying the full constraint exists with that value in the Xi slot. Each global constraint ships with its own dedicated GAC propagator. When a solver description says “arc consistency,” it almost always means GAC applied across all constraint arities.
A two-machine job shop schedules operations for three jobs. Machine A processes each job first; Machine B handles a follow-on operation. A constraint says Machine A must finish a job before Machine B can start it. Machine A’s start-time domain is {9am, 10am, 11am} and Machine B’s start-time domain (per job) is {10am, 11am, noon}. So far every value in A’s domain has a compatible partner in B’s domain, and every value in B’s domain has a compatible partner in A’s, so arc consistency finds nothing to prune.
Now a delivery deadline forces Machine B to finish all work by 11am. Each B operation takes one hour, so noon is eliminated from B’s domain, leaving {10am, 11am}. Arc consistency immediately re-checks: can A’s 11am start-time (finishing at noon) still find a compatible B start? No: B cannot start at noon any more. A’s 11am value is eliminated. The solver derived that A cannot start at 11am from a deadline placed on B, without branching at all.
This bidirectional propagation continues until no more values can be removed. In a real job shop with hundreds of operations and dozens of machines, each constraint eliminated via arc consistency spares the solver from generating and evaluating thousands of partial assignments.
The symbols, for the record. Let X be A’s start-time variable with domain D(X)={9,10,11} (hours) and Y be B’s start-time variable with domain D(Y)={10,11,12}. The constraint C(X,Y) requires X+1 ≤ Y (A finishes in one hour before B starts). The deadline sets Y≤11. After the deadline, D(Y)={10,11}. Arc consistency checks: does X=11 have any Y in {10,11} satisfying 11+1≤Y? No. So 11 is removed from D(X), leaving D(X)={9,10}.
Misread 1 — “Arc consistency runs once, before search”
Most practitioners assume arc consistency runs once as a pre-processing step, before the solver starts branching. In reality, modern constraint programming (CP) solvers run arc consistency continuously: every time the solver branches and fixes a variable to a value, arc consistency immediately propagates that assignment to all connected variables, removing any value in their domains that has now lost its compatible partner. It is not front-loaded pre-processing; it is a live, recursive pruning mechanism woven into every node of the search tree. (In the CP literature this continuous enforcement is called “maintaining arc consistency” or MAC, to distinguish it from a single-pass application.)
Misread 2 — “Arc consistency covers all constraints, and a consistent network has a solution”
On scope: Classical arc consistency operates on binary constraints (rules between exactly two variables). For constraints involving more than two variables at once, such as AllDifferent (no two variables in a set share a value) or NoOverlap (no two operations share a machine time-slot), modern CP solvers enforce the stronger Generalized Arc Consistency (GAC, also called Hyper-Arc Consistency): a value in variable Xi is GAC-supported only if a complete tuple satisfying the full multi-variable constraint exists with that value in the Xi slot. The AC-3 algorithm handles the binary case; dedicated GAC propagators (one per global constraint type) handle the n-ary case. In practice, when a CP solver description says “arc consistency,” it usually means GAC applied to all constraint arities.
On completeness: Whether the constraint is binary or n-ary, the same ceiling applies. A network that is fully arc consistent (or GAC-consistent) can still have no feasible solution; the infeasibility only surfaces when three or more variables must be assigned simultaneously. What propagation delivers is aggressive elimination of locally impossible values, not a proof that a solution exists. (The property that does guarantee extensibility is called strong k-consistency, which requires checking all subsets of k variables.)
Misread 3 — “Arc consistency is slow to apply”
Because arc consistency sounds like a whole-network scan, practitioners sometimes worry it adds prohibitive overhead to every branching decision. In practice, modern implementations maintain the propagation queue incrementally: when a value is deleted, only the constraints directly involving the affected variable are re-checked, not the entire network. The AC-3 algorithm runs in time O(ed2), where e is the number of constraints and d is the largest domain size, a cost that is almost always dominated by the savings from fewer branches. Solvers like Google CP-SAT and IBM ILOG CP Optimizer enforce arc consistency at every node without meaningful runtime penalty on industrial instances.
The diagnostic question when evaluating any published constraint programming model: are all binding operational constraints expressed explicitly as constraints between pairs of variables? If a constraint is left implicit (embedded in the objective or in ad-hoc heuristics), arc consistency cannot prune it, and the solver pays full search cost for a conflict it could have detected before the first branch.
“Make every constraint visible to the network, and the network will do the pruning for you.”
Alan Mackworth’s 1977 paper formalised arc consistency and showed that local pair-wise enforcement could substitute for the combinatorial cost of global enumeration on constraint networks. The principle names the key distinction this page has established: the work of eliminating impossibilities belongs to propagation, not to search. Search handles only what propagation cannot reach.