algorithm - 解决这种游戏的最佳方法是什么？

Question

今天晚上我试图解决一个木头拼图，所以我想知道哪种方法是以编程方式解决此类问题的最佳方法。

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

查看这张图片以了解我的意思。

Answer 1

在我最新的 CS 课程中，我们制作了一个通用的解谜器，它通过将状态表示为 C++ 中的对象来工作。每个对象都有一个方法来比较它所代表的状态和另一个状态。这用于记忆，以确定是否已经看到状态。每个状态也有一种方法来生成从该状态可直接到达的状态（即旋转一个方块、放置一个方块、移动一个方块）。求解器通过维护一个状态队列、从队列前面弹出一个状态、检查它是否是所需状态（即解谜）来工作。如果不是，则检查记忆（我们使用散列集）以查看是否已经看到状态。如果不是，则生成从当前状态可到达的状态并将其附加到队列的后面。一个空队列标志着一个无法解决的难题。

为 3D 概念化类似的东西会很困难，但这是计算机化解谜的基本方法。

Answer 2

似乎是 3维多米诺包装问题的一个更简单的子集。关于该主题有各种学术论文。

Answer 3

因为这是一个或多或少的小问题，因为对于计算机而言，可能存在少量组合，我会尝试一个简单的搜索算法。我的意思是一种算法，它检查每个可能的配置，并从这个配置的结果继续下去，直到它最终形成一个最终配置，在你的例子中是多维数据集。

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

Answer 4

如果您要处理的难题是您链接的照片中的那个难题，那么只需搜索一棵可能的解决方案树，直到找到通往底部的路，这可能是可行的。

如果每个拼图块是一些贴在它们脸上的立方体，并且我要通过将每个拼图块放入一个更大的立方体中来解决这个难题，每个边上 4 次作为组成立方体，那么我将按以下步骤进行。

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

如果给定旋转，然后将原始立方体平移到该块的任何其他立方体，则尝试通过寻找产生相同最终块的可能方向来剔除搜索空间，从而产生与先前完全相同的占用体积考虑轮换，从未来考虑中剔除该轮换。

从袋子里拿出一块。如果袋子里没有碎片，那么这是一个解决方案。循环通过溶液体积的每个单元格，以及每个单元格的拉片的每次旋转。如果该片段完全在搜索量内，并且不与任何其他片段重叠，则递归到本段。否则，进行下一个轮换，或者如果没有更多轮换，则进行下一个单元格，或者如果没有更多单元格，则返回无解。

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