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!
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.
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
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 would have this code:
function performMoves(sequence):
foreach move in sequence:
cube.do(move)
if cube.isSolved() then return true
return false
getMoves(performMoves)
Mr Dumb's code passes his callback function once to Mr Smart, who will then keep calling back that function until it returns true.
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:
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.
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
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.
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.
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
Again, I will not define getCornerPairRotationSequence. A similar reasoning as for the edges applies.
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.
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
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).
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)
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.
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
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.
The function is quite simple:
function getParitySwitchingSequences
return = [
[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.
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.
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.