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   X $\neq$ Z   Y $\neq$ Z

and a constraint store

$X \in \ensuremath{\{0,1\}} \hspace{4mm} Y \in \ensuremath{\{0,1\}} \hspace{4mm} Z \in \ensuremath{\{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 ^. X + 3 ^. Y = 5 ^. Z   X - Y = Z   X + Y = Z + 2

and a constraint store

$X \in \ensuremath{\{4,\dots,10\}} \hspace{4mm} Y \in \ensuremath{\{1,\dots,7\}} \hspace{4mm} Z \in \ensuremath{\{3,\dots,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 \ensuremath{\{5,\dots,10\}} \hspace{4mm} Y \in \ensuremath{\{1,\dots,6\}} \hspace{4mm} Z \in \ensuremath{\{4,\dots,9\}}$

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