解决魔方的傻瓜立方体 [英] Solving Rubik's Cubes for Dummies
问题描述
先生。杜姆：您好，我很愚蠢，但我仍然想解决3x3x3魔方的问题。
Mr. Dum: Hello, I'm very stupid but I still want to solve a 3x3x3 Rubik's cube.
先生。聪明：嗯，你很幸运。 此处是这样做的指导！
Mr. Smart: Well, you're in luck. Here is guidance to do just that!
先生。杜姆：不，这对我不起作用，因为我是杜姆。我只能遵循这样的算法。
Mr. Dum: No that won't work for me because I'm Dum. I'm only capable of following an algorithm like this.
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!
先生。聪明：啊，没问题，这是您的列表！
Mr. Smart: Ah, no problem here's your list!
好的，那么什么样的列表可以解决这样的问题？我知道魔方永远不会远离20个要解决的动作，并且有43,252,003,274,489,856,000个Rubik's Cube的排列。因此，我认为该列表的长度可能为（20 * 43,252,003,274,489,856,000），但是
Ok, so what sort of list would work for a problem like this? I know that 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. Therefore, I think that this list could be (20 * 43,252,003,274,489,856,000) long, but
- 有人知道当前已知的最短列表吗？
- 您如何找到理论上最短的列表？
请注意，这纯粹是一个理论问题而且我实际上并不想对计算机进行编程来做到这一点。
Note that this is purely a theoretical problem and I don't actually want to program a computer to do this.
推荐答案
在所有排列中获得这样一条路径的想法多维数据集的用途是使用人类求解器使用的一些序列。 Smart先生的算法的主要结构如下：
An idea to get such a path through all permutations of the Cube would be to use some of the sequences that human solvers use. The main structure of the algorithm for Mr Smart would look like this:
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 ... 函数将全部返回序列数组，其中每个序列都是一个动作数组。回调系统将避免将所有移动都保留在内存中，并且可以使用更现代的生成器语法重写（如果目标语言可用）。
The 5 get... functions would all return an array of sequences, where each sequence is an array of moves. A callback system will avoid the need for keeping all moves in memory, and could be rewritten in the more modern generator syntax if available in the target language.
Mr Dumb会拥有这段代码：
Mr Dumb would have this code:
function performMoves(sequence):
foreach move in sequence:
cube.do(move)
if cube.isSolved() then return true
return false
getMoves(performMoves)
Dumb先生的代码将其回调函数一次传递给Smart先生，Smart先生随后将继续回调该函数，直到其返回true。
Mr Dumb's code passes his callback function once to Mr Smart, who will then keep calling back that function until it returns true.
Smart先生的代码将通过5个 get 函数中的每一个，以检索他开始向调用者生成序列所需的基本序列。我将在下面描述这些函数，从在最里面的循环中使用其结果的函数开始：
Mr Smart's code will go through each of the 5 get functions to retrieve the basic sequences he needs to start producing sequences to the caller. I will describe those functions below, starting with the one whose result is used in the innermost loop:
想象一个立方体，它的所有块都在其右槽中并向右旋转，除了可以翻转的边，但仍在右槽中。如果将它们翻转，则将解决多维数据集。由于有12条边，但是只能同时用2条边翻转，因此此多维数据集可以翻转（或不翻转）其边的方式的数量为2 ^ 11 =2048。否则，则有12条中的11条边缘可以具有任意翻转状态（翻转或不翻转），而最后一个则受其他11个翻转的约束。
Imagine a cube that has all pieces in their right slots and rightly rotated, except for the edges which could be flipped, but still in right slot. If they would be flipped, the cube would be solved. As there are 12 edges, but edges can only be flipped with 2 at the same time, the number of ways this cube could have its edges flipped (or not) is 2^11 = 2048. Otherwise put, there are 11 of the 12 edges that can have any flip status (flipped or not), while the last one is bound by the flips of the other 11.
此函数应返回尽可能多的序列，这样，在应用了这些序列中的一个之后，就产生了具有唯一一组翻转边的立方体的下一个状态。
This function should return just as many sequences, such that after applying one of those sequences the next state of the cube is produced that has a unique set of edges flipped.
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
内部循环可确保在外部循环的每次迭代中进行一次翻转，即可获得所有可能的翻转状态。
The inner loop makes sure that with one flip in each iteration of the outer loop you get exactly all possible flip states.
就像以二进制表示形式列出所有数字一样，只需翻转一位就可以得出下一个数字。以这种方式产生时，数字的输出将不按顺序排列，但是您将得到全部。例如，对于4位（而不是11位），它将是这样的：
It is like listing all numbers in binary representation by just flipping one bit to arrive at the next number. The numbers' output will not be in order when produced that way, but you will get them all. For example, for 4 bits (instead of 11), it would go like this:
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
序列将确定与第12条边一起翻转的边。我现在不再去定义 getEdgePairFlipSequence 函数。显然，存在翻转任意一对边缘的序列，并且在不公开的情况下，可以轻松地进行一些移动以使这两个边缘处于更好的位置，进行两次翻转并将这些边缘返回到原始位置。
The sequence will determine which edge to flip together with the 12th edge. I will not go into defining that getEdgePairFlipSequence function now. It is evident that there are sequences for flipping any pair of edges, and where they are not publicly available, one can easily make a few moves to bring those two edges in a better position, do the double flip and return those edges to their original position again by applying the starting moves in reversed order and in opposite direction.
与上述相同，但现在具有转角。区别在于，一个角可以具有三个旋转状态。但是，就像翻转边缘一样，如果您知道7个角的旋转（已经在其正确的位置），那么也会确定第8个角的旋转。因此，有3 ^ 7种可能的方式可以旋转多维数据集的角。
The idea is the same as above, but now with rotated corners. The difference is that a corner can have three rotation states. But like with the flipped edges, if you know the rotations of 7 corners (already in their right position), the rotation of the 8th corner is determined as well. So there are 3^7 possible ways a cube can have its corners rotated.
将角与第8个角一起旋转的技巧，从而找到所有可能的角旋转在这里也可以。 3基数表示中的模式如下（对于3个角）：
The trick to rotate a corner together with the 8th corner, and so find all possible corner rotations also works here. The pattern in the 3-base number representation would be like this (for 3 corners):
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
因此该函数的代码如下所示：
So the code for this function would look like this:
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个，因为不可能在不更改任何其他内容的情况下交换两个边。
When you want to move edges around without affecting the rest of the cube, you need to cycle at least 3 of them, as it is not possible to swap two edges without altering anything else.
例如，有可能交换两个边缘和两个角。但这将超出此功能的范围。
For instance, it is possible to swap two edges and two corners. But that would be out of the scope of this function. I will come back to this later when dealing with the last function.
该函数的目的是查找可以通过重复循环3个边来获得的所有可能的立方体状态。有12条边线，如果您知道其中10条边线的位置，则确定剩余2条边线的位置（仍然假设边角保持在其位置）。因此，在这些条件下，边的排列可能有12！/ 2 = 239 500 800个。
This function aims to find all possible cube states that can be arrived at by repeatedly cycling 3 edges. There are 12 edges, and if you know the position of 10 of them, the positions of the 2 remaining ones are determined (still assuming corners remain at their position). So there are 12!/2 = 239 500 800 possible permutations of edges in these conditions.
这可能在内存方面有点问题，因为要生成的序列数组将占据该数字的倍数（以字节为单位），所以我们可以谈论一个几千兆字节。但我会假设有足够的内存用于此操作：
This may be a bit of problem memory-wise, as the array of sequences to produce will occupy a multiple of that number in bytes, so we could be talking about a few gigabytes. But I will assume there is enough memory for this:
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 函数将返回边缘的三元组数组，这样，如果您将边缘按三元组中的顺序从左向右循环，然后对整个数组重复此过程，您将获得边缘的所有可能排列（而不更改角的位置）。
The getCyclesAchievingAllPermutations function would return an array of triplets of edges, such that if you would cycle the edges from left to right as listed in a triplet, and repeat this for the complete array, you would get to all possible permutations of edges (without altering the position of corners).
我提出的问题可以用来实现 getCyclesReachingAllPermutations 。基于此答案的伪代码看起来像
Several answers for this question I asked can be used to implement getCyclesReachingAllPermutations. The pseudo code based on this answer could look like this:
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 的依赖，在此不再赘述。有许多已知的序列可以在多个位置循环三个边缘，并且可以很容易地从中得出其他边缘。
Similarly for the other main functions, also here is a dependency on a function getEdgeTripletCycleSequence, which I will not expand on. There are many known sequences to cycle three edges, for several positions, and others can be easily derived from them.
我会尽量简短，因为这与边缘相同。如果边缘不移动，则角有8！/ 2个可能的排列。
I will keep this short, as it is the same thing as for edges. There are 8!/2 possible permutations for corners if edges don't move.
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）来解决该多维数据集时，这很奇怪。
getParitySwitchingSequences
This extra level is needed to deal with the fact that a cube can be in an odd or even position. It is odd when an odd number of quarter-moves (a half turn counts as 2 then) is needed to solve the cube.
我之前没有提到，但是以上所有使用的序列均不应更改多维数据集的奇偶校验。当我写到置换边缘时，拐角应保持在原始位置，因此我确实隐式地提到了它。这确保了奇偶校验不变。另一方面，如果您要应用同时交换两个边和两个角的序列，则势必会切换奇偶校验。
I did not mention it before, but all the above used sequences should not change the parity of the cube. I did refer to it implicitly when I wrote that when permuting edges, corners should stay in their original position. This ensures that the parity does not change. If on the other hand you would apply a sequence that swaps two edges and two corners at the same time, you are bound to toggle the parity.
但是由于那不是考虑到上面的四个功能，需要额外的一层。
But since that was not accounted for with the four functions above, this extra layer is needed.
该功能非常简单：
function getParitySwitchingSequences
return = [
[L], [-L]
]
L 是一个常数，表示立方体左表面的四分之一移动，而 -L 是同样的举动，但倒退了。
L is a constant that represents the quarter move of the left face of the cube, and -L is the same move, but reversed. It could have been any face.
切换多维数据集奇偶校验的最简单方法是：执行四分之一移。
The simplest way to toggle the parity of a cube is just that: perform a quarter move.
此解决方案当然不是最佳解决方案，但它最终会遍历多维数据集的所有状态，尽管存在很多问题重复出现的状态。并且它将在两个连续置换之间进行少于20步的移动。移动的数量将在1（对于奇偶切换）和18（对于翻转两个边缘）之间变化，允许进行2次额外的移动以使边缘处于良好的相对位置，而在进行两次翻转之后，将边缘重新放回2则14动作，我认为这是最坏的情况。
This solution is certainly not the optimal one, but it is a solution that will eventually go through all states of the cube, albeit with many duplicate statuses appearing along the way. And it will do so with less than 20 moves between two consecutive permutations. The number of moves will vary between 1 -- for parity toggle -- and 18 -- for flipping two edges allowing for 2 extra moves to bring an edge in a good relative position and 2 for putting that edge back after the double flip with 14 moves, which I think is the worst case.
一种快速的优化方法是将奇偶校验循环作为内部循环，因为它只包含四分之一步，所以重复一次最多会更有效。
One quick optimisation would be to put the parity loop as the inner loop, as it only consists of one quarter move it is more efficient to have that one repeated the most.
已构建了一个图形，其中每个边缘代表一个动作，其中节点表示所有唯一的多维数据集状态。这是循环的，因此从最后一个节点开始的边沿将您带回到第一个节点。
A graph has been constructed where each edge represents one move, and where the nodes represent all unique cube states. It is cyclic, such that the edge forward from the last node, brings you back to the first node.
因此，这应允许您使用as来遍历所有多维数据集状态许多动作。显然，没有更好的解决方案。可以下载图 。
So this should allow you to go through all cube states with as many moves. Clearly a better solution cannot exist. The graph can be downloaded.
这篇关于解决魔方的傻瓜立方体的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
