CLP: Constraints on structured variables?

Question

Lets have the following hypothetical scenario ... a grid with 5x5 and let say 3 figures. We want to define constraint on the positions. In CLP we normally define the constraints with integers, so this is one way of doing it :

  ... Fig1X #\= 2, Fig1Y #\= 3, ....

i.e. we have separate variable for every X and Y position. Is there a way to define constraint on structured-variable which is built on top of integers. For the sake of example :

 .... Fig1 #\= (2,4) ...

The scenario is just for illustration.

I'm interested mainly in how do you handle structured-variables, is there standard practices.

Answer 1

Especially in connection with geometric tasks as in your example, there are at least the following quite different conceptual approaches:

1. geost/N: These constraints provide a dedicated mini-language for reasoning about multi-dimensional objects. This is a very powerful and flexible approach that is available in SICStus Prolog and also in some other constraint systems.
2. reified constraints. For example, you can state X #= 2 #==> Y #\= 4 to express that Y must not be 4 if X is equal to 2. Thus, (X,Y) is automatically different from (2,4).
3. extensional constraints (available as table/2, fd_relation/2 etc. in many Prolog systems) let you explicitly enumerate the admissible set of tuples or its complement.
4. remodeling your task as selecting between admissible positions by Boolean indicators. See Packing Squares for an example of this approach.

These approaches come with different consequences and trade-offs. My personal preferences and recommendations are roughly reflected in the above order. However, depending on the situation at hand, there may be significant advantages of one approach over the others.

The modeling part in CSPs is sometimes referred to as more of an art than a science also because there are so many different possibilities to choose from, and it is not a priori clear which model is best also because there are so many trade-offs—such as convenience, portability, scalability, speed, memory etc.—involved.