3

我正在研究一个名为“除以盒子”的谜题。本质上，它是一种基于给定线索的完美矩形拟合形式。规则是：

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

例如：

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 的内置 search/6 并能够轻松地尝试不同的搜索启发式。

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

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

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

问题输入数据：

语法：问题（ID，宽度，高度，提示）（提示是三元组：（I，J，Value））

问题(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)])。

问题(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)])。

问题(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)])。

问题(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)])。

问题(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)])。

4

1 回答 1

3

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

如果这是家庭作业，让我给出一些建议。我将首先定义一些辅助谓词，例如

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.

这与您在ECLiPSe网站上的平铺示例中找到的方法相同。

编辑

感谢提供问题实例。我在不到 1.5 秒的时间内获得了所有这些问题的解决方案，以及今天的 30x40 拼图。

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

尽管如此，特别是对于干扰简单结构的附加约束的问题，这种方法可能无法充分扩大规模。出于这个原因，人们开发了专门的放置/包装约束，例如参见disjoint2SICStus或nooverlapGecode。后者在 ECLiPSe 中也可以通过disjoint2/1in 获得library(gfd)。

附言

正如@SeekAndDestroy 所报道的，标记策略smallest（选择其域中当前最小值的变量）给出了更好的结果。此外，使用library(gfd)而不是library(ic)提供进一步的加速。我已将我的解决方案添加到 ECLiPSe 网站上的示例中。

于 2016-03-18T00:01:49.063 回答