Someone proved that Rubik's Cube can be solved in at most 26 moves:
http://www.ccs.neu.edu/home/gene/papers/rubik.pdf
I think the SPOJ crowd might enjoy the paper (even if you're not really into playing with that annoying cube). They use some pretty cool mathematics to drastically reduce the search space. Just the kind of thing that may take you from TLE to AC. 
-- Mauro
