constraint-programming - 使用累积函数进行矩形放置

Question

我有一个矩形放置问题。我想要的是将大小为 x x y 的矩形不重叠地放置到另一个矩形中。我最终想要的是每个矩形的起点。

我为此编写了这部分代码，其逻辑是它将沿函数的高度和宽度累积检查 x 轴和 y 轴。但是，当我运行它时，它适用于少数情况，但不适用于其他情况。所以我贴了其中一个具体的实例，它在这里给出了重复点，询问问题是什么以及可以进行哪些更改。

谢谢

constraint cumulative(start, x, y, height);
constraint cumulative(starty, y, x, width);

Answer 1

如果您添加限制框不重叠的 diffn 约束，它应该可以工作，即

include(globals.mzn);
....
constraint diffn(start,starty,x,y);
... 

参见 https://www.minizinc.org/doc-2.4.3/en/lib-globals.html?highlight=diffn有关 diffn 的更多信息。

10752的解决方案之一是:

15  15
10
1: 3 3  0 9
2: 3 4  12 0
3: 3 5  12 10
4: 3 6  12 4
5: 3 7  9 8
6: 3 8  9 0
7: 3 9  0 0
8: 3 12 3 0
9: 3 15 6 0
10: 6 3 0 12

我在纸上检查过这是一个正确的解决方案，即没有重叠并且 15x15 框中的所有单元格都被覆盖了。