Brute force method of solving the cube: How many moves would it take?

Given that Rubik's cube has finitely many positions, one possible "brute force" method to solve it would be to determine once a sequence of moves which eventually reaches every possible position of the cube, and then whenever you want to solve a cube, you just mindlessly follow the sequence until you eventually reach the solved cube. This strategy is absolutely failsafe, provided you have an extraordinary memory and enough time (so, it's not a strategy for humans, but maybe for bored gods waiting for their just created universe to finally develop intelligent life ;-)).

However, the question is: How many moves does the shortest possible sequence which visits every reachable position have? Of course, it's easy to give a lower bound: At least as many moves as there are reachable positions, which according to Wikipedia is $43\,252\,003\,274\,489\,856\,000 \approx 4{.}3 \cdot 10^{19}$. However, I doubt that there's a sequence which gives a not yet visited position at every move, so the actual number of moves is likely even higher.

Is there maybe even a constructive method to create this "bored god's algorithm" (so that even gods with less than stellar memory can apply it)?


At http://bruce.cubing.net/index.html it is claimed that there is a Hamiltonian circuit for the corresponding graph. Thus there is a sequence of moves that goes through each position exactly once and then comes back to the original position.


This is known as the "Devil's Algorithm" in Rubik's cube circles. There are some results concerning this, mostly on websites rather than published papers, but I'm pretty sure it's unsolved. One such page, which only deals with the 2x2x2 cube, is here. I don't know any better bounds for the 2x2x2 cube, and essentially no bounds at all for the 3x3x3 one.

The problem is equivalent to a graph-theoretical problem (for the 3x3x3 cube), namely what is the minimal path in the Cayley graph of the cube group (specifying either of the standard generating sets, either the quarter-turns or face-turns, which correspond to slightly different problems). If the devil's number is equal to the order of the cube group, that is equivalent to the statement that the Cayley graph of the cube group has a Hamiltonian path, which is typically very difficult to prove computationally.

Edit: According to Robert's answer, the problem has been solved.


Eivind Fonn (a cuber himself) actually developed a so-called "Devil's Algorithm".

[...] If you apply it to the cube, it will be solved at some point before you have done the algorithm once. [...]

Although it is suboptimal (3,847,762,288,469,010,006,992 moves [HTM]), I'm pretty sure I found a proof for his version like two years ago on a fairly large web community. I just don't seem to be able to find it anymore...

His version basically consists of substitutions, thus quite short and easily memorizable for any human person.

In the worst case, you will reach the solved state with the last move. In that case, doing 5 turns per second [TPS] (that's a fairly realistic number for a speed-cuber, taking no thinking-time into account), reaching that state will take you $\frac{3,847,762,288,469,010,006,992}{TPS * 60 * 60 * 24 * 365}\approx2.44\cdot10^{13}$ years (in case you don't intend to sleep).

A few more details and the actual algorithm can be found as a text document on his webspace.

TL;DR: Yes, you can build and memorize the Devil's Algorithm without a stellar memory. Will you ever reach a solved state with this method within you lifetime? Probably not.