Rubik's Cube Hamiltonian Cycle

Rubik's Cube Hamiltonian Cycle

It has now been proven that there exists a way to manipulate a Rubik’s cube so that you visit all 43,252,003,274,489,856,000 different states and without repeating a position at any point along the way. Even better than that, you can accomplish this feat so that when you are finished a single move will be enough to take you back to the position you started with. We call this a Hamiltonian Cycle. Notice that no matter which position you started with, your cube will be in a solved state exactly once somewhere along the way.

The method comes from group theory, but I'll try to give the spirit of the argument without using too much technical language. We are going to start by looking at the set of moves {UR} which is one movement of the Upper face followed by one movement of the Right face. After 105 applications of this pair of moves we end up back at the original position. Instead of completing the last of these moves we instead do the first move of the next set which is {U,R} so we complete a single move U, then repeat the first group again. This behaviour continues, completing all of the sets below before taking the next element of the highest up set and proceeding to the next set every time you are done.

The sets in order are: {UR} {U,R} {U,R,D} {U,R,D,L} {U,R,D,L,F}. Notice that we never perform a turn on the Back face to enact our cycle. Every set eventually loops and we are doing enough loops of each set that we almost get back to the same point on the cube each time before interrupting it with an action from the next set. These loops get incredibly long.

To get an idea of what this sort of algorithm would look like, here are the first 31 lines (out of 51031 lines) for a similar algorithm for the simpler 2x2x2 pocket cube:

 V means U'

V means U'

Charlie's Puzzle Solutions

Charlie's Puzzle Solutions

God's Number

God's Number