解决魔方的傻瓜立方体

Question

杜姆先生：您好，我很愚蠢，但我仍然想解决一个3x3x3的Rubik立方体。

斯玛特先生：好的，您很幸运。 这就是这样做的指导！

杜姆先生：不，因为我是杜姆，这对我不起作用。我只能遵循这样的算法。

pick up cube

look up a list of moves from some smart person

while(cube is not solved)
    perform the next move from list and turn
    the cube as instructed.  If there are no
    more turns in the list, I'll start from the
    beginning again.

hey look, it's solved!

斯玛特先生：好的，这是您的清单！

---

好的，什么样的列表可以解决这样的问题？我知道，魔方永远不能远离20点移动到解决，并且有一个魔方的43,252,003,274,489,856,000排列。因此，我认为该列表的长度可能为（20 * 43,252,003,274,489,856,000），但是

• 有谁知道目前已知的最短列表？
• 您将如何找到理论上最短的清单？

请注意，这纯粹是一个理论问题，我实际上并不希望对计算机进行编程来做到这一点。

Answer 1

通过立方体的所有排列获得这样的路径的一个想法是使用人类求解器使用的一些序列。Mr Smart 算法的主要结构如下所示：

function getMoves(callback):
    paritySwitchingSequences = getParitySwitchingSequences()
    cornerCycleSequences = getCornerCycleSequences()
    edgeCycleSequences = getEdgeCycleSequences()
    cornerRotationSequences = getCornerRotationSequences()
    edgeFlipSequences = getEdgeFlipSequences()
    foreach paritySeq in paritySwitchingSequences:
        if callback(paritySeq) return
        foreach cornerCycleSeq in cornerCycleSequences:
            if callback(cornerCycleSeq) return
            foreach edgeCycleSeq in edgeCycleSequences:
                if callback(edgeCycleSeq) return
                foreach cornerRotationSeq in cornerRotationSequences:
                    if callback(cornerRotationSeq) return
                    foreach edgeFLipSeq in edgeFlipSequences:
                        if callback(edgeFlipSeq) return

5 个get...函数都会返回一个序列数组，其中每个序列都是一个移动数组。回调系统将避免将所有移动保留在内存中，并且可以用更现代的生成器语法重写（如果目标语言可用）。

哑巴先生会有这样的代码：

function performMoves(sequence):
    foreach move in sequence:
        cube.do(move)
        if cube.isSolved() then return true
    return false

getMoves(performMoves)

Dumb 先生的代码将他的回调函数传递给 Smart 先生一次，然后 Smart 先生将继续回调该函数，直到返回 true。

Smart 先生的代码将遍历 5 个get函数中的每一个来检索他开始为调用者生成序列所需的基本序列。我将在下面描述这些函数，从最内层循环中使用结果的函数开始：

获取边缘翻转序列

想象一个立方体，所有部件都在其正确的插槽中并正确旋转，除了可以翻转的边缘，但仍然在正确的插槽中。如果将它们翻转，立方体就会被解决。由于有 12 条边，但同时只能翻转 2 条边，因此该立方体的边翻转（或不翻转）的方式为 2^11 = 2048。否则，12 条边中有 11 条可以具有任何翻转状态（翻转或未翻转）的边，而最后一个边则受其他 11 条翻转的约束。

该函数应返回同样多的序列，以便在应用其中一个序列后，会生成具有一组唯一的翻转边的立方体的下一个状态。

function getEdgeFlipSequences
    sequences = []
    for i = 1 to 2^11:
        for edge = 1 to 11:
           if i % (2^edge) != 0 then break
        sequence = getEdgePairFlipSequence(edge, 12)
        sequences.push(sequence) 
    return sequences

内部循环确保在外部循环的每次迭代中进行一次翻转，您就可以获得所有可能的翻转状态。

这就像以二进制表示形式列出所有数字，只需翻转一位即可得出下一个数字。以这种方式生成的数字输出不会按顺序排列，但您将获得全部数字。例如，对于 4 位（而不是 11 位），它会像这样：

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

该序列将确定哪条边与第 12 条边一起翻转。我现在不会定义getEdgePairFlipSequence函数。显然，存在翻转任何一对边的序列，并且在它们不公开的情况下，人们可以轻松地进行一些操作以使这两个边处于更好的位置，进行双重翻转并将这些边返回到原始状态通过以相反的顺序和相反的方向应用起始动作来再次定位。

获取角点旋转序列

这个想法与上面相同，但现在有旋转的角。不同的是，一个角可以有三种旋转状态。但与翻转边缘一样，如果您知道 7 个角的旋转（已经处于正确位置），则也可以确定第 8 个角的旋转。因此，立方体的角旋转有 3^7 种可能的方式。

将一个角与第 8 个角一起旋转并找到所有可能的角旋转的技巧在这里也适用。3 基数表示的模式如下（对于 3 个角）：

000
001
002
012
011
010
020
021
022
122
121
120
110
111
112
102
101
100
200
201
202
212
211
210
220
221
222

所以这个函数的代码如下所示：

function getCornerRotationSequences
    sequences = []
    for i = 1 to 3^7:
        for corner = 1 to 7:
           if i % (3^edge) != 0 break
        sequence = getCornerPairRotationSequence(corner, 8)
        sequences.push(sequence)
    return sequences

再次强调，我不会定义getCornerPairRotationSequence。与边缘类似的推理也适用。

获取边缘循环序列

当您想要移动边而不影响立方体的其余部分时，您需要循环至少 3 个边，因为不可能在不改变其他任何内容的情况下交换两条边。

例如，可以交换两条边和两个角。但这超出了该函数的范围。稍后在处理最后一个函数时我会再次讨论这一点。

该函数的目的是找到通过重复循环 3 个边可以到达的所有可能的立方体状态。有 12 条边，如果您知道其中 10 条边的位置，则可以确定其余 2 条边的位置（仍然假设角保持在其位置）。因此，在这些条件下，边有 12!/2 = 239 500 800 种可能的排列。

这可能在内存方面存在一些问题，因为要生成的序列数组将占用该数字的倍数（以字节为单位），因此我们可能正在讨论几千兆字节。但我假设有足够的内存：

function getEdgeCycleSequences
    sequences = []
    cycles = getCyclesReachingAllPermutations([1,2,3,4,5,6,7,8,9,10,11,12])
    foreach cycle in cycles:
        sequence = getEdgeTripletCycleSequence(cycle[0], cycle[1], cycle[3])
        sequences.push(sequence)
    return sequences

getCyclesAcheeringAllPermutations函数将返回一个三元组边的数组，这样，如果您按照三元组中列出的方式从左到右循环边，并对完整数组重复此操作，您将获得所有可能的边排列（不改变角的位置）。

我提出的这个问题的几个答案可用于实现getCyclesReachingAllPermutations。基于此答案的伪代码可能如下所示：

function getCyclesReachingAllPermutations(n):
    c = [0] * n
    b = [0, 1, ... n]
    triplets = []

    while (true):
        triplet = [0]
        for (parity = 0; parity < 2; parity++):
            for (k = 1; k <= c[k]; k++):
                c[k] = 0
                if (k == n - 1):
                    return triplets
            c[k] = c[k] + 1
            triplet.add( b[k] )
            for (j = 1, k--; j < k; j++, k--):
                swap(b, j, k)
        triplets.add(triplet)

类似地，对于其他主要函数，这里也依赖于函数getEdgeTripletCycleSequence，我不会对其进行扩展。有许多已知的序列可以循环三个边缘、多个位置，并且可以很容易地从它们导出其他序列。

获取角点循环序列

我将保持简短，因为它与边缘相同。如果边不移动，则角有 8!/2 种可能的排列。

function getCornerCycleSequences
    sequences = []
    cycles = getCyclesReachingAllPermutations([1,2,3,4,5,6,7,8])
    foreach cycle in cycles:
        sequence = getCornerTripletCycleSequence(cycle[0], cycle[1], cycle[3])
        sequences.push(sequence)
    return sequences

获取奇偶校验切换序列

需要这个额外的级别来处理立方体可以处于奇数或偶数位置的事实。当需要奇数次四分之一移动（那么半圈算作 2）来解出立方体时，这就很奇怪了。

我之前没有提到过，但是上面使用的所有序列都不应该改变立方体的奇偶校验。当我写到排列边缘时，角应该保持在原来的位置时，我确实隐含地提到了这一点。这确保了奇偶校验不会改变。另一方面，如果您要应用同时交换两个边缘和两个角的序列，则必须切换奇偶校验。

但由于上面的四个函数没有考虑到这一点，因此需要这个额外的层。

该功能非常简单：

function getParitySwitchingSequences
    return = [
        [L], [-L]
    ]

L是一个常数，表示立方体左面的四分之一移动，-L是相同的移动，但方向相反。它可以是任何面孔。

切换立方体奇偶校验的最简单方法就是：执行四分之一移动。

想法

这个解决方案当然不是最优的，但它是一个最终会遍历立方体所有状态的解决方案，尽管一路上会出现许多重复的状态。两次连续排列之间的移动次数少于 20 步即可实现这一点。移动次数将在 1（用于奇偶校验切换）和 18（用于翻转两个边缘）之间变化，允许 2 次额外移动以使边缘处于良好的相对位置，以及 2（用于在双翻转后将该边缘放回原位） 14移动，我认为这是最坏的情况。

一种快速优化是将奇偶校验循环作为内部循环，因为它只包含四分之一的移动，所以让该循环重复次数最多会更有效。

汉密尔顿图：最好的

已构建了一个图，其中每条边代表一次移动，其中节点代表所有唯一的立方体状态。它是循环的，这样从最后一个节点向前延伸的边将带您回到第一个节点。

因此，这应该允许您以尽可能多的移动次数遍历所有立方体状态。显然，不存在更好的解决方案。该图可以下载。