[gecode-users] Clockwise constraint

[Guido Tack]

Malcolm Ryan wrote:

> I want to make a constraint which represents the order of three values
> around a ring.
>
> Eg: if we have a,b,c \in {1,2,3,4} then I want to represent the
> constraint:
>
> clockwise(a,b,c) == (a < b < c) or (b < c < a) or (c < a < b)
>
> I can construct this directly using BExprs, but the use of 'or' means
> that it doesn't propagate very well. Eg:
> [...]
> Will give a = {1,4}, b = [2..3], c = [2..3] when it should be able to
> deduce that b = 2, c = 3. Is there any other way to represent this so
> that the propagation works better?

You can't get the full pruning directly (you'd need something like  
constructive disjunction for that).  Something you might want to add  
is a distinct constraint over all variables (although it wouldn't do  
the pruning in your example, it would add some pruning in other  
cases).  Or, if the domains are always dense (at most one value more  
than variables, that is), you could use a+1=b instead of a<b.  You  
could also encode the constraint into a TupleSet and use extensional,  
which would probably result in a really big table but give you domain  
consistency.

Cheers,
	Guido

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20080602/183d9bb3/attachment.htm>