5

达姆先生:你好,我很笨,但我还是想解一个 3x3x3 魔方。

斯马特先生:嗯,你很幸运。 是这样做的指导!

达姆先生:不,这对我不起作用,因为我是达姆。我只能遵循这样的算法。

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) 长,但是

  • 有谁知道目前已知的最短的此类列表?
  • 您如何找到理论上最短的列表?

请注意,这纯粹是一个理论问题,我实际上并不想对计算机进行编程来执行此操作。

4

2 回答 2

4

通过立方体的所有排列获得这样一条路径的一个想法是使用人类求解器使用的一些序列。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函数中的每一个,以检索他开始为调用者生成序列所需的基本序列。我将在下面描述这些函数,从其结果用于最内层循环的函数开始:

getEdgeFlipSequences

想象一个立方体,它的所有部分都在其右侧插槽中并正确旋转,除了可以翻转的边缘,但仍在右侧插槽中。如果它们被翻转,立方体就会被解决。由于有 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函数。很明显,有用于翻转任何一对边缘的序列,并且在它们不公开的情况下,可以轻松地进行一些移动以使这两个边缘处于更好的位置,进行双重翻转并将这些边缘返回到它们的原始位置通过以相反的顺序和相反的方向应用开始移动来再次定位。

getCornerRotationSequences

这个想法和上面的一样,但是现在有旋转的角。不同的是,一个角可以有三种旋转状态。但是就像翻转的边缘一样,如果你知道 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。与边缘类似的推理也适用。

getEdgeCycleSequences

当您想在不影响立方体其余部分的情况下移动边时,您需要循环至少 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

getCyclesAchievingAllPermutations函数将返回一个由三元组边组成的数组,这样如果您按照三元组中列出的从左到右循环边,并对整个数组重复此操作,您将获得所有可能的边排列(不改变角的位置)。

我提出的这个问题的几个答案可用于实现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的依赖,我不会对其进行扩展。有许多已知的序列可以循环三个边缘,用于几个位置,并且可以很容易地从中推导出其他序列。

getCornerCycleSequences

我会保持简短,因为它与边缘相同。如果边不移动,则角有 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

getParitySwitchingSequences

需要这个额外的级别来处理立方体可以处于奇数或偶数位置的事实。当解立方体需要奇数个四分之一移动(半转算为 2)时,这很奇怪。

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

但是由于上面的四个函数没有考虑到这一点,所以需要这个额外的层。

该功能非常简单:

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

L是一个常数,表示立方体左面的四分之一移动,-L是相同的移动,但相反。它可能是任何一张脸。

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

想法

这个解决方案当然不是最优的,但它是一个最终会遍历立方体所有状态的解决方案,尽管在此过程中会出现许多重复的状态。它会在两个连续排列之间少于 20 次移动。移动的数量将在 1 - 用于奇偶切换 - 和 18 - 用于翻转两个边缘之间变化,允许 2 个额外的移动使边缘处于良好的相对位置,2 用于在两次翻转后将该边缘放回 14移动,我认为这是最坏的情况。

一种快速的优化是将奇偶校验循环作为内部循环,因为它仅包含四分之一移动,因此重复最多的移动会更有效。

汉密尔顿图:最好的

已经构建了一个图,其中每条边代表一个移动,并且节点代表所有唯一的立方体状态。它是循环的,因此从最后一个节点向前的边缘将您带回第一个节点。

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

于 2016-01-17T16:55:14.350 回答
3

您可以使用De Bruijn 序列来获得一个肯定会解决魔方的序列(因为它将包含大小为 20 的所有可能排列)。

来自维基(Python):

def de_bruijn(k, n):
    """
    De Bruijn sequence for alphabet k
    and subsequences of length n.
    """
    try:
        # let's see if k can be cast to an integer;
        # if so, make our alphabet a list
        _ = int(k)
        alphabet = list(map(str, range(k)))

    except (ValueError, TypeError):
        alphabet = k
        k = len(k)

    a = [0] * k * n
    sequence = []

    def db(t, p):
        if t > n:
            if n % p == 0:
                sequence.extend(a[1:p + 1])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return "".join(alphabet[i] for i in sequence)

你可以像这样使用它:

print(de_bruijn(x, 20))

其中 20 是您的序列的大小,而 x 是一个列表/字符串,其中包含立方体的每个可能的转弯(想不出更好的词)。

于 2016-01-07T13:45:32.773 回答