Supercomputer takes on Rubik's Cube
- August 17, 2007 3:23 PM |
- By Paul Jay
by Paul Jay, CBCNews.ca
The Rubik's Cube was never my bag growing up, but clearly, some people still remain devoted to solving the seemingly simple yet surprisingly complex puzzle game in as few moves as possible.
How many moves is that you ask? A pair of researchers at Northeastern University in Boston say they've come closer to the answer, proving that a Rubik's Cube can be solved in 26 moves or fewer.
The two announced their findings two and a half weeks ago at the International Symposium on Symbolic and Algebraic Computation hosted by the University of Waterloo.
As the BBC reports, the two had to figure out a way to go through the potential 43 billion billion possible cube positions - a task too daunting even for today's supercomputers. So instead they programmed the computer to arrive at one of 15,000 half-solved solutions they knew could be solved with a few extra moves.
That gave the computer a more manageable database to work with - though it still took the computer 8000 hours - and in the end the computer was able to solve all of the positions in 26 moves or less.
It's not the final word on the subject, however, as the two suggest the actual minimum number of moves to solve all positions - which has been dubbed 'God's number' - is probably lower.
You can read the actual pdf of the report here.
All News blogs
- Universe hates Higgs boson, Chicago Cubs
- By John Bowman, CBCNews. A physicist working on the Large Hadron Collider doesn't think much of the theory that the universe is sabotaging the project to prevent the discovery of the Higgs boson. Might as well say that Nature hates... Continue reading this post
- Large Hadron Collider goes Back to the Future
- By Peter Evans, CBCNews.ca. Two respected physicists have put forward the theory that the Large Hadron Collider's stated aim of finding the Higgs boson might be so abhorrent to nature that mysterious forces are traveling back through time and sabotaging... Continue reading this post
- Multi-touch concept for desktops: 10/GUI
- By John Bowman, CBCNews.ca. I'm a fan of alternative ideas for human-computer interaction, so this video caught my attention. It shows an idea for a ten-finger touchpad interface and associated changes in the way a computer would handle multiple windows.... Continue reading this post