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.
Categories
All News blogs
Most Commented
Most Recommended
Tech Bytes
Most Commented
Most Recommended
Recent Entries
- 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
is a multimedia producer for CBCNews.ca.
Comments (8)
If it takes a computer to solve a rubik's cube in 26 moves and to solve it in 8000 hours just think how long it would take the average human to solve it within 26 moves? probably a whole life time.
Do they even sell these things anyomore? I remember having one as a kid. It took about two months to solve the thing the first time, and I kept shaving time off until it would take the better part of a day.
I've recently read about a competition being held in Michigan I believe, and the average completion time is 14-20 seconds. Whoa. Now, I don't know if that's for a partially completed puzzle (probably) or for a completely random one, but I find it impressive nonetheless.
Just wait until they program them [the robots] to boast to other robots about how much better they are when solving Rubix Cubes. It'll be one hell of a sight to see.
Once you know how to recognize cube orientation and move the cubes into place, solving the puzzle becomes easy. I could do it in less than a minute back in the day. This summer, I found an old cube at my parents' place. Solving the cube is not like riding a bike it turns out.
One guy takes it a step further by studying it for a few minutes then solves it blind folded...I guess remembering Pi got boring!
For a pro, 14-20 seconds for a completed puzzle is quite believable. My younger sister took it upon herself to figure out the Rubik's cube and she can easily solve a completely random puzzle in about a minute, every time. I'm sure she uses way more than 26 moves tho - I'm going to have to count next time!!
I know someone who does it in about 16 seconds each time for a completely scrambled cube. Seriously, who does a "partially" scrambled cube? And what is a "partially" scrambled cube? It still takes me about five minutes. And yeah, it takes way less time to just do it without using 26 moves.
Actually Dan, it would take a lifetime just to count to 1 billion...so that computer did something like 500 lifetimes of work.