Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
The least amount of moves it takes to solve the cube is 22 moves, I believe and It's known as the God's Algorithm. –  gekkostate Aug 20 '12 at 20:07
2  
@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). –  celtschk Aug 20 '12 at 20:11
7  
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. –  Steven Stadnicki Aug 20 '12 at 20:12
4  
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. –  Will Jagy Aug 20 '12 at 20:57
add comment

3 Answers

up vote 16 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
5  
So the bored god is the devil. :-) –  celtschk Aug 20 '12 at 20:20
add comment

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.

share|improve this answer
    
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). –  celtschk Aug 21 '12 at 7:27
    
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. –  fjdumont Aug 21 '12 at 7:47
    
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 :-) –  celtschk Aug 21 '12 at 8:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.