CODEWITHSUNDEEP
prologstructureclp
sten
sten

Reputation: 7476

CLP: Constraints on structured variables?

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.

Upvotes: 4

Views: 211

Answers (2)

mat
mat

Reputation: 40768

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.

Upvotes: 4

jschimpf
jschimpf

Reputation: 5034

In cases like yours, where the "structured variables" have a fixed structure containing only numeric fields, you don't need a notion of "structured variable". You conceptually just work with tuples of numbers (or numeric variables).

Sometimes these tuples are best represented as lists, because then you can directly apply global constraints that take lists as arguments. For example, to constrain a point [X,Y] not to be on a diagonal, you could write

alldifferent([X,Y])

or use a table-constraint to constrain it to a given set of coordinates:

table([[X,Y]], [[1,2],[2,4],[3,1],[4,3]])

In other cases it is nicer to use structures with descriptive functors such as point(X,Y) or rect(X1,Y1,X2,Y2), and then write your corresponding constraint wrappers, such as

points_differ(point(X,Y), point(V,W)) :-
    X#\=V or Y#\=W.

or

rect_contains_point(rect(I,J,K,L), point(PI,PJ)) :-
    I #=< PI, PI #=< K,
    J #=< PJ, PJ #=< L.

(The latter example is taken from http://eclipseclp.org/examples/shikaku.ecl.txt)

Upvotes: 3

Related Questions