prolog - ECLiPSe CLP 拼图 : perfect rectangle fitting

Question

我正在研究一个名为“按框划分”的谜题。本质上，它是一种基于给定线索的完美矩形拟合形式。规则是:

• 一些网格单元包含数字(这是已知的输入数据)
• 任务是将网格区域划分为满足以下约束的矩形房间:每个房间只包含一个数字，房间的总面积等于其中的数字

例如:

4 _ 2
_ _ _
_ 3 _

有解决办法:

+-----------+
| 4  . | 2  |
| .  . | .  |
|------+----+
| .   3  .  |
+-----------+

我已经编写了约束条件和一个小型有限域求解器，它可以有效地为每个提示提供所有可能的矩形放置，就像这样(坐标从 (1,1) 开始并从左上角移动到右下角):

% Syntax: rectangle(X,Y,Width,Height,HintValue)
[
  [rectangle(1, 1, 2, 2, 4)],
  [rectangle(2, 1, 2, 1, 2), rectangle(3, 1, 1, 2, 2)],
  [rectangle(1, 3, 3, 1, 3), rectangle(2, 1, 1, 3, 3)]
]

我随后尝试编写自己的求解器，该求解器基于检查重叠约束(即，如果两个矩形水平重叠，则它们不应垂直重叠，反之亦然)。它适用于小谜题，但是，由于广泛的约束检查，我的两次尝试都没有成功地扩大到大于 ~ 15x15 的谜题。

因此，我们的目标是找到一个可以扩展到更大谜题的模型，如果可能的话，可以使用 ECLiPSe 的内置搜索/6 并能够轻松地尝试不同的搜索启发式方法。

有什么想法/想法吗？提前致谢!

注意:我正在使用整数 IC 域库(= lib(ic))

(编辑他们现在都在不到半秒内解决，以防有人对运行时间结果感兴趣)

问题输入数据:

Syntax: problem(ID,Width,Height,Hints) (Hints are triplet-tuples: (I,J,Value))

problem(p(15,1),15,15,[(9,1,4),(11,1,2),(12,1,3),(14,1,3),(2,2,4),(3,2,2),(4,2,2),(8,2,12),(2,3,3),(10,3,3),(1,4,2),(10,4,11),(15,5,7),(8,7,36),(12,8,24),(3,9,27),(13,9,24),(15,9,7),(4,11,3),(8,11,2),(7,12,6),(8,12,2),(7,13,3),(8,13,2),(10,13,3),(4,14,7),(9,14,3),(10,14,2),(11,14,2),(12,14,6),(6,15,8)]).

problem(p(15,2),15,15,[(1,1,9),(11,1,2),(13,1,2),(7,3,36),(13,4,3),(14,4,16),(1,6,2),(7,6,24),(4,7,3),(6,7,8),(2,8,6),(3,8,3),(9,8,7),(7,9,9),(15,9,5),(1,10,5),(3,10,2),(11,10,16),(14,10,5),(1,12,2),(4,12,2),(6,12,3),(10,12,6),(11,12,2),(3,13,3),(7,13,2),(12,13,5),(13,13,7),(1,14,2),(14,14,26),(15,14,2)]).

problem(p(20,1),20,20,[(2,1,2),(4,1,2),(11,1,4),(13,1,2),(1,2,2),(5,2,12),(9,2,35),(16,3,15),(19,3,20),(1,4,2),(1,5,2),(4,6,8),(20,6,5),(14,7,2),(3,8,10),(10,8,5),(1,10,4),(5,11,30),(15,13,60),(7,14,24),(12,14,54),(14,14,13),(9,15,54),(1,16,8),(16,18,6),(17,18,3),(19,18,2),(20,18,8),(20,19,3),(18,20,3)]).

problem(p(20,2),20,20,[(3,1,3),(6,1,2),(8,1,4),(2,2,2),(4,2,4),(9,2,3),(16,2,15),(17,2,3),(18,2,6),(11,3,2),(19,3,2),(20,3,3),(1,4,4),(5,4,7),(9,4,2),(17,4,7),(19,4,2),(4,5,5),(9,5,2),(10,5,3),(12,5,9),(1,6,2),(2,6,2),(7,6,18),(2,7,2),(10,7,2),(13,7,20),(1,9,20),(20,9,3),(4,10,3),(11,10,45),(15,12,28),(19,12,2),(20,12,2),(5,13,2),(8,13,3),(15,13,40),(6,14,2),(9,14,12),(3,15,14),(5,15,4),(6,15,6),(18,15,18),(3,16,2),(4,16,6),(5,18,3),(14,18,15),(17,18,2),(3,19,2),(5,19,4),(10,19,2),(2,20,6),(5,20,3),(6,20,2),(8,20,3),(16,20,2),(17,20,2),(20,20,6)]).

problem(p(25,1),25,25,[(2,1,2),(11,1,10),(15,1,8),(17,1,8),(24,1,2),(13,2,2),(14,2,2),(3,3,6),(12,3,32),(25,3,2),(2,4,2),(4,4,2),(14,4,2),(24,4,8),(25,4,2),(4,5,3),(14,5,4),(13,7,2),(1,8,18),(18,8,56),(21,9,6),(22,9,3),(25,9,4),(2,10,6),(19,10,18),(24,10,4),(10,11,60),(14,11,10),(15,11,4),(23,11,3),(2,12,2),(4,12,5),(10,12,4),(22,12,2),(23,12,3),(24,12,6),(6,13,15),(19,13,2),(21,13,2),(2,14,2),(5,14,28),(17,14,3),(20,14,3),(22,14,2),(18,15,3),(21,15,5),(7,16,7),(12,16,3),(15,16,3),(16,16,2),(9,17,2),(11,17,2),(17,17,3),(20,17,16),(7,18,12),(8,18,2),(9,18,3),(12,18,4),(13,18,9),(19,18,12),(24,18,2),(25,18,3),(1,19,2),(5,19,9),(11,19,2),(3,20,2),(5,20,5),(9,20,2),(20,20,7),(7,21,24),(18,22,6),(20,22,3),(21,22,10),(4,23,6),(5,23,3),(7,23,9),(10,23,12),(16,23,24),(17,23,4),(24,23,5),(1,24,2),(18,24,8),(25,24,2),(2,25,4),(17,25,11)]).

Answer 1

您可以根据有限域约束来表述整个问题，然后使用标准搜索例程求解。无需预先计算各个矩形放置的列表。

如果这是作业，让我给出一些建议。我将从定义一些辅助谓词开始，比如

rect_contains_point(rect(I,J,K,L), point(PI,PJ)) :-
    I #=< PI, PI #=< K,
    J #=< PJ, PJ #=< L.

这在制定整体模型时会派上用场。在这里，我使用了 rect(I,J,K,L) 来表示一个带有角 (I,J) 和 (K,L)< 的矩形，因为事实证明这更便于制定必要的约束条件。

然后您可以将非重叠条件写为

no_overlap(rect(I1,J1,K1,L1), rect(I2,J2,K2,L2)) :-
    K1#<I2 or K2#<I1 or L1#<J2 or L2#<J1.

这与您在 tiling example 中找到的方法相同在 ECLiPSe 上网站。

编辑

感谢您提供问题实例。我在不到 1.5 秒的时间内找到了所有这些问题的答案，还有今天的 30x40 拼图。

有趣的是，使用最朴素的标签策略 input_order 可以获得最佳性能。对于此类具有简单几何结构的问题，通常最好根据变量在几何中的“相邻性”来标记变量，并且在这里简单地使用按行顺序就可以很好地工作。

不过，特别是对于具有扰乱简单结构的额外约束的问题，这种方法可能无法充分扩展。出于这个原因，人们开发了专门的放置/包装约束，例如参见disjoint2 in SICStus或 nooverlap in Gecode .后者也可通过 disjoint2/1 in library(gfd) 在 ECLiPSe 中获得。 .

附言

据@SeekAndDestroy 报道，标记策略smallest(选择其域中当前值最小的变量)给出了更好的结果。此外，使用 library(gfd) 而不是 library(ic) 可以进一步加快速度。我添加了my solution ECLiPSe 网站上的示例。