constraint-programming - 找到所有组合 - 正方形内的 N 个矩形

Question

我是使用 Minizinc 进行约束编程的初学者，我需要该领域专家的帮助。
如何使用 Minizinc 计算所有可能的组合:正方形(10x10)内的 6 个矩形？
考虑到问题的 RESTRICTIONS 是:

1) No Rectangle Can Overlap

2) The 6 rectangles may be vertical or horizontal

输出:
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
继续组合...

Answer 1

这是使用 MiniZincs Geost 约束的另一个解决方案。这个解决方案很大程度上基于 Patrick Trentins 的优秀回答 here .如果这对您有帮助，请务必给他一些荣誉。还要确保看到他对模型的解释。
我假设使用 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]，如下图所示: