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

Question

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

它就像，给了 6 个蓝色垫子-

从下面的mats中，需要推导出一个Cube——

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

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

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

我用提供的每个垫子或图表制作了矩阵，然后我将它们顺时针旋转 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。

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

基本上，该算法的工作原理如下:首先，为立方体的边分配一个固定的顺序，例如，让我们将它们编号为 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

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

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