I'm trying to solve a constraint processing problem in prolog.
I need to pack 4 squares of 5x5,4x4,3x3 and 2x2 in a grid of 10x10. They may not overlap.
My variables look like this:
Name: SqX(i), i=1..10, domain: 1..10
Where X is either 5,4,3 or 2. The index i represents the row, the domain the column in the grid.
My first constraints try to define the width and height of the squares. I formulate it as such:
Constraint: SqX(i) > SqX(j)-X /\ i>j-X, range: i>0 /\ j>0
So that the possible points are constrained to be within X rows and columns from each other. Prolog however, stops on these constraints and gives the following result:
Adding constraint "(Sq5_I > Sq5_J-5) /\ (I>J-5)" for values:
I=1, J=1,
I=1, J=2,
I=1, J=3,
I=1, J=4,
I=1, J=5,
I=1, J=6,
=======================[ End Solutions ]=======================
So it stops there, not even checking the other squares. My constraints are most likely too tight, but I can't see why or how. Any suggestions?
For each square, define
X
andY
variables that denote the upper left corner. These variable will have domains1..10-L
, whereL
is the length of the square. If you set the domain to1..10
, the squares may be placed partly outside your 10x10 rectangle.Then you can post constraints for each pair of rectangles
(X,Y)
and(X1,Y1)
that state that if they overlap on the x axis, they must not overlap on the y axis, and vice versa:(your particular constraint syntax may vary)