Image via Wikipedia
Technology ThursdayI still have the very first Rubik's Cube I ever owned. I never solved it. I mean, I never figured out how to solve it on my own. I did get a 'solution' at some point and solved it using that. But of course, that's totally cheating. Still, what a great toy. And really timeless. I have no idea what the sales figures for Rubik's Cubes have been like over the years. I'm sure there have been ups and downs. But it seems to me if you have a kid who's into puzzles or math, that it's a must-have. I had several other toys at the time that were variations on the theme - one shaped link a pyramid, one that involved links, and I think I even had a mini-Rubik's Cube on a keychain. But it was the iconic full-size cube that I've kept all these years.
Turns out that scientists are still thinking about the Rubik's Cube.
Any Rubik's Cube configuration can be solved in 20 moves or fewer, according to new research. The recent puzzle-based findings come from a small group of researchers, including a university mathematician and a Google engineer. Collectively they found that every single one of a Rubik's Cube's massive 43,252,003,274,489,856,000 combinations can be solved in just 20 moves or less.From this brief write-up of how it was done, it seems that they used some mathematics (group theory) to divide up the problem, and then applied huge amounts of computational resources to do some brute force searching of all possible solutions. The minimum number of moves to solve any configuration is apparently referred to as "God's Number." The BBC notes:
The figure is known as "God's number" because an all-knowing entity would know the optimal number of steps needed to solve the puzzle. "We now know for certain that the magic number is 20," Professor Morley Davidson, a mathematician from Kent State University, told BBC News. The results suggest that there are more than 100 million starting positions - of a possible 43 billion billion - that can be solved in exactly 20 moves. However, the majority of solutions take between 15 and 19 moves to solve.So, not only could you give a puzzle-obsessed kid a Cube and have them figure out how to solve it. You could then further challenge them to see in how few moves they could solve it! For myself, I sort of lost interest once it became clear to me that there was an algorithm to solving the Rubik's Cube. Later on in life I figured out that, for me, once something is provably solvable, it's solved! It's similar to the way that tic-tac-toe quickly becomes boring once you realize you can always play to a stalemate. I'm personally more interested in the existence of a general solution (a proof or algorithm) than in actually solving any specific configuration myself. (It's probably why I studied math and software and now poke around at hard policy problems.) But those kinds of analyses are far in the future for my 2-year-old. And I'll be making sure he has lots of puzzles, like the Rubik's Cube, to play around with.
P.S. I was going to write about the Google/Verizon alliance regarding net neutrality (or net non-neutrality) this week, but my head hurt just reading about it. For starters, the EFF and Wired are not pleased.