2.5 Incompleteness of Propagation

Constraint propagation is not a complete solution method. It may happen that a space has a unique solution and that constraint propagation does not find it. It may also happen that a space has no solution and that constraint propagation does not lead to a failed propagator.

A straightforward example for the second case consists of three propagators for

$X\neq Y \qquad X\neq Z \qquad Y\neq Z$

and a constraint store

$X\in 0\#1 \qquad Y\in 0\#1 \qquad Z\in 0\#1.$

This space has no solution. Nevertheless, none of the propagators is inconsistent or can tell something to the constraint store.

To see an example for the case where a unique solution is not found by constraint propagation, suppose we have interval propagators for the constraints

${3\cdot X}+{3\cdot Y}=5\cdot Z \qquad X-Y=Z \qquad X+Y=Z+2$

and a constraint store

$X\in 4\#10 \qquad Y\in 1\#7 \qquad Z\in 3\#9$

This space has the unique solution X=4 , Y=1 , Z=3 . Nevertheless, none of the propagators can narrow a variable domain.

If we narrow the domains to

$X\in 5\#10 \qquad Y\in 1\#6 \qquad Z\in 4\#9$

the space becomes unsatisfiable. Still, none of the above propagators is inconsistent or can narrow a variable domain.