如何高效简单地解决5*5魔方

Question

如何高效简单地解决5*5魔方

5

有一个名为“快乐立方问题”的5*5魔方谜题，需要根据给定的图案组成一个立方体。 http://www.mathematische-basteleien.de/cube_its.htm#top 就像这样，有6个蓝色的图案： enter image description here

需要从这些图案中组合出一个立方体： enter image description here

这样还有3种解决方案。对于这种问题，我能想到的最简单的方法是基于递归的，对于每个立方体，我有6个位置，对于每个位置，我将尝试检查所有其他图案，并递归地解决相同的问题。就像找到每个立方体的所有排列，然后找到最佳匹配的一样。所以这是动态规划的方法。

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

我将每个图案或图表制成矩阵，然后将它们顺时针旋转90度4次和逆时针旋转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

仍然在努力整理逻辑。

- Marek

要么我的大脑完全短路了，要么这个例子根本不是一个解决方案。就我所看到的，4和5并不匹配。同样的情况也出现在4和6之间。 - user4668606

终于找到了解决方案。该解决方案通过让一些边缘突出立方体来实现。好的，祝你在实施中好运。 - user4668606

即使我们拒绝了这个解决方案，从编程的角度来解决问题的方法应该是什么？ - Marek

该死，又开始了，上述方法仅适用于4和5，而不是4和6。我完全不知道这些部分应该如何拼合在一起。 - user4668606

我很想看到这个问题的解决方案。虽然我完全不知道如何着手解决它。甚至不知道如何解决魔方本身。 - user4668606

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Niklas B. · Accepted Answer

我简直不敢相信，但实际上我在2009年写了一组脚本来强制执行这个确切问题的解决方案，对于简单的立方体情况。我将代码放在Github上：https://github.com/niklasb/3d-puzzle 不幸的是，文档是德语的，因为那是我团队唯一理解的语言，但源代码注释是英文的。特别是，请查看文件puzzle_lib.rb。

方法确实只是一个直接的回溯算法，我认为这是正确的方法。但我不能说它很容易，因为据我所记，三维方面有点棘手。我实现了一种优化：预先找到所有的对称性，并尝试每个块的唯一方向。这个想法是，块越“特征化”，放置块的选择就越少，因此我们可以早早地进行剪枝。在许多对称性的情况下，可能会有很多可能性，我们只想检查具有对称性的唯一性。

基本上，算法的工作方式如下：首先，为立方体的各个面分配一个固定顺序，例如编号为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个拼图，则更重要的是尽早修剪。