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|
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. The results can be seen in this table:
|Number of moves required to solve||Number of possible configurations|
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 A1..A3674160. 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'1..A'3674160.
Let D = A1A'1A2A'2..A3674160A'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 An. While executing the algorithm, after every pair of AiA'i for i < n, the cube will return to configuration n. Then, after An 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.
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.
Proof: Construct a Devil's Algorithm by setting D = N1->2N2->3...N3674159->3674160N3674160->1, where Ni->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.
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."
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.
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.
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.
Hosted by theorem.ca