Does arc consistency guarantee a solution?

Not in general. The two-color triangle is arc-consistent but has no complete solution.

Why repeat checks after pruning a domain?

Removing a value can eliminate the last support for a value in another variable's domain.

What does an empty domain indicate?

Under sound propagation, no solution remains for the current problem or search branch, because that variable has no permissible value.

AI Glossary / Graphs and symbolic AI / Intermediate

Local consistency

Definition

Local consistency is a family of conditions used in constraint satisfaction to check whether assignments to small groups of variables can be extended without violating relevant constraints. Enforcing such conditions can remove unsupported values and expose contradictions before full search. Passing a local check does not generally prove that the entire problem has a solution.

What it means

A constraint satisfaction problem specifies variables, their possible values, and restrictions on combinations of values. Local consistency examines limited portions of that problem rather than immediately testing every complete assignment.
The word local refers to the scope of the consistency requirement, not necessarily geographic proximity or a single computer. Different strengths examine different amounts of interaction. Node consistency handles individual-variable restrictions; arc consistency checks support across binary constraints. Stronger notions inspect larger groups, usually requiring more computational work. The appropriate strength depends on both the problem structure and the cost of remaining search.

How it works

For a binary constraint between X and Y, arc consistency from X to Y requires every retained value of X to have at least one compatible value in Y's current domain. If a value has no support, it can be removed. Domain reductions can remove support elsewhere, so propagation repeats relevant checks.
Higher-order consistency asks whether consistent partial assignments can extend to another variable. For example, k-consistency concerns extending assignments on k - 1 distinct variables to a kth variable. These conditions support systematic pruning, but limited-scope support can be mutually incompatible when considered across the whole problem.

Three practical examples

A scheduling model can remove a time option that has no compatible option for a linked task.
A configuration model can propagate restrictions when selecting one component eliminates alternatives for another.
A map-coloring exercise can show that every neighboring pair has compatible colors even though the entire map cannot use the available number of colors.

Think of it this way

Think of checking that each pair of meeting arrangements has some compatible choice. Those pairwise possibilities may use different choices, so they need not combine into one workable calendar. The analogy is limited because formal consistency specifies exactly which assignments and constraints must be checked, rather than relying on an informal sense that arrangements seem compatible.

Worked example

Consider an invented binary constraint problem with variables X and Y. Initially X has domain {1, 2, 3}, Y has domain {1, 2}, and the constraint is X < Y.
Value X = 1 has support Y = 2. Value X = 2 has no support because neither 1 nor 2 is greater than 2. Value X = 3 also has no support. Enforcing consistency from X to Y therefore reduces X to {1}.
Now check the reverse direction. With X restricted to {1}, value Y = 1 has no compatible X because 1 < 1 is false. Value Y = 2 remains supported by X = 1. The final domains are X = {1} and Y = {2}, which identify the solution in this small problem.
For a contrasting example, let A, B, and C each have domain {red, blue}, with all three pairwise constraints A != B, B != C, and A != C. Every value has support across every individual edge: red is supported by blue and blue by red. The network is arc-consistent.
Yet no complete solution exists. If A is red, both B and C must be blue, violating B != C. If A is blue, both must be red, producing the same conflict. A locally supported value is therefore not necessarily part of any global solution.
The second example requires consideration of the three-way interaction, stronger reasoning, or search to expose the contradiction. It also shows why the supports used for separate constraints cannot automatically be combined into one shared assignment.

Illustrative case study

In a fictional staffing project, Cedar Schedule reports that every remaining shift option has support in each neighboring requirement. A manager interprets that message as confirmation that a complete roster exists.
The team changes the report to say that propagation has not yet found a contradiction and continues the solver's search. It separately reports a validated complete assignment when one is found. This invented case illustrates careful interpretation of intermediate solver results, not a defect in the local consistency procedure.

Common misconceptions and mistakes

Arc-consistent does not mean solved, and nonempty domains do not generally prove satisfiability. Support for a value is evaluated against particular constraints and current domains; support in different places may rely on incompatible choices.
Also, pruning should preserve the solutions of the encoded problem. Removing a value merely because it looks inconvenient is not a sound consistency operation. Stronger consistency is not automatically the best practical choice because additional propagation has a cost. Finally, this entry concerns constraint satisfaction, not similarly named consistency properties in distributed storage or probabilistic graphical models.

Business use

Local consistency is useful when a business problem has discrete choices and explicit compatibility rules. It can reveal impossible options early and reduce the amount of search needed for a complete answer. The model still needs correct variables, domains, and constraints.
Distinguish three outcomes in reporting: a contradiction detected, a complete solution verified, and an unresolved problem whose domains have been reduced. For debugging, retain explanations of why values were removed. When performance matters, compare the time spent propagating with the search it avoids, using representative instances rather than assuming maximum consistency strength is always preferable.

Check your understanding

Why does the two-color triangle pass each pairwise support check but fail globally?

Answer: Each color has an opposite color available at each neighbor, but the choices cannot be coordinated across all three variables. Assigning one node forces the other two to share a color even though they must differ.

Related terms

Constraint satisfaction problem
Domain
Constraint propagation
Satisfiability
node consistency
arc consistency
path consistency
k-consistency
backtracking
support

Learn next

Add a third color to the triangle and construct a complete solution. Then return to two colors, assign one variable, and propagate its consequences. Compare what was visible before the assignment with what becomes detectable after the domains of its neighbors shrink.

Sources

University of California, Berkeley, original CS188 textbook, filtering, arc consistency and k-consistency: https://inst.eecs.berkeley.edu/~cs188/textbook/csp/filtering.html

Previous: Local Community Detection Next: Local costmap