Exactly half of the theoretically permutations are even (see 34 for prove), therefore only 1/2 of the permutations are valid.
We can create a lower bound for the God's number using the possible number of permutations created and the total number of permutations. There are 6 faces with 3 options each (90 o clockwise/90 o anti-clockwise/180 o ) giving 6 x 3 = 18 options. In an optimal solution, no consecutive moves will be of the same face,
thus the remaining moves only have 15 options. Let the God's Number be n . We have the inequality
18 • 15 n−1 ≥ 43252003274489856000 15 n−1 ≥ 2.403 • 10 18
log(2.403 × 10 18 ) log(15)
n ≥
= 15.6…… = 16 (rounded up to the nearest integer)
However, a lot of move sequences within 16 moves actually create the same permutation. By analysing the different move sequences of 17 or fewer moves, the lower bound of 18 has been established in 1980 35 . In 1995, Michael Reid increased the lower bound to 20 by proving that the optimal solution of the 'Superflip position' requires 20 moves. 36 While the lower bound has stayed at 20 since 1995, the upper bound has dropped from 29 in 1995 to just 22 in 2008 35 .You may wonder if it's possible to find optimal solutions for all 4.3 x 10 19 permutations with current technology? The answer is no, but not far off. By breaking them down into smaller problems (partitioning) and using symmetry, the number of sets to be solved could be reduced to 55,882,296 35 . Since the lower bound of 20 has already been established, it is not necessary to find the optimal solution for each permutation. The computer can stop searching for better solutions once a 20- move solution is found. With the help of mathematical tricks, accurate programming and powerful computers (from Google!), all the cases have been checked 35 and it is shown that all of them can be solved within 20 moves! The God's number is finally proved to be 20 in 2010 by Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge 31 . The God's Number is found after years of investigation, but it is not the end of the story. Is there a mathematical reason of why every permutation can be achieved in 20 moves? What makes a permutation (e.g. Superflip) 'difficult' (require 20 moves)? There are still a lot of mathematics behind the Rubik's Cube to be unravelled
34 Provenza, H. (2009) Group Theory and the Rubik’s Cube. University of Chicago 35 God’s Number is 20 (no date) Available at: http://www.cube20.org/ (Accessed: 19 August 2014) 36 Superflip (2014) in Wikipedia. Available at: http://en.wikipedia.org/wiki/Superflip (Accessed: 19 August 2014)
52
Made with FlippingBook - Online Brochure Maker