想要获取魔方所有排列的路径,一个想法是使用一些人类解决者使用的序列。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...函数都将返回一个序列数组,其中每个序列是移动的数组。通过回调系统可以避免需要在内存中保留所有移动,并且如果目标语言支持更现代的生成器语法,则可以重写该系统。
对于Mr Dumb,会使用以下代码:
function performMoves(sequence):
foreach move in sequence:
cube.do(move)
if cube.isSolved() then return true
return false
getMoves(performMoves)
Mr. Dumb的代码将他的回调函数交给了Mr. Smart,然后Mr. Smart会一直调用该函数,直到它返回true。
Mr. Smart的代码将依次遍历5个get函数,以获取开始生成序列并向调用方返回所需的基本序列。我将在下面描述这些函数,从其结果在最内层循环中使用的功能开始:
getEdgeFlipSequences
想象一个魔方,所有块都放在正确的位置和正确的旋转角度,除了可能被翻转但仍放在正确位置的边块。如果它们被翻转了,魔方就会被还原成已解决状态。由于有12条边,但只能同时翻转其中两条,因此这个魔方边块可能的翻转方式(或不翻转方式)的数量为2^11 = 2048。换句话说,有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
< p > 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的函数,我不会展开讲解。有许多已知的序列可以循环三条边,在几个位置上,其他序列可以从它们中轻易得到。
获取角落循环序列
这里我就简单介绍了,因为和边缘循环序列是一样的。如果边缘不动,角落的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
这一层额外处理魔方可能处于奇数或偶数位置的情况。如果解决魔方需要奇数个1/4转(半个转动算2个),则魔方处于奇数位置。
我之前没有提到过,但是以上所有使用的序列都不应该改变魔方的奇偶性。我在推置棱块时隐含地提到了这一点。这可以确保奇偶性不变。另一方面,如果你应用了同时交换两个棱块和两个角块的序列,那么就会切换奇偶性。
由于以上四个函数没有考虑这点,所以需要这个额外的层。
这个函数相当简单:
function getParitySwitchingSequences
return = [
[L], [-L]
]
L是一个常数,代表魔方的左面进行一格转动,-L则是相同的移动,但是反向的。它也可以是任何一个面。
切换魔方的奇偶性最简单的方法就是:进行一个四分之一格的转动。
思考
这种解决方法肯定不是最优的,但它是一种会穿过魔方所有状态的解决办法,尽管在此过程中会出现许多重复的状态。而且它将在两个连续的排列之间以不到20步的方式完成。移动的次数将在1(用于切换奇偶性)到18(用于翻转两个边,允许额外的两个移动将边放置在良好的相对位置,并用14个步骤进行双重翻转后将该边放回其原位),我认为这是最坏的情况。
一个快速的优化方法是将奇偶循环作为内部循环,因为它只包含一个四分之一的移动,所以最好多次重复该移动。
哈密顿图:最佳
构建了一个图,其中每条边代表一次移动,而节点表示 所有 独特的魔方状态。它是循环的,因此从最后一个节点向前走的边将您带回第一个节点。
因此,这应该允许您通过尽可能少的步数遍历所有魔方状态。显然,没有更好的解决方案。可以下载该图。