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

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

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 框中的所有单元格都被覆盖了。

Answer 2

Cumulative 只会检查单个维度的资源使用情况（这很有用，有时可以很好地修剪），它不能确保不重叠属性。 diffn global constraint 是用于确保无重叠的规范。

Using Cumulative function for Rectangular Placement