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.

UPDATE - February 20th, 2013: I am ready to make an educated guess about the value of the Devil's Number for the standard 3x3x3 Rubik's Cube. I claim that the Devil's Number for the Rubik's Cube is 34,326,986,725,785,601 (using the quarter turn metric). This is 43,252,003,274,489,856,000 (the total number of possible permutations) divided by 1260 (the largest possible order of an algorithm) plus one. This guess is based on patterns observed with the "Restricted" Pocket Cube puzzle and the regular 2x2x2 Pocket Cube puzzle that I have explored below. If someone out there can actually figure out how to prove or disprove that this is the Devil's Number for the Rubik's Cube, I would love to hear from you.

So far I believe that we have proved that the Devil's Number for the 2x2x2 Pocket Cube is between 102060 and 2886840. We have also proved that the Devil's Number for the standard Rubik's Cube is between 34,326,986,725,785,600 and 43,251,683,287,486,463,996.

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.

UPDATE - February 15th, 2013: I received an email from Melinda Green (the creator of Magic Cube 4D), who suggested that I consider restricting the 2x2x2 puzzle by only allowing half turns. This was a great idea, since it actually makes finding the Devil's Number possible by brute force. So, I can now announce that the Devil's Number for the Restricted Pocket Cube is 7, and a Devil's Algorithm for the Restricted Pocket Cube is RURURBR. This means that even someone who is completely blind can solve the Restricted Pocket Cube by repeating this sequence over and over again until the cube is solved.

Let us quickly run through some stats for the Restricted Pocket Cube:

God's number for the Restricted Pocket Cube is 4:

Number of moves required to solve	Number of possible configurations
0	1
1	3
2	6
3	9
4	5
Total	24

Since the total number of states for the Restricted Pocket Cube is only 24, we can draw a graph of the entire state space:

By Theorem 1 (see below), an upper bound for the Devil's Number is 126.

By Theorem 2 (see below), a better upper bound for the Devil's Number is 96.

Since the maximum order of any algorithm for the Restricted Pocket Cube is 4 (left as an exercise to the reader), then by the Corollary to Theorem 3 (see below), a lower bound for the Devil's Number is 24 / 4 = 6.

Just by quickly playing around with the graph pictured above, I found the following Hamiltonian path for the Restricted Pocket Cube: UBRURBUBRURBUBRURURBRBR (23121323121323121213131). Thus by Theorem 4 (see below), a better upper bound for the Devil's Number is 23.

By Theorem 5 (see below), since the first 6 moves are repeated in the next 6 moves, then the last 17 moves also constitutes a Devil's Algorithm for the Restricted Pocket Cube. So a better upper bound for the Devil's Number is 17.

Since we know that the Devil's Number is actually 7, it is nice to see that my lower and upper bounds are actually reasonable.

Now let us return to the unrestricted Pocket Cube to see what progress can be made.

First, I wrote a quick program to verify that God's Number is equal to 14 for the Pocket Cube.

Important note! I will be considering the Pocket Cube only in configurations where the Red+White+Blue corner is in the front upper left (FUL) position, with Red pointing up. This reduces the number of possible states I have to consider by a factor of 24 due to rotational symmetry of the entire cube. Now, you may ask whether this affects the Devil's Number for the cube, and the answer is: Maybe. More work is required to determine whether you can find a shorter Devil's algorithm if you allow movement of the RWB corner.

Thanks to Paul Kwiatkowski for noticing this unstated assumption that I made. See Theorem 3 below for how this may affect the Devil's Number.

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!

Note: Paul Kwiatkowski pointed out that I wasn't considering certain move combinations, due to my desire to simplify things by keeping the RWB corner in the FUL position. It turns out that if you relax this restriction, the maximum order of the Pocket Cube is actually 45. The move sequence U, R', D, D has order 45. This was found by David Singmaster. I verified (again via exhaustive computer search) that this was correct.

This gives a lower bound for the Devil's Number of 3674160 / 45 = 81648, which is lower than the value given by the Corollary below.

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.

Theorem 4: An upper bound for the Devil's Number is 3674159.

Proof: Hamiltonian paths have been found for both the 2x2x2 and 3x3x3 cubes by cuBer Bruce. A Hamiltonian path is an algorithm that visits every possible state of the cube exactly once. Thus, a Hamiltonian path for the 2x2x2 cube is 3674159 moves long.

Since a Hamiltonian Path is a Devil's Algorithm, then there exists a Devil's Algorithm of length 3674159.

Theorem 5: An upper bound for the Devil's Number is 2886840.

Proof: This result is due to cuBer Bruce again. In his Hamiltonian path for the Pocket Cube, the first 787320 moves are repeated in the next 787320 moves. Therefore, the last 2886840 moves is a valid Devil's Algorithm, since by self similarity of the cube graph you can shift a Hamiltonian path by any number of moves, and thus you can choose to start it at the 787321st move, and repeating that 2886840 move sequence will complete the Hamiltonian circuit of the cube.

Further Thoughts

• Based on the results for the Restricted Pocket Cube, I'm going to go out on a limb and predict that the Devil's Number for the Pocket Cube is 102061.
• 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 around 102060 (2 * x + 3), which is extremely close to my prediction of 102061.

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

http://bruce.cubing.net/

http://www.mersenneforum.org/showthread.php?t=16597

https://www.randelshofer.ch/rubik/virtual_cubes/pocket/instructions/2x_instructions_big.html