为傻瓜解魔方
Solving Rubik's Cubes for Dummies
先生Dum：你好，我很笨，但我还是想解一个3x3x3的魔方
先生斯玛特：嗯，你很幸运。 Here 就是这样做的指南！
先生Dum：不，这对我不起作用，因为我是 Dum。我只能遵循这样的算法。
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!
先生斯玛特：啊，没问题，这是你的清单！
好的，什么样的列表可以解决这样的问题？我知道the Rubik's cube can never be farther away from 20 moves to solved, and that there are 43,252,003,274,489,856,000 permutations of a Rubik's Cube。因此，我认为这个列表可能有 (20 * 43,252,003,274,489,856,000) 长，但是
- 有谁知道目前已知的最短的此类列表？
- 你如何找到理论上最短的列表？
请注意，这纯粹是一个理论问题，我实际上并不想编写计算机程序来执行此操作。
您可以使用 De Bruijn sequence 得到一个序列，该序列将 肯定 解决魔方（因为它将包含大小为 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 是 list/string 包含立方体的所有可能 turn（想不出更好的词）。
通过立方体的所有排列获得这样一条路径的一个想法是使用人类求解器使用的一些序列。 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... 函数都是 return 一个序列数组，其中每个序列都是一个移动数组。回调系统将避免将所有移动保存在内存中的需要，并且如果在目标语言中可用，可以用更现代的生成器语法重写。
阿呆先生会有这样的代码：
function performMoves(sequence):
foreach move in sequence:
cube.do(move)
if cube.isSolved() then return true
return false
getMoves(performMoves)
Dumb 先生的代码将他的回调函数传递给 Smart 先生一次，后者将继续回调该函数，直到它 return 为真。
Smart 先生的代码将遍历 5 个 get 函数中的每一个，以检索他开始为调用者生成序列所需的基本序列。我将在下面描述这些函数，从结果在最内层循环中使用的函数开始：
getEdgeFlipSequences
想象一个立方体，它的所有部分都在正确的插槽中并且正确旋转，但可以翻转的边缘除外，但仍在正确的插槽中。如果将它们翻转，则立方体将被解决。由于有 12 条边，但只能同时翻转 2 条边，因此该立方体翻转（或不翻转）边的方式数为 2^11 = 2048。否则，12 条中有 11 条可以具有任何翻转状态（翻转或不翻转）的边缘，而最后一个边缘受其他 11 个翻转的约束。
此函数应 return 尽可能多的序列，以便在应用其中一个序列后，生成立方体的下一个状态，该状态具有一组独特的边翻转。
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 函数。很明显，存在用于翻转任何一对边的序列，并且在它们不公开的地方，可以轻松地进行一些移动以使这两条边处于更好的位置，进行两次翻转和 return 那些通过以相反的顺序和相反的方向应用起始移动，再次将边移动到它们的原始位置。
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 种可能的边排列。
这可能有点问题 memory-wise，因为要生成的序列数组将占用该数字的字节数的倍数，因此我们可能会讨论几千兆字节。但我假设有足够的内存：
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 函数将 return 边的三元组数组，这样，如果您按照三元组中列出的方式从左到右循环边，并且对整个数组重复此操作，您将得到所有可能的边排列（不改变角的位置）。
I asked can be used to implement getCyclesReachingAllPermutations. The pseudo code based on 的几个答案可能如下所示：
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)
同样适用于 t其他主要函数，这里也依赖一个函数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
需要这个额外的关卡来处理立方体可能处于奇数或偶数位置的事实。解魔方需要奇数quarter-moves（转半圈算2）才算奇数。
我之前没有提到，但是上面所有使用的序列应该不会改变立方体的奇偶性。当我写到当排列边时，角应该保持在原来的位置时，我确实隐含地提到了它。这确保了奇偶校验不会改变。另一方面，如果您要应用同时交换两条边和两个角的序列，则您必须切换奇偶校验。
但是由于上面的四个函数没有考虑到这一点，所以需要这个额外的层。
功能很简单：
function getParitySwitchingSequences
return = [
[L], [-L]
]
L是代表立方体左面四分之一移动的常量，-L是相同的移动，但逆转了。它可能是任何面孔。
切换立方体奇偶性的最简单方法就是：执行四分之一移动。
想法
这个解决方案当然不是最佳解决方案，但它是一个最终将遍历立方体所有状态的解决方案，尽管在此过程中会出现许多重复状态。并且它会在两个连续排列之间进行不到 20 次移动。移动次数将在 1（用于奇偶切换）和 18（用于翻转两条边，允许 2 次额外移动以使边处于良好的相对位置）和 2 次（用于在两次翻转后将边放回 14）之间变化移动，我认为这是最坏的情况。
一种快速优化方法是将奇偶校验循环作为内循环，因为它只包含四分之一的移动，所以重复次数最多的循环会更有效。
汉密尔顿图：最佳
A graph has been constructed 其中每条边代表一次移动，节点代表 所有 独特的立方体状态。它是循环的，因此从最后一个节点向前的边缘将您带回到第一个节点。
所以这应该允许您通过尽可能多的移动来遍历所有立方体状态。显然不存在更好的解决方案。图 can be downloaded.
先生Dum：你好，我很笨，但我还是想解一个3x3x3的魔方
先生斯玛特：嗯，你很幸运。 Here 就是这样做的指南！
先生Dum：不，这对我不起作用，因为我是 Dum。我只能遵循这样的算法。
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!
先生斯玛特：啊，没问题，这是你的清单！
好的，什么样的列表可以解决这样的问题？我知道the Rubik's cube can never be farther away from 20 moves to solved, and that there are 43,252,003,274,489,856,000 permutations of a Rubik's Cube。因此，我认为这个列表可能有 (20 * 43,252,003,274,489,856,000) 长，但是
- 有谁知道目前已知的最短的此类列表？
- 你如何找到理论上最短的列表？
请注意，这纯粹是一个理论问题，我实际上并不想编写计算机程序来执行此操作。
您可以使用 De Bruijn sequence 得到一个序列，该序列将 肯定 解决魔方（因为它将包含大小为 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 是 list/string 包含立方体的所有可能 turn（想不出更好的词）。
通过立方体的所有排列获得这样一条路径的一个想法是使用人类求解器使用的一些序列。 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... 函数都是 return 一个序列数组，其中每个序列都是一个移动数组。回调系统将避免将所有移动保存在内存中的需要，并且如果在目标语言中可用，可以用更现代的生成器语法重写。
阿呆先生会有这样的代码：
function performMoves(sequence):
foreach move in sequence:
cube.do(move)
if cube.isSolved() then return true
return false
getMoves(performMoves)
Dumb 先生的代码将他的回调函数传递给 Smart 先生一次，后者将继续回调该函数，直到它 return 为真。
Smart 先生的代码将遍历 5 个 get 函数中的每一个，以检索他开始为调用者生成序列所需的基本序列。我将在下面描述这些函数，从结果在最内层循环中使用的函数开始：
getEdgeFlipSequences
想象一个立方体，它的所有部分都在正确的插槽中并且正确旋转，但可以翻转的边缘除外，但仍在正确的插槽中。如果将它们翻转，则立方体将被解决。由于有 12 条边，但只能同时翻转 2 条边，因此该立方体翻转（或不翻转）边的方式数为 2^11 = 2048。否则，12 条中有 11 条可以具有任何翻转状态（翻转或不翻转）的边缘，而最后一个边缘受其他 11 个翻转的约束。
此函数应 return 尽可能多的序列，以便在应用其中一个序列后，生成立方体的下一个状态，该状态具有一组独特的边翻转。
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 函数。很明显，存在用于翻转任何一对边的序列，并且在它们不公开的地方，可以轻松地进行一些移动以使这两条边处于更好的位置，进行两次翻转和 return 那些通过以相反的顺序和相反的方向应用起始移动，再次将边移动到它们的原始位置。
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 种可能的边排列。
这可能有点问题 memory-wise，因为要生成的序列数组将占用该数字的字节数的倍数，因此我们可能会讨论几千兆字节。但我假设有足够的内存：
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 函数将 return 边的三元组数组，这样，如果您按照三元组中列出的方式从左到右循环边，并且对整个数组重复此操作，您将得到所有可能的边排列（不改变角的位置）。
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)
同样适用于 t其他主要函数，这里也依赖一个函数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
需要这个额外的关卡来处理立方体可能处于奇数或偶数位置的事实。解魔方需要奇数quarter-moves（转半圈算2）才算奇数。
我之前没有提到，但是上面所有使用的序列应该不会改变立方体的奇偶性。当我写到当排列边时，角应该保持在原来的位置时，我确实隐含地提到了它。这确保了奇偶校验不会改变。另一方面，如果您要应用同时交换两条边和两个角的序列，则您必须切换奇偶校验。
但是由于上面的四个函数没有考虑到这一点，所以需要这个额外的层。
功能很简单：
function getParitySwitchingSequences
return = [
[L], [-L]
]
L是代表立方体左面四分之一移动的常量，-L是相同的移动，但逆转了。它可能是任何面孔。
切换立方体奇偶性的最简单方法就是：执行四分之一移动。
想法
这个解决方案当然不是最佳解决方案，但它是一个最终将遍历立方体所有状态的解决方案，尽管在此过程中会出现许多重复状态。并且它会在两个连续排列之间进行不到 20 次移动。移动次数将在 1（用于奇偶切换）和 18（用于翻转两条边，允许 2 次额外移动以使边处于良好的相对位置）和 2 次（用于在两次翻转后将边放回 14）之间变化移动，我认为这是最坏的情况。
一种快速优化方法是将奇偶校验循环作为内循环，因为它只包含四分之一的移动，所以重复次数最多的循环会更有效。
汉密尔顿图：最佳
A graph has been constructed 其中每条边代表一次移动，节点代表 所有 独特的立方体状态。它是循环的，因此从最后一个节点向前的边缘将您带回到第一个节点。
所以这应该允许您通过尽可能多的移动来遍历所有立方体状态。显然不存在更好的解决方案。图 can be downloaded.