The Devil's Number and The Devils' Algorithm

While walking home from work one day, contemplating the cube and God's Number, I had the idea that there is an opposite idea as well, which I cleverly called "The Devil's Number". When I got home I did a quick check on the internet to see if anyone else had come up with a similar idea, and found out that they had. 20 years ago. And they called it the same thing. Well, so much for being original.

However, I didn't find a lot of information online, so I decided to do some thinking and make a little website. So, first, some definitions.

Definition: A Devil's Algorithm is defined as a set of moves that when applied, repeatedly if necessary, will eventually return a Rubik's Cube to a solved state regardless of the starting configuration.

Definition: The Devil's Number is the number of moves in the shortest Devil's Algorithm.

For the time being, I will restrict myself to talking about the 2x2x2 Pocket Cube, since I can actually analyze the solution space of that one with my home computer. Furthermore, from this point forward I will always use the "quarter turn" metric, because I find it easier to think about.

First, I wrote a quick program to verify that God's Number is equal to 14 for the Pocket Cube. The results can be seen in this table:

Number of moves required to solve	Number of possible configurations
0	1
1	6
2	27
3	120
4	534
5	2256
6	8969
7	33058
8	114149
9	360508
10	930588
11	1350852
12	782536
13	90280
14	276
Total	3674160

So we can see that there are 3674160 unique configurations of the Pocket Cube, and you need at most 14 moves to solve any one of them.

Theorem 1: An upper bound for the Devil's Number is 78380016.

Proof: Construct a Devil's Algorithm as follows. Enumerate all possible configurations, and for each configuration, list the shortest possible algorithm to solve it.
Call these algorithms A₁..A_3674160. Each of these algorithms has an inverse. This follows from the fact that the list of algorithms forms a mathematical Group, which can be easily checked.
Call the inverses A'₁..A'_3674160.
Let D = A₁A'₁A₂A'₂..A_3674160A'_3674160.
Then D is a Devil's Algorithm, because the cube will start off in one of the 3674160 possible configurations (call it "n"), and the algorithm required to solve is thus A_n. While executing the algorithm, after every pair of A_iA'_i for i < n, the cube will return to configuration n. Then, after A_n is executed, the cube will be solved.
Since D is a Devil's Algorithm, and it can easily be checked that D has length 78380016 (due to the fact that the inverse of an algorithm must be the same length as the original algorithm), we have proven our result.

Note that in the proof of Theorem 1, it is possible to go through any given state many times. In fact, if we order the states in order of "easiest" to "hardest" to solve, and the cube starts out in state 3674160, the algorithm will cycle through that state exactly 3674159 times again before it is solved.

We can obviously do better.

Lemma 1: You can get from any configuration to any other configuration in 14 moves or less.

Proof: Suppose we wish to get from configuration N to configuration M. Consider a second cube that is in configuration M already. Now peel all of the stickers off this second cube, and reapply them so that the cube is in the solved state. Keep track of which stickers were moved to which locations, and call this sticker rearrangement R.
Note that R is a legal rearrangement of stickers (meaning it produces a solvable cube), because cube M was in a legal configuration.
Now, perform the exact same sticker rearrangement R on the first cube in configuration N. Since the sticker rearrangment R is "legal", the cube will still be in a legal configuration N*. Now, solve the first cube using God's Algorithm for configuration N* (we will call this algorithm God(N*)). Then apply the reverse sticker rearrangement R' to the first cube, thus putting it in configuration M.

To summarize, we have taken cube N, applied sticker rearrangement R to get N*, solved N* in 14 moves or less, and applied sticker rearrangement R' to get M.
Now, since the mechanics of the cube do not depend on sticker positions, the two sticker rearrangments in the above set of steps can be cancelled out.
Therefore, we have found an algorithm God(N*) that is 14 moves or less that gets us from configuration N to configuration M.

Note: I know this isn't a very rigorous proof, but hopefully when I have time I will make it better.

Theorem 2: A slightly better upper bound for the Devil's Number is 51438240.

Proof: Construct a Devil's Algorithm by setting D = N_1->2N_2->3...N_{3674159->3674160}N_3674160->1, where N_i->j is an algorithm that takes you from configuration i to configuration j. We know from Lemma 1 that such an algorithm exists and is at most 14 moves long.

This algorithm cycles through every possible state, and is at most 3674160 * 14 = 51438240 moves long.

Can we do even better? Hopefully... but for the time being let's try to set some lower bounds.

Theorem 3: Any element of the permutation group of the Pocket Cube has an order of at most 36.

Proof: I proved it to myself by exhaustive computer search. I'm sure there is an easier way to prove it as well.

Update: I received an email from Mark Eichenlaub with a simple proof.

"Any permutation can be broken down into cycles. We're permuting eight corners, but because rotations of the entire cube are meaningless, we need to declare one particular corner to be in place, and so we're really permuting seven corners. If we look at a single seven-cycle, that has order 7 or 21 (7 if it doesn't mess up orientations, 21 if it does). A 2-cycle and a 3-cycle have order 6 (or 18). The highest order you can achieve comes from a 3-cycle and a 4-cycle, so that we need to do the permutation 12 times to put everything back in place, and do all that 3 times, or 36 total, to get the orientations right."

Thanks, Mark!

Corollary: A lower bound for the Devil's Number is 102060.

Proof: From Theorem 3, any algorithm, if repeated, will return to the starting position in 36 repetitions or less. This means that in order to cycle through every possible state, the algorithm must be at least 3674160 / 36 = 102060 moves long.

Further Thoughts

• For every given algorithm, there is an equivalent member of the cube permutation group (i.e. another algorithm that performs the same operation) of length 14 or less.
• Preliminary exhaustive maximum coverage calculations give the following results:

• This preliminary data suggests that the Devil's Number is at least 10000. I haven't been able to work out a reasonable curve fit to this data yet to make a better prediction.

References

http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/13440

http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/13969

http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/13973

http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/13976