4

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.

false
  • 10,264
  • 13
  • 101
  • 209
sten
  • 7,028
  • 9
  • 41
  • 63

2 Answers2

4

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.

mat
  • 40,498
  • 3
  • 51
  • 78
3

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)

jschimpf
  • 4,904
  • 11
  • 24
  • do u happen to know if swi-prolog has something akin to table/2 – sten Feb 23 '18 at 21:08
  • 2
    SWI's library(clpfd) has tuples_in/2. – jschimpf Feb 24 '18 at 01:03
  • I have a question to jschimpf.In your code,there are local variables Height and Width in rect_size/2, and they are also constrained. In SWI, I used such local variables with constraints and don't return them to caller, they were gabagecollected and I couldn't get answer. It looks like your code is written in ECLiPSe. I'm interested that you don't have to care local clp variables are gabagecollected in ECLiPSe. – Taku Koyahata Feb 24 '18 at 11:18
  • 1
    @Taku: correct, ECLiPSe will not lose any unsolved constraint, even if you lose access to its variables. The worst that can happen is that your toplevel query terminates with unsolved constraints (= delayed goals, in ECLiPSe terminology). In the example, this does not happen because labeling the rectangle variables leads, via propagation, to instantiation of these auxiliary Height/Width variables. If that were not the case, you would have to pass these variables to a labeling routine. – jschimpf Feb 24 '18 at 17:23
  • I see. Thank you for the answer! – Taku Koyahata Feb 25 '18 at 11:52