I've talked about the Rubik's Cube before and linked to last year's paper by Kunkle and Cooperman proving Twenty-Six Moves Sufﬁce for Rubik’s Cube.
Now Tomas Rokicki has proved that Twenty-Five Moves Suffice for Rubik's Cube. Actually, what he proved is that no configuration takes 26. If x <= 26 and x != 26 then x <= 25 QED.
It is known that some configurations need 20 moves and that no configuration needs 21. So the possible optimal move maxima are 20, 22, 23, 24 and 25.
UPDATE: Actually, I don't think it's been proven that no configuration needs 21, just no configuration has been found that needs 21.
UPDATE 2: David Joyner informs me a 2nd edition of his book is coming out soon.
The original post had 3 comments I'm in the process of migrating over.