3

我不确定这是最好的还是属于数学的，但我想我也可以在这里得到一些关于代码的指针。对于作业，我需要使用 Prolog解决凸七巧板谜题。

所有的谜题和可用的部分都被定义为顶点列表。例如： puzzle(1,[(0,0),(4,0),(4,4),(0,4)])代表一个方形拼图，piece(1,[(0,0),(4,0),(2,2)])可能是大三角形之一。

我已经用一个 id 和一个点列表定义了所有 7 个片段，我认为我应该能够编写适当的代码来遍历这些片段并对它们执行一些操作。但是，我在几何方面并不是那么有见地，所以我不知道如何仅根据其顶点来确定哪一块适合拼图的哪个位置。

本课程中的大部分作业都是基于经典的组合问题，例如旅行推销员。是否有任何涉及凸形（或任何类型的形状）的问题可能会激发我提出解决方案？我很难找到以这种方式处理形状的声明性代码的在线示例。如果我知道要寻找什么，那将非常有帮助。

我想我可以通过检查拼图的外边界是否被覆盖一次而内部边界（由于放置碎片）是否被覆盖两次来验证解决方案是否正确。我可能会将此事实用作解决方案某些部分的基本案例。除此之外，我目前能想到的最好的办法就是将每一块拼图的边界强制放入一些未占用的空间，直到它们适合为止。

4

2 回答 2

2

您必须使用纯 Prolog 解决问题，还是也可以使用约束编程？

如果您可以使用 CP，请查看这篇论文：Perspectives on Logic-based Approaches for Reasoning About Actions and Change。第 6 节描述了作者如何使用 CLP(FD) 解决七巧板。

即使您必须使用纯 Prolog，也许该论文会为您提供如何解决它的想法，因为可以用被动测试代替约束。但是，搜索将花费更长的时间，因为搜索树不会被约束修剪。

我还记得我很久以前参加的 CLP 课程中有人使用 Gröbner 基础来推理几何（“如何在狭窄的角落移动钢琴？”），尽管我不确定这是否适用于解决七巧板。

如果这有点理论和先进，我很抱歉。

于 2011-11-09T07:32:25.663 回答
1

我认为解决这个问题的关键应该是检测碎片的重叠。根据定义，如果没有发生重叠，则每个可接受的位置都是一个解决方案。然后，迭代片的位置，我们应该检测是否发生任何重叠。

每个形状都可以表示为由单位网格细分产生的最小三角形的联合。我们总共有 100 个（4*5*5）个小三角形。

因此，当我们将坐标列表正确转换为小三角形列表时，可以通过交集轻松检测到重叠。

例如，以升序和顺时针方向编号，piece(1, [(0,0), (1,1), (2,0)])变为[2, 3, 4, 7].

绕原点顺时针旋转 90° 形状很容易，如果我们注意到每次旋转：X'=Y 和 Y'=-X。上面的部分，顺时针旋转 90°：piece(1, [(0,0), (1,-1), (0,-2)])。在 Y 上标准化时：piece(1, [(0,2), (1,1), (0,0)])。

确定哪些小三角形覆盖一个形状可以简单地重复每个小三角形的“多边形中的点”测试。

于 2011-11-11T15:41:00.613 回答