Τomas Rokicki is a man of many algorithms. He co-authored Golly, a Life simulator that is super fast due to its unique hashlife algorithm. Last month he proved that 25 face moves (where face move = a quarter or half turn) are suffficient to solve any Rubik’s cube, and he did it using a computer (similar to the solution to the famous Four Color Problem) – specifically, he used Herbert Kociemba’s Cube Solver, which you can download for free.
In 1995 Michael Reid showed that 20 moves were necessary to solve the superflip (pictured). Kociemba ran his cube solver over 1 million random configurations, and not one needed more than 20 moves to solve. He then ran 1000 optimal random configurations (at ~2 minutes per solution with 3 GHz processors and 8 GB memory) and found the “average” cube can be optimally solved in ~18 moves. It clearly appears that 20 moves should suffice to solve any Rubik’s cube. But can that be proven?
Initially, solution algorithms could take up to 75 moves. In 1995 Reid showed Kociemba’s algorithm could reduce the maximum to 29 moves, still quite a ways from 20. In 2006 this was improved to 27, and in 2007 to 26. Now, thanks to Tom Rokicki, it stands at 25 - and he is on to 24.
Update: As of June, Rokicki cut it to 23 using a Sony/Spiderman render farm.
Update: As of August, Rokicki cut it to 22 using the same Sony/Spiderman render farm.