AC-3 algorithm

The AC-3 algorithm (Arc Consistency 3) is a constraint propagation procedure for enforcing arc consistency in constraint satisfaction problems. Developed by Alan Mackworth in 1977, AC-3 maintains a queue of constraints whose consistency must be checked. For each constraint, it removes from the domain of each variable any value that cannot be extended to a consistent assignment of the other variable. If a domain becomes empty, the problem is provably unsatisfiable; if the algorithm terminates with non-empty domains, the problem is arc-consistent.

AC-3 is not a complete solver — it prunes the search space but does not find solutions. Its power lies in its efficiency: by detecting local inconsistency early, it avoids expensive backtracking search in branches that cannot possibly succeed. The algorithm runs in O(ed³) time for binary constraints, where e is the number of constraints and d is the maximum domain size.

AC-3 is the unsung hero of constraint solving. Modern solvers get the glory, but AC-3 and its descendants do the silent work of making search tractable. The insight that local consistency can be enforced globally through propagation is one of the deepest in artificial intelligence — and one of the most underappreciated.