Minimal Move Set for the Rubik’s Cube
When solving the Rubik’s Cube, we normally allow any rotation of any face on the cube, resulting in 18 distinct rotations. In this post, we seek to find out how many distinct rotations are required to solve any scramble of a 3x3x3 Rubik’s Cube.
Notation
We use standard notation to denote moves. A clockwise rotation of a face is marked with a letter:
- F: Front
- D: Down
- U: Up
- R: Right
- L: Left
- B: Back
This means that with the move set {F, D, U, R, L, B} we can denote a clockwise rotation of each face of the Rubik’s Cube. Often, in algorithms we also see moves such as F’ meaning a anticlockwise rotation of F, or F2 meaning a 180 degree (double rotation) of F.
Full move set
The full move set including clockwise, anticlockwise, and double rotations is show below:
{
F, F’, F2,
D, D’, D2,
U, U’, U2,
R, R’, R2,
L, L’, L2,
B, B’, B2
}With this move set, it is possible to solve any scramble of a Rubik’s Cube. In fact, it has been shown that Gods Number is 20, meaning that any scrambled Rubik’s Cube can be solved in 20 moves or less, using this move set.
6 Moves
The first reduction to the move set we will perform, is to remove anticlockwise and double rotations from the move set, meaning the move set will shrink to a third of the former size, going from 18 moves to 6.
So how do we show that we can still solve every Rubik’s Cube scramble? We show that every move that we have removed from the move set, can be emulated using only the remaining moves. In this first reduction, this is relatively straightforward, as a double rotation can be achieved by two consecutive clockwise rotations, and an anticlockwise rotation can be achieved by three consecutive clockwise rotations.
{
F, D, U,
R, L, B
}So with this restricted move set we can replicate the behaviour of the original large move set by an encoding of anticlockwise and double rotations as:
F2 = F F and F’ = F F F
Since we have shown that the original larger move set can be replicated, we can conclude that the 6 moves is enough to solve any Rubik’s Cube scramble.
5 Moves
We will now expand on the intuition of the first reduction, to reduce our move set even further.
Without loss of generality, let’s assume that we remove the move D from our move set. The specific face does not matter since we could adapt the following procedure to each face. We must now show that it is possible to replicate a D move without actually turning the D face.
Without further ado, here is an algorithm that uses the remaining 5 face to perform a D move.
F2 U’ R2 U’ B2 U’ L2 U’ F2 // CrossU’ R U2 R’ U’ R U R’ // Corner 1
U L’ U’ L // Corner 2
B’ U2 B // Corner 3
U R’ U2 R // Corner 4U’ B’ U B U L U’ L’ // Edge 1 + 2
U B U’ B’ U’ R’ U R // Edge 3
U F’ U F U R U’ R’ // Edge 4U R U2 R2 F R F’ U2 R’ F R F’ // OLL
U2 R2 F R U R U’ R’ F’ R U2 R’ U2 R U2 // PLL
In the algorithm I have used double and anticlockwise rotations for simplicity, even though strictly speaking they are not in our move set. However, as we have already seen how they can be achieved using the regular clockwise rotations, it does not change the result.
The algorithm is not optimized for the shortest amount of moves, but uses the simple beginner method to first create the (rotated) cross at the bottom, adding the corner pieces, placing the edges in the middle layer, then performs two algorithms to orient and eventually solve the final layer. You can do the algorithm one line at a time, and see the effect on your Rubik’s Cube.
The effect on the solved Rubik’s Cube, is that the bottom face has been turned once, hence we have replicated the D move which, as we have seen, can be repeated to obtain D2 and D’, hence we again have our entire move set.
An attempt at 4 moves
Sadly, this is where the reductions come to an end. There is no way to solve every Rubik’s Cube with a move set of only 4 moves. We illustrate this with a case analysis of the locked faces i.e. the face we have removed from the move set.
The first case we will explore is if the two locked faces shares an edge. Without loss of generality we assume that the locked faces are green and red.
Keep white on top, and red at the front, and perform the moves to ‘scramble’ the Rubik’s Cube.
F U LWe must now attempt to solve this scramble without the F and L moves.
We have 4 remaining moves, {D, U, R, B} , but no matter which move we perform we see that the green middle, the red/green edge and the red middle never moves. So no matter which allowed moves we chose, we never affect the orientation of the red/green edge, hence we can never solve this scramble.
The second case we explore is if the two locked faces do not share a common edge. Again we can, without loss of generality, choose two faces that does not share an edge, so let’s pick white and yellow as the locked faces. Now keep white on top, and red at the front and do the following scramble:
U' R' F'
Now our goal is to fix the red/white edge without using U and D moves. We now look at how our algorithm could look for solving this edge. Let’s explore the available first moves:
- L, R and B moves wouldn’t work since they don’t affect any of the three pieces at all, hence we are no closer to a solution
- U or D moves are not allowed
This leaves us with the first move F. And we will continue to explore the following move.
- L and B moves do not affect the pieces
- U and D moves are not allowed
- F leaves it “stuck” in bottom layer until another F moves which is a symmetric position to what we saw after the first F move
So our second move is R
Now the only available move that affects the piece is R, hence our third move is R. Repeating the same intuition we quickly realize that the red/white edge cannot be placed in the correct orientation between the red and white center pieces. The algorithm simply ends up in symmetric positions to the ones we have already seen.
Another way to show that this case is impossible to solve, is to explore all possible locations the edge piece can end up in, given a particular move set. I have implemented a small program in Racket, that given a move set, an initial edge position and a goal position, finds an algorithm to achieve the goal, by exploring all possible moves (ignoring duplicate positions). As we only care about a single edge piece, the state space is not very big, hence the programs runs very quickly. It can be found here and (unsurprisingly) finds no solution that flips the red/white edge piece without U or D moves.
Conclusion
We have shown that a reduction from 18 moves to 5 moves is possible, but a further reduction to only 4 moves introduces cases that cannot be solved. The minimal move set therefore is 5 out of the 6 faces of the Rubik’s Cube.
