1

我现在开始使用 SICStus Prolog 学习 prolog 中的限制。虽然我知道如何使用它来解决简单的问题，但我有一个练习，我必须解决一个拼图游戏。但是我不知道如何解决这个问题，因为我将有几个具有不同属性（片段）的不同元素，谁能给我一个例子，说明如何在序言中表示片段列表以及我应该使用什么样的限制？

4

1 回答 1

4

对于第一次尝试，我会按照以下方式做一些事情：

对于每个字段，使用 5 个变量。第一个变量表示进入该领域的拼图。每件作品都有自己的 id。对于您在上面的评论中提到的难题，有 12 个部分，因此每个变量的域为 {1..12}：

P #:: 1..12,

其他四个变量表示每个字段的四个边缘，以及放置在该字段中的拼图是否有凹痕或标签。在您的拼图中，每个“上”或“下”面都有一个标签和一个凹痕，因此您表示标签是左侧还是右侧。同样，布尔决策变量。

[EL,EU,ER,ED] #:: 0..1,

一块拼图可以这样编码：

piece(1,  [](0,1,1,0)).

例如，这是您在评论中给出的网站上拼图描述中的 A 部分。

现在您可以定义两个相邻字段之间的相邻关系。由于您有布尔变量，并且选项卡需要满足凹痕，因此您设置了一个约束（不是“限制”），要求总和为一：

R1 + L2 #= 1,

即，第一场棋子的右边缘必须与第二场棋子的左边缘相匹配。

您还为沿边界的边缘设置了类似的约束。

您设置了一个约束，要求所有字段必须包含不同的部分：

alldifferent(Fields),

（其中 Fields 是包含 P 变量的列表）

您需要一个表示拼图方向的变量：

O #:: 0..1,

你只需要一个，因为在你的拼图中，所有的棋子都必须朝向同一个方向。

最后，您需要将每个字段的片段、方向和边缘变量组合在一起的约束，这样当您为字段选择片段（并且方向已知）时，您可以适当地设置边缘变量：

 once(piece(N, [](L,U,V,D))),
 ( ((P#=N) #/\ (O#=0)) #=> ((EL#=L) #/\ (EU#=  U) #/\ (ER#=R) #/\ (ED#=  D)) ),
 ( ((P#=N) #/\ (O#=1)) #=> ((EL#=R) #/\ (EU#=1-D) #/\ (ER#=L) #/\ (ED#=1-U)) ),

（语法不是针对 Sicstus，而是针对 ECLiPSe。不过，FD 约束库应该足够相似）

请注意，在将一块上下颠倒时，我必须反转下边缘的编码。这允许我保持上/下边缘的“总和等于一个”约束，但不是最佳的，因为它阻止我轻松地将信息从边缘变量传播到片段变量（片段可能获得与另一个倒置时）。但是我懒得更改第一次尝试的编码。

（编辑：这应该很容易通过反转下边缘的编码来解决，例如：piece(1, [](0,1,1,1)).，并使用要求相邻部分的上下边缘具有相同值而不是总和的约束。）

将所有内容放在一起并简单地标记 P 变量（在首先实例化方向变量之后）给出了两种解决方案：

?- rapids(S,O).
S = []([](5, 2, 8, 6), [](11, 10, 1, 4), [](3, 9, 12, 7))
O = 0
Yes (0.01s cpu, solution 1, maybe more)
S = []([](5, 3, 11, 12), [](8, 9, 7, 4), [](2, 10, 6, 1))
O = 1
Yes (0.04s cpu, solution 2, maybe more)
No (0.05s cpu)

我使用矩阵而不是列表，以使拼图字段的行更加突出。矩阵还允许更快地访问不同行中的相邻字段。

于 2011-12-01T17:07:33.943 回答