Pages

August 21, 2010

Rubiks Cube Coset Solution

Ad Support : Nano Technology   Netbook    Technology News    Computer Software

Tomas Rokicki combined the computing might of Google with some clever mathematical insights to check all 43 quintillion possible jumbled positions the Rubiks cube can take and has shown that it takes a maximum of 20 moves to solve any cube.

* First they divided the set of all possible starting configurations into 2.2 billion sets, each containing 19.5 billion configurations, according to how these configurations respond to a group of 10 possible moves. This grouping allowed the team to reduce the number of sets to just 56 million, by exploiting various symmetries of a cube. [40 times improvement from problem analysis]

* Rokicki's realised dead-end moves are actually solutions to a different starting position, which led him to an algorithm that could try out one billion cubes per second instead of previous algorithms that checked 4000 cubes per second. [250,000 times improvement from algorithm]

* An optimal solution to a position is one that requires no more moves than is required. Since a position that required 20 moves was already known, we did not need to optimally solve every position; we just needed to find a solution of 20 moves or less for each sequence. This is substantially easier; the table at left show the rate a good desktop PC has when solving random positions. The faster algorithm finds near optimal solutions that prove 20 moves or less.

* Solving each set of 19.5 billion in under 20 seconds would still take 35 years

* Used google cloud computing to solve in weeks [300 times speed up]


Here is a link to a paper that describes the Rubiks cube solution in more detail (but before the Google processing that confirmed 20 moves or less)

This work is interesting to get a sense for how near-optimal or approximate solvers can speed up the process of getting solutions. It also reveals how complex problems can be analyzed to reduce the complexity. It also reveals the progress over time to a solved complex problem.

Date   Lower bound Upper bound  Gap Notes and Links
July, 1981   18        52         34  Morwen Thistlethwaite proves 52 moves suffice.
April, 1992  18        42         24  Hans Kloosterman improves this to 42 moves.
May, 1992    18        39         21  Michael Reid shows 39 moves is always sufficient.
May, 1992    18        37         19  Dik Winter lowers this to 37 moves just one day later!
Jan, 1995    18        29         11  Michael Reid cuts the upper bound to 29 moves by analyzing Kociemba's two-phase algorithm.
Jan, 1995    20        29          9  Michael Reid proves that the ''superflip'' position (corners correct, edges placed but flipped) requires 20 moves.
Dec, 2005    20        28          8  Silviu Radu shows that 28 moves is always enough.
April, 2006  20        27          7  Silviu Radu improves his bound to 27 moves.
May, 2007    20        26          6  Dan Kunkle and Gene Cooperman prove 26 moves suffice.
March, 2008  20        25          5  Tomas Rokicki cuts the upper bound to 25 moves.
April, 2008  20        23          3  Tomas Rokicki and John Welborn reduce it to only 23 moves.
August, 2008 20        22          2  Tomas Rokicki and John Welborn continue down to 22 moves.
July, 2010   20        20          0  Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge prove that God's Number for the Cube is exactly 20.


Here is a link to the wikipedia list of the complexities of well known games.

If you liked this article, please give it a quick review on Reddit, or StumbleUpon. Thanks

Supporting Advertising

Business Success
   How to Make Money    
Executive Jobs    
Paid Surveys


Thank You
blog comments powered by Disqus