Consider the constraint set C, consisting of
x1 + x2 + x4 >= 1
x1 + (1-x2) + x3 >= 1
x1+(1-x4)>=1
with domains xj ∈ {0, 1} for j = 1, 2, 3, 4.
Draw the dependency graph and note that it has width 2 with respect to the ordering 1,2,3,4.
Show that the constraint set is not 3-consistent, and show that a branching algorithm that follows the ordering 1,2,3,4 may be required to backtrack.
Recall that a constraint is not violated until all of its variables are fixed.
Add the constraints x1 + x2 ≥ 1 and x1 + x3 ≥ 1 to C and verify that C is now strongly 3-consistent. Check that the sequence of branches that led to the back track is no longer possible.