algorithm - 解决此类游戏的最佳方法是什么？

Question

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

目的是将一组实体(如三维的俄罗斯方 block )组合在一起，以一种可行的方式形成一个形状，考虑到只有当它们适合一种运动(忽略旋转，仅旋转 90°)。

检查 this图片出来明白我的意思。

Answer 1

在我最近的 CS 类(class)中，我们制作了一个通用的解谜器，它通过将状态表示为 C++ 中的对象来工作。每个对象都有一个方法来将它所代表的状态与另一个状态进行比较。这用于内存，以确定是否已经看到状态。每个状态也有一种方法来生成从该状态可直接到达的状态(即旋转 block 、放置 block 、移动 block )。求解器通过维护一个状态队列来工作，从队列的前面弹出一个状态，检查它是否是所需的状态(即拼图已解决)。如果不是，则检查内存(我们使用散列集)以查看状态是否已经被看到。如果不是，则生成从当前状态可达的状态并将其附加到队列的尾部。一个空队列表示一个无法解决的难题。

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