解决这种游戏的最佳方法是什么？
今天晚上，我试图解决一个木头拼图，所以我想知道哪种方法是通过编程找到此类问题的解决方案的最佳方法。
目的是将一组实体（如三维俄罗斯方块）组合在一起，以一种可行的方式形成一个形状，并考虑到只有当它们适合运动类型时，才可以将块附着或滑入结构中（忽略旋转，仅旋转 90°）。
检查这张图片来理解我的意思。
This evening I tried to solve a wood puzzle so I wondered which is the best way to find a solution to this kind of problem programmaticaly.
The aim is to combine a set of solids (like tetris pieces in three dimensions) together to form a shape in a feasable way that takes into account the fact that pieces can be attached or slided into the structure only if they fit the kind of movement (ignore rotations, only 90° turns).
Check this picture out to understand what I mean.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
在我最新的 CS 课程中，我们制作了一个通用的谜题求解器，它通过将状态表示为 C++ 中的对象来工作。 每个对象都有一个方法来将它所代表的状态与另一个状态进行比较。 这用于记忆，以确定是否已经看到状态。 每个状态还有一种方法来生成可从该状态直接到达的状态（即旋转块、放置块、移动块）。 求解器的工作方式是维护一个状态队列，从队列前面弹出一个状态，检查它是否是所需的状态（即谜题已解决）。 如果没有，则检查记忆（我们使用散列集）以查看该状态是否已经被看到。 如果不是，则生成从当前状态可达的状态并将其附加到队列的末尾。 空队列预示着一个无法解决的难题。
为 3D 概念化类似的东西会很困难，但这是计算机化解谜的基本方法。
In my latest CS class we made a generic puzzle solver that worked by having states represented as objects in C++. Each object had a method to compare the state it represented to another state. This was used for memoization, to determine if states had already been seen. Each state also had a method to generate states directly reachable from that state (i.e. rotating a block, placing a block, shifting a block). The solver worked by maintaining a queue of states, popping a state off the front of the queue, checking to see if it was the desired state (i.e. puzzle solved). If not, the memoization (we used a hashed set) was checked to see if the state had already been seen. If not, the states reachable from the current state were generated and appended to the rear of the queue. An empty queue signaled an unsolvable puzzle.
Conceptualizing something like that for 3D would be hard, but that is the basic approach to computerized puzzle solving.
看起来像是三维多联骨牌打包问题的一个更简单的子集。 关于该主题有各种学术论文。
Seems like an easier subset of a three-dimensional polyomino packing problem. There are various scholarly papers on that subject.
因为这或多或少是一个小问题，因为对于计算机来说，可能的组合数量很少，所以我会尝试一个简单的搜索算法。
我的意思是一个算法，它检查每个可能的配置并根据此配置的结果继续进行直到它最终形成最终配置，在您的情况下是立方体。
问题似乎是编写一个能够执行所有状态检查以及从一种状态到另一种状态的转换的程序。 因为你必须看看配置在物理上是否可行。
As it is a more or less small problem because for a computer there is a small number of combinations possible I would try a simple search algorithm.
I mean an algorithm that checks every possible configuration and goes on from the result of this configuration until it ends up in a end configuration, in your case the cube.
The problem seams to be writing a program that is able to do all the state checks and transformations from one state to another. Because you have to see if the configuration is physically possible.
如果您想要解决的难题是您链接的照片中的难题，那么只需在可能的解决方案树中搜索，直到找到底部的方法可能是可行的。
如果每个拼图块都是许多面附着的立方体，并且我要通过将每个拼图块放入一个更大的立方体中来解决拼图，每个边缘作为组合立方体 4 次，那么我将按如下方式进行。
声明每块的任意一个立方体作为其原点。 观察每个拼图块有 24 种可能的旋转，原点立方体朝上的每个可能的面有一个方向，乘以该位置绕垂直轴的 4 种可能的旋转。
如果给定的旋转，然后将原始立方体平移到该块的任何其他立方体，则尝试通过寻找产生相同最终块的可能方向来剔除搜索空间，从而产生与先前完全相同的占用体积考虑轮换，从未来的考虑中剔除该轮换。
从袋子里取出一块。 如果袋子里没有碎片，那么这就是一个解决方案。 循环遍历溶液体积的每个单元格，以及每个单元格的拉片的每次旋转。 如果该片段完全位于搜索量内，并且不与任何其他片段重叠，则递归到本段落。 否则，继续进行下一次旋转，或者如果没有更多的旋转，则继续到下一个单元格，或者如果没有更多的单元格，则返回而不返回解。
如果最后一段没有给出答案，那么这个谜题就无法解决。
If the puzzle you want to handle is that one in the photo you have linked, then it's probably feasible to just search through a tree of possible solutions until you find your way to the bottom.
If each puzzle piece is a number of cubes attached at their faces, and I am to solve the puzzle by fitting each piece into a larger cube, 4 times on each edge as the composing cubes, then I'd proceed as follows.
Declare an arbitrary cube of each piece as its origin. Observe that there are 24 possible rotations for each puzzle piece, one orientation for each possible face of the origin cube facing upwards, times 4 possible rotations about the vertical axis in that position.
Attempt to cull the search space by looking for possible orientations that produce the same final piece, if a given rotation, followed by a translation of the origin cube to any of the other cubes of the piece results in exactly the same occupied volume as a previously considered rotation, cull that rotation from future consideration.
Pull a piece out of the bag. If there are no pieces in the bag, then this is a solution. Loop through each cell of the solution volume, and each rotation of the pulled piece for each cell. If the piece is completely inside the search volume, and does not overlap with any other piece, recurse into this paragraph. Otherwise, proceed to the next rotation, or if there are no more rotations, proceed to the next cell, or if there are no more cells, return without a solution.
If the last paragraph returns without a solution, then the puzzle was unsolvable.