Finding all the Combinations - N Rectangles inside the Square

Question

I am a beginner in Constraint Programming using Minizinc and I need help from experts in the field.

How can I compute all the possible combinations: 6 Rectangles inside the Square (10x10) using Minizinc?

Considering that the RESTRICTIONS of the problem are:

1) No Rectangle Can Overlap

2) The 6 rectangles may be vertical or horizontal

OUTPUT:

---

0,1,1,0,0, . . . , 0,0,6,6,6
1,1,1,0,0, . . . , 0,0,0,4,4
0,0,5,5,0, . . . , 0,0,1,1,1
0,0,0,2,2, . . . , 0,0,0,0,0
0,0,0,0,2, . . . , 0,0,0,0,0
6,6,6,0,0, . . . , 0,4,4,4,0
Continue Combination...

---

Answer 1

The following model finds solutions within a couple of seconds:

%  Chuffed: 1.6s
%  CPLEX:   3.9s
%  Gecode:  1.5s

int: noOfRectangles = 6;
int: squareLen = 10;
int: Empty = 0;

set of int: Coords = 1..squareLen;
set of int: Rectangles = 1..noOfRectangles;

%  decision variables:
%  The square matrix
%  Every tile is either empty or belongs to one of the rectangles
array[Coords, Coords] of var Empty .. noOfRectangles: s;

%  the edges of the rectangles
array[Rectangles] of var Coords: top;
array[Rectangles] of var Coords: bottom;
array[Rectangles] of var Coords: left;
array[Rectangles] of var Coords: right;

%  function
function var Coords: getCoord(Coords: row, Coords: col, Rectangles: r, Coords: coord, Coords: defCoord) =
  if s[row, col] == r then coord else defCoord endif;
    
%  ----------------------<  constraints  >-----------------------------
  
%  Determine rectangle limits as minima/maxima of the rows and columns for the rectangles.
%  Note: A non-existing rectangle would have top=squareLen, bottom=1, left=squareLen, right=1
%  This leads to a negative size and is thus ruled-out.
constraint forall(r in Rectangles) (
  top[r] == min([ getCoord(row, col, r, row, squareLen) | row in Coords, col in Coords])
);
constraint forall(r in Rectangles) (
  bottom[r] == max([ getCoord(row, col, r, row, 1) | row in Coords, col in Coords])
);
constraint forall(r in Rectangles) (
  left[r] == min([ getCoord(row, col, r, col, squareLen) | row in Coords, col in Coords])
);
constraint forall(r in Rectangles) (
  right[r] == max([ getCoord(row, col, r, col, 1) | row in Coords, col in Coords])
);

%  all tiles within the limits must belong to the rectangle
constraint forall(r in Rectangles) (
  forall(row in top[r]..bottom[r], col in left[r]..right[r]) 
    (s[row, col] == r)
);

%  enforce a minimum size per rectangle
constraint forall(r in Rectangles) (
  (bottom[r] - top[r] + 1) * (right[r] - left[r] + 1) in 2 .. 9 
);

%  symmetry breaking: 
%  order rectangles according to their top/left corners
constraint forall(r1 in Rectangles, r2 in Rectangles where r2 > r1) (
 (top[r1]*squareLen + left[r1]) < (top[r2]*squareLen + left[r2])
);


%  output solution

output [ if col == 1 then "\n" else "" endif ++ 
         if "\(s[row, col])" == "0" then "  " else "\(s[row, col]) " endif 
         | row in Coords, col in Coords];

The grid positions in the sqare can be empty or assume one of six values. The model determines the top and bottom rows of all rectangles. Together with the left and right columns, it makes sure that all tiles within these limits belong to the same rectangle.

To experiment, it is helpful to start with smaller square dimensions and/or smaller numbers of rectangles. It might also make sense to delimit the size of rectangles. Otherwise, the rectangles tend to become too small (1x1) or too big.

Symmetry breaking to enforce a certain ordering of rectangles, does speed-up the solving process.