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

and a constraint storeXYXZYZ

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

3and a constraint store^{ . }X+ 3^{ . }Y= 5^{ . }ZX-Y=ZX+Y=Z+ 2

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

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

Andreas Rossberg 2006-08-28