如何以高效简单的方式解决 5 * 5 立方体

Question

有一个名为 Happy cube Problem 的 5*5 立方体拼图，其中对于给定的垫子，需要制作一个立方体。 http://www.mathematische-basteleien.de/cube_its.htm#top

好像送了6张蓝垫-

从以下垫子中，需要导出一个立方体 -

这样它还有3个解决方案。所以像第一个幼崽

对于这样的问题，我能想到的最简单的方法是基于递归，对于每个立方体，我有 6 个位置，对于每个位置，我将尝试检查所有其他伙伴，哪个适合，我将再次递归地解决相同。就像找到每个立方体的所有排列，然后找到适合 best.So 动态规划方法的排列。

但是我在递归中犯了很多错误，所以有没有更好的简单方法可以用来解决这个问题？

我用提供的每个垫子或图表制作了矩阵，然后我将它们顺时针旋转 4 次和逆时针旋转 90 度。我翻转数组并做了同样的事情，现在对于上面的每次迭代，我将不得不为其他立方体重复该步骤，所以再次递归。

 0 0 1 0 1
 1 1 1 1 1
 0 1 1 1 0
 1 1 1 1 1
 0 1 0 1 1
-------------
 0 1 0 1 0
 1 1 1 1 0
 0 1 1 1 1
 1 1 1 1 0
 1 1 0 1 1
-------------
 1 1 0 1 1
 0 1 1 1 1
 1 1 1 1 0
 0 1 1 1 1
 0 1 0 1 0
-------------
 1 0 1 0 0
 1 1 1 1 1
 0 1 1 1 0
 1 1 1 1 1
 1 1 0 1 0
-------------

1st - block is the Diagram
2nd - rotate clock wise
3rd - rotate anti clockwise
4th - flip

仍在努力理清逻辑。

Answer 1

我不敢相信，但实际上我早在 2009 年就针对简单的立方体案例编写了一组脚本来暴力解决这个确切问题。我只是把代码放在 Github: https://github.com/niklasb/3d-puzzle

不幸的是，文档是德语的，因为这是我的团队唯一能理解的语言，但源代码注释是英语的。特别是，查看文件 puzzle_lib.rb.

该方法确实只是一种简单的回溯算法，我认为这是可行的方法。我真的不能说它 easy 不过，据我所知，3-d 方面有点挑战性。我实施了一个优化：事先找到所有对称性，只尝试一块的每个独特方向。这个想法是，碎片越特征，放置碎片的选项就越少，所以我们可以早点修剪。在许多对称性的情况下，可能有很多可能性，我们只想检查对称性唯一的那些。

基本上算法的工作原理如下：首先，为立方体的边指定一个固定顺序，例如让我们将它们编号为 0 到 5。然后执行如下算法：

def check_slots():
    for each edge e:
        if slot adjacent to e are filled:
            if the 1-0 patterns of the piece edges (excluding the corners)
                   have XOR != 0:
                return false
            if the corners are not "consistent":
                return false
    return true

def backtrack(slot_idx, pieces_left):
    if slot_idx == 6:
        # finished, we found a solution, output it or whatever
        return
    for each piece in pieces_left:
        for each orientation o of piece:
            fill slot slot_idx with piece in orientation o
            if check_slots():
                backtrack(slot_idx + 1, pieces_left \ {piece})
            empty slot slot_idx

拐角的一致性有点棘手：要么拐角必须恰好由相邻的棋子之一填充，要么必须可以从尚未填充的插槽访问，即不被已分配的棋子切断。

当然你可以忽略掉部分或全部的一致性检查，只检查最后，因为只有8^6 * 6！整体可能的配置。如果你有超过 6 个，那么尽早修剪就变得更加重要。

如何以高效简单的方式解决 5 * 5 立方体

How to solve 5 * 5 Cube in efficient easy way

algorithm

recursion

dynamic-programming