34
$\begingroup$

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)?

$\endgroup$
4
  • 3
    $\begingroup$ @gekkostate: IIRC it's 20 moves. However I asked not about the shortest sequence to solve a given cube, but the shortest sequence to visit every position (which could then even be used — at least in principle — to solve a cube you can't see, provided someone tells you after each move whether it is solved or not). $\endgroup$
    – celtschk
    Aug 20, 2012 at 20:11
  • 8
    $\begingroup$ Actually, there's a pretty good reason to believe that a minimal 'bored god's algorithm' does exist! What you're talking about is a Hamiltonian path on the so-called Cayley Graph of the cube's symmetry group (a graph whose nodes are positions and whose edges correspond to moves between one position and the next), and the Lovász conjecture (en.wikipedia.org/wiki/Lov%C3%A1sz_conjecture) contends that every finite and connected Cayley Graph has such a path. $\endgroup$
    – Steven Stadnicki
    Aug 20, 2012 at 20:12
  • 6
    $\begingroup$ You can pull the pieces apart and put them back together as you like. I'm not sure how many moves that counts as. But it is brute force. $\endgroup$
    – Will Jagy
    Aug 20, 2012 at 20:57
  • $\begingroup$ @JeelShah Wrong, in July 2010 they calculated that it is 20, not 22 cube20.org $\endgroup$
    – MCCCS
    Oct 2, 2017 at 14:11

3 Answers 3

Reset to default
21
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
1
  • 6
    $\begingroup$ So the bored god is the devil. :-) $\endgroup$
    – celtschk
    Aug 20, 2012 at 20:20
4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Note: $2.44\cdot 10^{13}$ years $\approx 1877$ times the age of the universe. This means, a bored god must do it a bit faster than five moves per second if he wants to be finished by the time intelligent life appears in his universe (assuming our universe is typical). $\endgroup$
    – celtschk
    Aug 21, 2012 at 7:27
  • 1
    $\begingroup$ That is an interesting comparison I wasn't aware of :) Also note that Eivind Fonns Devil's Algorithm might not be the shortest one available on the interwebs, I'm pretty sure there are shorter ones available. $\endgroup$
    – fjdumont
    Aug 21, 2012 at 7:47
  • $\begingroup$ Yes, the algorithm linked to by Robert Israel (assuming it is correct) needs only $\approx 4.3\cdot 10^{19}$ moves, which for 5 moves per seconds needs in the worst case $\approx 2.7\cdot 10^{11}$ years, or $\approx 20$ times the age of the universe. However with about 200 megabytes of specification, you need a quite stellar memory to do it in your head :-) $\endgroup$
    – celtschk
    Aug 21, 2012 at 8:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .