如何以高效简便的方式解决5*5立方体问题

Question

有5*5立方体拼图名为快乐立方体问题,对于给定的垫子,需要制作立方体. http://www.mathematische-basteleien.de/cube_its.htm#top

就像6个蓝色垫子一样 -

从以下垫子,需要派生一个立方体 -

这样它还有3个解决方案.就像第一只小熊一样

对于这样的问题,我能想象的最简单的方法是基于递归,对于每个立方体,我有6个位置,并且对于每个位置,我将尝试检查所有其他配合,哪个适合,我将再次递归地解决相同的问题.就像找到每个立方体的所有排列然后找到最适合的那样.所以动态编程方法.

但是我在递归中犯了很多错误,那么有什么更好的方法可以用来解决这个问题吗？

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

 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.

该方法确实只是一个简单的回溯算法，我认为这是可行的方法。但我真的不能说这很容易，据我记得 3D 方面有点具有挑战性。我实现了一项优化：预先找到所有对称性，并且只尝试一块的每个独特方向。这个想法是，碎片越有特色，放置碎片的选择就越少，所以我们可以尽早修剪。在许多对称性的情况下，可能有很多可能性，我们只想检查对称性唯一的可能性。

基本上，该算法的工作原理如下：首先，为立方体的边分配固定的顺序，例如，将它们编号为 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 个，尽早修剪就变得更加重要。