Prolog Constraint Processing : Packing Squares

Question

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?

Answer 1

For each square, define X and Y variables that denote the upper left corner. These variable will have domains 1..10-L, where L is the length of the square. If you set the domain to 1..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:

(((X  #=< X1) and (X+L   #> X1)) => ((Y+L #=< Y1) or (Y1+L1 #=< Y))), (((X1 #=< X)  and (X1+L1 #> X))  => ((Y+L #=< Y1) or (Y1+L1 #=< Y))), (((Y  #=< Y1) and (Y+L   #> Y1)) => ((X+L #=< X1) or (X1+L1 #=< X))), (((Y1 #=< Y)  and (Y1+L1 #> Y))  => ((X+L #=< X1) or (X1+L1 #=< X))) 

(your particular constraint syntax may vary)