Rubik’s Cube Cracked
August 11th, 2007 by SplineGuy
I am no expert when it comes to the Rubik’s cube. As a kid, my strategy was to start with a completely solved cube and to rearrange in such a way that I could always reverse my steps. I’d go a little further each time until I couldn’t get it back, at which point I would try a series of random rearrangements until I eventually gave up and waited for someone else to “heal” my cube. Occasionally I would even resort to the guaranteed method of disassembling the cube by popping out the pieces and sticking them back in their appropriate location. It didn’t take long for this to destroy the cube so that it was practically impossible to play with any longer. Only once did I resort to removing the stickers and putting them back on. After only once they start to fall off on their own. That wasn’t too bad since a Rubik’s cube with missing stickers is certainly easier to solve.
I know you’d probably expect a mathematician to be able to have mastered the art of the cube but I just never took the time to think it through and apply a logical approach. Before my mind goes, I plan on getting one and conquering it once and for all. I was quite impressed when one of my students from Wayland was able to quickly solve one from any arrangement. By quickly I mean a couple minutes, maybe even less than a minute. That was impressive, but not as impressive as the kid who can study a Rubik’s cube then put on a blindfold and completely solve the cube. If you don’t believe me: Check this out.
I was reading MathTrek, and learned that Daniel Kunkle, a computer scientist at Northeastern University has proved that 26 moves are enough to solve ANY Rubik’s cube (3×3x3), no matter how scrambled. There are approximately 43 quintillion possible configurations for a 3×3x3 Rubik’s cube (that’s 43,000,000,000,000,000,000). When you eliminated equivalent configurations such as rotations and color symmetry, you still end up with just over a quintillion. It was interesting to see how you can show that 26 is enough considering that is beyond the scope of having a computer simulate every possible configuration.
Powered by ScribeFire.
I’ve written computer game solver programs for other perfect information games. 8 queens, a solitair card game, etc. One can often tell the computer how to reduce the cominations that need to be checked. The 8 queens problem can be solved by checking all 8^8′th positions (16,777,216), which used to be a big deal. But there are ways to eliminate huge parts of the problem, and all solutions can be generated in under a millisecond.
Sometimes there are ways to stochastically eliminate likely dead ends and find very good solutions quickly. So, this one solitar card game i’ve worked on typically has something like 4^70 (10^42) possible solutions, but a computer checking less than 10^9 solutions can get one of the optimal solutions at least 999 out of 1000 times, taking a few minutes at most.
The big deal recently, has been the solving of checkers, creating an unbeatable opponent. All moves are book moves. I remember hearing about the project in the late 80’s. It’s been 30 years.
You know, Scott, I remember when I was smarter than you (simply becase I am older)… now I read your blog and say… um, huh?