哪种解决这种游戏最好的方法是？

Question

今天晚上我试图解决一个木拼图，所以我想知道哪种方法是找到解决这种类型的问题programmaticaly的最佳途径。

其目的是将一组固体（如三维中的俄罗斯方块）组合在一起形成一个可行的形状，考虑到这样一个事实，只有当它们合适时才可以将部件连接或滑入结构这种运动（忽略旋转，只有90°转弯）。

查看this图片了解我的意思。

Answer 1

在我最新的CS类中，我们制作了一个通用的拼图求解器，它通过将状态表示为C++中的对象来工作。每个对象都有一个方法来比较它表示的状态与另一个状态。这是用于memoization，以确定是否已经看到国家。每个状态还有一种方法来生成可以从该状态直接到达的状态（即旋转块，放置块，移动块）。解算器通过维护一系列状态来工作，从队列的前面弹出一个状态，检查它是否是所需的状态（即解决难题）。如果没有，则检查记忆（我们使用哈希集合）以查看状态是否已经被看到。如果不是，则从当前状态可达的状态被生成并附加到队列的后部。一个空队列表示一个无法解决的难题。

概念化类似3D的东西很难，但这是计算机化拼图解决方案的基本方法。

Answer 2

由于这是一个或多或少的小问题，因为对于一台计算机有少量的组合可能我会尝试一个简单的搜索算法。 我的意思是一个algorithm，它检查每个可能的配置，并从这个配置的结果继续，直到它结束在一个结束配置，在你的情况下多维数据集。

问题接踵而来就是要编写一个能够执行从一个状态到另一个状态的所有状态检查和转换的程序。因为您必须查看配置在物理上是否可行。

Answer 3

似乎是一个三维polyomino包装问题的更容易的子集。关于这个问题有各种各样的scholarly papers。

Answer 4

如果您想处理的难题是您已链接的照片中的问题，那么只需在可能的解决方案树中进行搜索，直到您找到自己的方式就可行了。

如果每个拼图是连接在它们脸上的多个立方体，并且我将通过将每个拼块装入一个更大的立方体中来解决拼图，每个边缘上有4次作为拼合立方体，然后我继续如下。

声明每个作品的任意立方体作为其原点。观察每个拼图块有24个可能的旋转，原点立方体每个可能的面朝上的一个方向，围绕该位置的垂直轴旋转4次。

尝试通过查找产生相同最后一块的可能方位来甄别搜索空间，如果给定的旋转，然后将原始立方体转换为该块的其他立方体的任何一个导致完全相同的占用作为以前考虑的轮换量，从未来的考虑中剔除轮换量。

从包里拉出一块。如果包内没有碎片，那么这是一个解决方案。循环通过溶液体积的每个单元格，并且每个单元格的被拉动的片段的每次旋转。如果作品完全处于搜索范围内，并且与其他作品没有重叠，请进入本段。否则，请继续下一个旋转，或者如果没有更多旋转，请继续到下一个单元，或者如果没有更多单元，则返回没有解决方案。

如果最后一段返回没有解决方案，那么这个难题是无法解决的。