Assignments and restrictions
Scheduling, labeling, and map coloring can be described by variables with possible values and restrictions on which combinations are allowed. A constraint satisfaction problem (CSP) asks for a complete assignment satisfying all restrictions; it need not attach an objective function to assignments.
Definition 1.2.1
(Finite binary constraint network)
A network has finitely many variables, each with a finite domain, and binary constraints. A binary constraint specifies allowed pairs; the reverse orientation uses the transposed relation. A solution chooses one value from each original domain and satisfies every constraint. For simplicity, combine multiple constraints on the same pair by intersecting their relations before applying the procedure below.
Support and arc consistency
Definition 1.2.2
(Support, revision and arc consistency)
For a directed arc of a constraint, a value has support in if some satisfies . To revise is to remove from every value with no such support. The direction matters: revising the reverse arc removes values from instead. A network is arc-consistent when every remaining value has support across each directed constraint arc. An empty domain signals failure; a constraint-free variable needs no neighboring support.
Repeatedly revise arcs while any value can be removed. Whenever a domain shrinks, neighboring arcs may lose support and must be reconsidered. An implementation can maintain a queue of affected arcs, but the mathematical stopping condition is that all directed arcs have been checked after relevant changes.
Proposition 1.2.3
(Revision removes no solution)
Let be obtained from a network by revising one directed arc. Then and have the same solutions, where a solution chooses a value from each current domain and satisfies every constraint. Consequently, if repeated revisions empty a domain, the original network has no solution.
Proof
(A solution supplies its own support)
Shrinking domains cannot create solutions, so every solution of is a solution of . Conversely, suppose a solution of uses while revising . The same solution assigns some with and , so is support for and is not removed. Hence the solution survives in . Induction over a sequence of revisions preserves the original solution set among the remaining values; if a domain becomes empty, no solution exists. This statement assumes the constraints themselves were not altered during revision.
Proof X-ray
Why deleting an unsupported value is safe
The argument uses one fact about a solution: it assigns a value to that lies in the current domain, and that value is the support. Support is therefore tested against the current domain , which by induction still contains every solution value; this is why a chain of revisions stays sound even though each one relies on earlier removals. Revision tests only a necessary condition for a value to occur in a solution, namely pairwise support along one arc. The converse fails, and the triangle below shows it: every value is supported along every arc, but no solution exists. The argument also depends on the constraints being binary and unchanged; support along each pair of arcs does not combine into support for a constraint on three variables.
Theorem 1.2.4
(Propagation terminates at the largest arc-consistent network)
Revising directed arcs until no revision removes a value terminates after at most removals. The resulting domains are arc-consistent, and they do not depend on the order of revisions: they form the largest arc-consistent choice of subdomains of the original domains.
Proof
(Every removal shrinks a finite measure)
Every actual removal reduces the total domain size by at least one, so at most removals occur. When no arc can remove anything, every remaining value has support across every directed arc, which is arc consistency. For the order independence, call a choice of subdomains arc-consistent if each value of has support in for every arc . A union of two arc-consistent choices is arc-consistent, since a value supported in one of them is supported in the union, so a largest one exists. No revision removes a value of : while for the current domains, each has support in . The final result contains and is itself arc-consistent, so it equals whatever the order.
Worked examples
Worked example 1.2.5
(Three mutually unequal variables)
Let , and . Require , , and . Revising removes from because can only be . Then revising removes from , and revising removes because can only be . The domains become ; the unique remaining assignment satisfies all three inequalities.
Worked example 1.2.6
(Failure detected without branching)
Let , , with the constraints and . Revising removes , since the only value of is . Now , and revising removes , since the only value of is also . The domain is empty, so the network has no solution. Direct reasoning agrees: forces , and leaves no value for . The failure was found by propagation alone.
Worked example 1.2.7
(Propagation first, then branching)
Let and , with all three variables required to differ pairwise. Every value already has support on every arc: for instance is supported by and by , and is supported by and by . So propagation removes nothing, even though only can be part of a solution. Branch on . Revising removes , and revising removes . With , revising removes . All domains are now singletons: , and checking the original constraints , , confirms a solution.
Counterexample mode
Local support does not guarantee a solution
Take a triangle of variables , each with domain , and require different values on every edge. Each value on each arc has the other value as support, so the network is already arc-consistent. Nevertheless it has no solution: if then both neighbors must be , contradicting ; the case is symmetric. The supporting value on one arc need not be compatible with the support chosen on another.
Search after propagation
If nonempty domains remain, choose a variable with several values and branch on one remaining value at a time. In each branch restrict that variable to the chosen singleton and propagate again. If any domain empties, discard that branch. If all variables become singleton, check all original constraints before reporting a solution.
Theorem 1.2.8
(Propagation with branching is sound and complete)
For a finite network, the procedure that propagates, branches on a variable with several remaining values, and recurses terminates. It reports a solution exactly when one exists, and every reported assignment satisfies all original constraints.
Proof
(Each branch loses a value and keeps every solution)
Each branch replaces a domain of at least two values by a singleton, and propagation only removes values, so the total domain size falls strictly along every branch; the recursion terminates. A reported assignment is checked against all original constraints, so it is a solution. Conversely, suppose a solution exists. It survives sound propagation, and it assigns the branching variable one of its remaining values, so it survives in the branch for that value. By induction on the total domain size it is found in some branch. Exhausting every remaining branch without success therefore proves unsatisfiability.
This finite backtracking procedure can take exponential time in the number of variables. Arc consistency can reduce the search but does not remove that worst-case possibility. The proof does not claim that a particular variable-selection or queue order is always fastest.
Common mistakes
Common mistake
(Revising the wrong direction)
Revising removes values from , not from . With , and , revising removes nothing, because is supported by . Revising removes . Both arcs must be considered; one direction does not do the work of the other.
Common mistake
(One pass over the arcs is not enough)
Take , , with and . Revise the arcs once in the order , , , . Only removes anything: it deletes because the only value of is , leaving . The network is still not arc-consistent, since now has no support in . The earlier arc must be revised again, which removes . The final domains are arc-consistent and give the solution . A shrinking domain puts its neighboring arcs back on the queue.
Exercises
Quick check
(In the first worked example, why is unsupported on the arc ?)
Look at the domain of .
Solution · Answer
can only be , and violates .
Quick check
(In the two-color triangle, exhibit support for separately on arcs and . Why does this not produce a full solution?)
Check whether the two supporting values are compatible with each other.
Solution · Answer
The value supports on each arc, but taking both and violates .
Quick check
(What conclusion follows if sound revision empties a domain?)
A solution must choose a value from every domain.
Solution · Answer
No solution exists: a solution would need a value in every domain, and sound revisions removed no value used by a solution.
Quick check
(Give a solution when three mutually unequal variables each have domain .)
Assign the three values in order.
Solution · Answer
Assign . Each edge has unequal endpoints.