Tomas Rokicki has improved the computer-assisted proof of the maximum number of moves that may be needed to solve Rubik's cube. It has been proven that 26 moves were enough; now, 25 moves are enough. Check it out. ;-)
The number 25 is the rigorous upper bound. The actual maximum number of moves may be lower. The most "complex" known configurations require 20 moves to be solved. So the actual correct maximum number of moves is between 20 and 25 moves. Well, I usually needed hundreds. ;-)
Hat tip: arXiv blog
Update: In 2010, the proof was radically improved. It's possible to sort the Rubik's cube in 20 moves.
Technical note: viewing this blog
Everyone with such problems is recommended to download Firefox 3 beta 5, released one hour ago for all operating systems - it works smoothly and very quickly - and bookmark the economical feed versions of this blog, including