通过立方体的所有排列获得这样的路径的一个想法是使用人类求解器使用的一些序列。 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
The 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 条边一起翻转。我不会对此进行定义获取EdgePairFlipSequence现在运行。很明显,存在翻转任何一对边的序列,并且在它们不公开的情况下,人们可以轻松地进行一些操作以使这两个边处于更好的位置,进行双重翻转并将这些边返回到原始状态通过以相反的顺序和相反的方向应用起始动作来再次定位。
获取角点旋转序列
这个想法与上面相同,但现在有旋转的角。不同的是,一个角可以有三种旋转状态。但与翻转边缘一样,如果您知道 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
再说一遍,我不会定义获取角点对旋转序列。与边缘类似的推理也适用。
获取边缘循环序列
当您想要移动边而不影响立方体的其余部分时,您需要循环至少 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
The getCycles实现所有排列函数将返回一个三元组边的数组,这样,如果您按照三元组中列出的方式从左到右循环边,并对完整数组重复此操作,您将获得所有可能的边排列(不改变位置)角)。
几个答案这个问题 https://stackoverflow.com/questions/34829677/find-permutations-by-repeatedly-cycling-3-elements/34832886我问可以用来实现getCyclesReachingAllPermutations。伪代码基于这个答案 https://stackoverflow.com/questions/34829677/find-permutations-by-repeatedly-cycling-3-elements#answer-34832747可能看起来像这样:
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)
类似地,对于其他主要函数,这里也是对函数的依赖获取EdgeTripletCycleSequence,我就不展开展开了。有许多已知的序列可以循环三个边缘、多个位置,并且可以很容易地从它们导出其他序列。
获取角点循环序列
我将保持简短,因为它与边缘相同。如果边不移动,则角有 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是同样的动作,但方向相反。它可以是任何一张脸。
切换立方体奇偶校验的最简单方法就是:执行四分之一移动。
Thoughts
这个解决方案当然不是最佳的,但它是一个最终会遍历立方体所有状态的解决方案,尽管一路上会出现许多重复的状态。两次连续排列之间的移动次数少于 20 步即可实现这一点。移动次数将在 1(用于奇偶校验切换)和 18(用于翻转两个边缘)之间变化,允许 2 次额外移动以使边缘处于良好的相对位置,以及 2(用于在双翻转后将该边缘放回原位) 14移动,我认为这是最坏的情况。
一种快速优化是将奇偶校验循环作为内部循环,因为它只包含四分之一的移动,所以让该循环重复次数最多会更有效。
汉密尔顿图:最好的
图表已经构建完成 https://math.stackexchange.com/questions/184760/brute-force-method-of-solving-the-cube-how-many-moves-would-it-take#answer-184763其中每条边代表一次移动,节点代表all独特的立方体状态。它是循环的,这样从最后一个节点向前延伸的边将带您回到第一个节点。
因此,这应该允许您以尽可能多的移动次数遍历所有立方体状态。显然,不存在更好的解决方案。图表可以下载 http://bruce.cubing.net/index.html.