One of the mailing lists I’m on pointed out the following project to make a LEGO robot that could solve the Rubik’s cube:
Very slick, but it mentioned something I found even more interesting: Herbert Kociemba’s algorithm for quickly solving the Rubik’s cube:
In his testing, he generated one million random cubes, and tried to solve them using his program. He found no candidates which could not be solved in 20 moves or less. As far as I know (and this might be out of date) there are proofs that 25 moves is sufficient, and there are positions for which 20 moves is necessarry, but it isn’t known what number actually suffices.
I spent six months carrying around a Rubik’s cube back when they were the fad in high school (at least among geeks like me), and ultimately had my own rather pathetic way of solving the cube (it was slow, and usually took me ten or fifteen minutes to do). Fun stuff.