Нахождение всех комбинаций - N прямоугольников внутри квадрата

Следующая модель находит решения за пару секунд:

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

Позиции сетки в sqare могут быть пустыми или принимать одно из шести значений. Модель определяет верхний и нижний ряды всех прямоугольников. Вместе с левым и правым столбцами он гарантирует, что все плитки в этих пределах принадлежат одному прямоугольнику.

Чтобы поэкспериментировать, полезно начать с меньшего размера квадрата и / или меньшего количества прямоугольников. Также имеет смысл ограничить размер прямоугольников. В противном случае прямоугольники могут стать слишком маленькими (1x1) или слишком большими.

Нарушение симметрии для обеспечения определенного порядка прямоугольников действительно ускоряет процесс решения.

Вот еще одно решение, использующее ограничение MiniZincs Geost. Это решение в значительной степени основано на отличном ответе Патрика Трентинса, который здесь. Пожалуйста, не забывайте отдавать ему должное, если это вам помогло. Также не забудьте увидеть его объяснение на модели.

Я предполагаю, что использование ограничения geost немного ускоряет процесс. Нарушение симметрии может еще больше ускорить процесс, как предлагает Аксель Кемпер.

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

Это означает, что первый прямоугольник помещается в [7, 0] и принимает форму [2,3], как показано на этом рисунке:

Основываясь на ответе @Phonolog, один из способов получить желаемый выходной формат - использовать 2d-массив m, который сопоставлен с x через ограничения (здесь size - размер ограничивающего прямоугольника):

% mapping to a 2d-array output format
set of int: SIDE     = 0..size-1;

array[SIDE, SIDE] of var 0..nObjects: m;
    
constraint forall (i, j in SIDE) ( m[i,j] = sum(o in OBJECTS)(o * 
    (i >= x[o,1] /\ 
     i <= x[o,1] + rect_size[kind[o],1]-1 /\ 
     j >= x[o,2] /\ 
     j <= x[o,2] + rect_size[kind[o],2]-1)) );
    
% symmetry breaking between equal objects
array[OBJECTS] of var int: pos = [ size*x[o,1] + x[o,2] | o in OBJECTS ];

constraint increasing([pos[o] | o in 1..nObjects-1]);
    
solve satisfy;

output ["kind=\(kind)\n"] ++
["x=\(x)\n"] ++
["m="] ++ [show2d(m)]

Изменить: вот полный код:

include "globals.mzn";

int: k = 2;
int: nObjects = 6;
int: nRectangles = 4;
int: nShapes = 4;
int: size = 10;

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 = [0, 0];
array[DIMENSIONS] of int:             u = [size, size];
array[OBJECTS,DIMENSIONS] of var int: x;
array[OBJECTS] of var SHAPES:         kind;

array[RECTANGLES,DIMENSIONS] of int: rect_size = [|
    3, 2|
    2, 3|
    5, 3|
    3, 5|];
array[RECTANGLES,DIMENSIONS] of int: rect_offset = [|
    0, 0|
    0, 0|
    0, 0|
    0, 0|];
array[SHAPES] of set of SHAPES: shape = [
    {1}, {2}, {3}, {4}];

array[OBJECTS] of set of SHAPES: valid_shapes = 
    [{1, 2}, {1, 2}, {1, 2}, {1, 2}, {1, 2}, {3, 4}];
    
constraint forall (obj in OBJECTS) (
    kind[obj] in valid_shapes[obj]
);

constraint
    geost_bb(
        k,
        rect_size,
        rect_offset,        
        shape,
        x,
        kind,
        l,
        u
    );
    
% mapping to a 2d-array output format
set of int: SIDE     = 0..size-1;

array[SIDE, SIDE] of var 0..nObjects: m;

constraint forall (i, j in SIDE) ( m[i,j] = sum(o in OBJECTS)(o * 
    (i >= x[o,1] /\ 
     i <= x[o,1] + rect_size[kind[o],1]-1 /\ 
     j >= x[o,2] /\ 
     j <= x[o,2] + rect_size[kind[o],2]-1)) );


% symmetry breaking between equal objects
array[OBJECTS] of var int: pos = [ size*x[o,1] + x[o,2] | o in OBJECTS ];

constraint increasing([pos[o] | o in 1..nObjects-1]);

solve satisfy;

output ["kind=\(kind)\n"] ++
["x=\(x)\n"] ++
["m="] ++ [show2d(m)]