johnkemeny.com

Dear friends, both known and unknown to me, fellow Russians, and people of all countries and continents, in a few minutes a mighty spaceship will carry me into the far-away expanses of space. What can I say to you in these last minutes before the start? At this instant, the whole of my life seems to be condensed into one wonderful moment. Everything I have experienced and done till now has been in preparation for this moment. You must realize that it is hard to express my feeling now that the test for which we have been training long and passionately is at hand. I don’t have to tell you what I felt when it was suggested that I should make this flight, the first in history. Was it joy? No, it was something more than that. Pride? No, it was not just pride. I felt great happiness. To be the first to enter the cosmos, to engage single handed in an unprecedented duel with nature – could anyone dream of anything greater than that? But immediately after that I thought of the tremendous responsibility I bore: to be the first to do what generations of people had dreamed of; to be the first to pave the way into space for mankind. This responsibility is not toward one person, not toward a few dozen, not toward a group. It is a responsibility toward all mankind – toward its present and its future. Am I happy as I set off on this space flight? Of course I’m happy. After all, in all times and epochs the greatest happiness for man has been to take part in new discoveries. It is a matter of minutes now before the start. I say to you, ‘Until we meet again,’ dear friends, just as people say to each other when setting out on a long journey. I would like very much to embrace you all, people known and unknown to me, close friends and strangers alike. See you soon! – Yuri Alekseevich Gagarin, first person in space, April 12, 1961

Τ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.