Arc Consistency (AC-3)

Arc consistency: for every directed pair of variables $(X_i, X_j)$ connected by a constraint, every value in $D_i$ has at least one supporting value in $D_j$. Iteratively prune until the property holds — that's AC-3.

Algorithm

``` function AC_3(csp): queue = all arcs (Xi, Xj) in csp while queue not empty: (Xi, Xj) = queue.pop() if revise(csp, Xi, Xj): if Di is empty: return failure for Xk in neighbors(Xi) except Xj: queue.add((Xk, Xi)) return success

function revise(csp, Xi, Xj): revised = False for x in Di: if no value y in Dj makes constraint(Xi, Xj, x, y) true: remove x from Di revised = True return revised ```

Properties

• Time: $O(c d^3)$ where $c$ is the number of constraints and $d$ is the max domain size.
• Sound but incomplete: AC-3 doesn't always find solutions; some CSPs are arc-consistent but unsolvable (e.g., a triangle graph with three variables, three colors, all "different from neighbor" — arc-consistent but unsatisfiable). It prunes but doesn't decide.

Why AC-3 still matters

Run AC-3 once as preprocessing. Then run backtracking with forward checking. Most of the inconsistent assignments AC-3 would have prevented are now pruned upfront, and the remaining search is dramatically smaller.

In practice, every serious CSP solver uses AC-3 as a baseline propagation routine, plus more sophisticated propagators (path consistency, learned clauses) layered on top.

Generalized arc consistency (GAC)

Extend to constraints over more than two variables. "All-different on $X_1, X_2, \dots, X_n$" has a specialized GAC algorithm (Régin's algorithm using bipartite matching) that's far more powerful than decomposing into pairwise "different" constraints.

When AC-3 isn't enough

For hard combinatorial problems (3-SAT at the phase transition, hard graph coloring), arc consistency alone barely makes a dent. Modern CDCL SAT solvers learn entirely new constraints from conflicts during search — a much more powerful (and complicated) approach.

The big picture: AC-3 is the bottom of a tower of constraint propagation techniques. Knowing it well is enough for most applied work; knowing what comes above is useful for problems where AC-3 doesn't scale.