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

以下模型在几秒钟内找到解决方案：

%  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];

方格中的网格位置可以为空或采用六个值之一。该模型确定所有矩形的顶行和底行。与左右列一起，确保这些限制内的所有图块都属于同一个矩形。

为了进行实验，从较小的正方形尺寸和/或较少数量的矩形开始是有帮助的。界定矩形的大小也可能有意义。否则，矩形往往会变得太小 (1x1) 或太大。

对称破坏以强制执行矩形的某种顺序，确实加快了求解过程。

Answer 2

这是使用 MiniZincs Geost 约束的另一个解决方案。该解决方案主要基于帕特里克Trentins优秀的答案在这里。如果这对您有帮助，请务必给他一些荣誉。还要确保看到他对模型的解释。

我假设使用 geost 约束会稍微加快这个过程。正如 Axel Kemper 所建议的那样，对称性破坏可能会进一步加快速度。

include "geost.mzn";

int: k;
int: nObjects;
int: nRectangles;
int: nShapes; 

set of int: DIMENSIONS = 1..k;
set of int: OBJECTS    = 1..nObjects;
set of int: RECTANGLES = 1..nRectangles;
set of int: SHAPES     = 1..nShapes;

array[DIMENSIONS] of int:             l;
array[DIMENSIONS] of int:             u;
array[RECTANGLES,DIMENSIONS] of int:  rect_size;
array[RECTANGLES,DIMENSIONS] of int:  rect_offset;
array[SHAPES] of set of RECTANGLES:   shape;
array[OBJECTS,DIMENSIONS] of var int: x;
array[OBJECTS] of var SHAPES:         kind;


array[OBJECTS] of set of SHAPES: valid_shapes;

constraint forall (obj in OBJECTS) (
    kind[obj] in valid_shapes[obj]
);

constraint geost_bb(k, rect_size, rect_offset, shape, x, kind, l, u);

以及相应的数据：

k = 2;                 % Number of dimensions
nObjects = 6;          % Number of objects
nRectangles = 4;       % Number of rectangles
nShapes = 4;           % Number of shapes

l = [0, 0];            % Lower bound of our bounding box
u = [10, 10];          % Upper bound of our bounding box

rect_size = [|
     2, 3|
     3, 2|

     3, 5|
     5, 3|];
     

rect_offset = [|
     0, 0|
     0, 0|
     
     0, 0|
     0, 0|];
     
shape = [{1}, {2}, {3}, {4}];
    
    
valid_shapes = [{1, 2}, {1, 2}, {1, 2}, {1, 2}, {1, 2}, {3, 4}];

输出读数略有不同。拿这个例子：

x = array2d(1..6, 1..2, [7, 0, 2, 5, 5, 0, 0, 5, 3, 0, 0, 0]);
kind = array1d(1..6, [1, 1, 1, 1, 1, 3]);

这意味着矩形 1 被放置在 [7, 0] 并采用形状 [2,3]，如下图所示：