在 Prolog 中解决七巧板谜题的好方法是什么？
我不确定这是否最好属于这里或数学，但我想我也可以在这里得到一些关于代码的指示。 对于一项作业，我需要使用 Prolog 解决凸七巧板谜题。
所有拼图和可用块都定义为顶点列表。例如： puzzle(1,[(0,0),(4,0),(4,4),(0,4)]) 表示方形拼图，而 piece(1,[ (0,0),(4,0),(2,2)]) 可能是大三角形之一。
我已经用 id 和点列表定义了所有 7 个部分，我认为我应该能够编写正确的代码来迭代这些部分并对它们执行一些操作。然而，我在几何方面并没有那么有洞察力，所以我不知道如何仅根据其顶点来确定哪一块适合拼图上的哪个位置。
本课程中的大部分作业都是基于经典的组合问题，例如旅行商。是否有任何涉及凸形状（或任何类型的形状）的问题可能会激发我想出解决方案？我很难找到以这种方式处理形状的声明性代码的在线示例。如果我知道要寻找什么，那将会非常有帮助。
我想我可以通过检查拼图的外边界是否被覆盖一次以及内部边界（由放置碎片产生的）是否被覆盖两次来验证解决方案是否正确。我可能可以使用这个事实作为我的解决方案的某些部分的基本案例。除此之外，我目前能想到的最好的办法就是将每一块强制放入拼图边界之间的某个未占用的空间中，直到它们适合为止。
I'm not sure if this best belongs here or in math but I figure I can get some pointers here about the code as well.
For an assignment I need to solve convex Tangram puzzles using Prolog.
All puzzles and available pieces are defined as lists of vertices. For example:puzzle(1,[(0,0),(4,0),(4,4),(0,4)]) represents a square puzzle and piece(1,[(0,0),(4,0),(2,2)]) could be one of the large triangles.
I already have defined all 7 pieces with an id and a list of points and I think I should be able to write the proper code to iterate through these pieces and perform some operations on them. However, I'm not that insightful when it comes to geometry so I have no clue how I could determine which piece fits where on a puzzle simply based on its vertices.
Most of the assignments in this course are based on classic combinatorial problems such as Travelling Salesman. Are there any such problems involving convex shapes (or any kind of shape) that might inspire me to come up with a solution? I'm having a hard time finding online examples of declarative code that deals with shapes in this way. It would be very helpful if I knew what to look for.
I figure I can verify a solution is correct by checking if the outer borders of the puzzle are covered once and the inner ones (resulting from placing pieces) are covered twice. I could probably use this fact as a base case for some part of my solution. Other than that the best I can think of at the moment is brute forcing every piece into some unoccupied space between the borders of the puzzle till they fit.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是否必须用纯 Prolog 来解决问题，还是也可以使用约束编程？
如果你会使用 CP，那么请看一下这篇论文：Perspectives on基于逻辑的推理方法
关于行动和改变。第 6 节描述了作者如何使用 CLP(FD) 解决七巧板问题。
也许这篇论文给了你一个想法如何解决它，即使你必须使用纯 Prolog，因为约束可以被被动测试取代。然而，搜索将花费更长的时间，因为搜索树不会被约束修剪。
我还记得我很久以前参加的 CLP 课程中有人使用 Gröbner 基底来推理几何（“如何在急转弯处移动钢琴？”），尽管我不确定这是否适用于解决七巧板。
如果这有点理论性和高级性，我很抱歉。
Do you have to solve the problem with pure Prolog, or can you use Constraint Programming as well?
If you can use CP, then take a look at this paper: Perspectives on Logic-based Approaches for Reasoning
About Actions and Change. Section 6 describes how the authors solved tangram with CLP(FD).
Maybe the paper gives you an idea how to solve it even if you have to use pure Prolog, since constraints can be replaced by passive tests. The search will then take longer, though, since the search tree won't be pruned by the constraints.
I also remember that someone in a CLP course I took long ago used Gröbner bases to reason about geometry ("how to move a piano around a tight corner?"), although I'm not sure whether that would be applicable for solving tangrams.
I'm sorry if that's all a bit theoretical and advanced.
我认为解决这个问题的关键应该是检测碎片的重叠。根据定义，如果不发生重叠，则每个允许的放置都将是一个解决方案。然后，迭代片段的放置，我们应该检测是否发生任何重叠。
每个形状都可以表示为单位网格细分所产生的最小三角形的并集。我们一共有100个（4*5*5）个小三角形。
因此，当我们将坐标列表正确转换为小三角形列表时，可以通过交集轻松检测到重叠。
例如，按升序坐标和顺时针编号，
piece(1, [(0,0), (1,1), (2,0)])变为[2, 3 , 4, 7]。如果我们注意到每次旋转：X'=Y 且 Y'=-X，则绕原点顺时针旋转形状 90° 是很容易的。上面的片段顺时针旋转 90°：piece(1, [(0,0), (1,-1), (0,-2)])。当在 Y 上标准化时：piece(1, [(0,2), (1,1), (0,0)])。
确定哪些小三角形覆盖了一个形状，可以简单地对每个三角形重复“多边形中的点”测试小三角形。
I think the key to solve this problem should be detection of pieces' overlapping. By definition, if no overlapping occurs, each admissible placement will be a solution. Then, iterating piece' placement we should detect if any overlapping occurs.
Each shape can be represented as the union of the smallest triangles resulting from subdivision of unit grid. We have a total of 100 (4*5*5) small triangles.
Thus overlapping can easily be detected by intersection, when we have a proper translation of list of coords to list of small triangles.
For instance, numbering in ascending coords and clockwise, the
piece(1, [(0,0), (1,1), (2,0)])becomes[2, 3, 4, 7].Rotating a shape clockwise of 90° around the origin it's easy, if we note that for each rotation: X'=Y and Y'=-X. The piece above, rotated 90° clockwise: piece(1, [(0,0), (1,-1), (0,-2)]). When normalized on Y: piece(1, [(0,2), (1,1), (0,0)]).
Determining which small triangles cover a shape can be done naively repeating the 'point in polygon' test for each small triangle.