Rubik's Cube Now Solvable in 20 Moves 309
A few years ago we reported that it had been proven that Rubik's Cubes could be solved in 23 moves. Well now that number is
down to just 20. Proving it required 35 years of computer time donated by Google to get it done.
Another way of thinking about this. (Score:5, Informative)
The shortest path between any two configurations (be them solved or not) on a graph of all possibilities will be no greater than 20.
Re:Thank God! (Score:5, Informative)
Don't have to, World Community Grid has already been doing cancer cure grid computing for years.
This one is complete:
http://www.worldcommunitygrid.org/research/hdc/overview.do [worldcommunitygrid.org]
These two are still running:
http://www.worldcommunitygrid.org/research/hcc1/overview.do [worldcommunitygrid.org]
http://www.worldcommunitygrid.org/research/hfcc/overview.do [worldcommunitygrid.org]
Re:Enough! (Score:3, Informative)
Are you new here? This is /. so, it should be listed here [wikipedia.org] :-)
Re:Enough! (Score:4, Informative)
Start with your right arm behind the wearer. Make sure your thumb is on the reinforced section holding the clasp, behind the clasp, on the side to your right. Your index and middle finders should be in a similar position on your left. Squeeze your thumb and the index and middle finger towards each other, while also pressing slightly in (towards you) with your arm. The bra should now be unhooked.
(Lefties use your left hand and switch left and right above.)
Re:35 years of computer time?!?! (Score:2, Informative)
Finally, we were able to distribute the 55,882,296 cosets of H among a large number of computers at Google and complete the computation in just a few weeks. Google does not release information on their computer systems, but it would take a good desktop PC (Intel Nehalem, four-core, 2.8GHz) 1.1 billion seconds, or about 35 CPU years, to perform this calculation.
From the article. They are guessing based on a known configuration how long it would take.
Re:Enough! (Score:1, Informative)
My brother's a paramedic and he says scissors are the fastest.
Re:Why approximate numbers? (Score:3, Informative)
Re:Enough! (Score:2, Informative)
I can't speak for every /.'er but I can do with 1 finger in one move. But seriously this is cool.
Re:35 years of computer time (Score:1, Informative)
How about measuring that in actual computer usage? X MHz on Y cores per Z nodes over A hours? Or at least say it would have taken one X MHz processor 35 years to compute it.
A simple visit to the web page [cube20.org] followed by a modicum of reading would have led you to the following (emphasis added):
Re:35 years of computer time (Score:3, Informative)
Except clock-cycles, which is what you get from your equation, is also not a good measurement of "computer usage".
However, Google Tech Talks had a rather nice explanation of the algorithm and core mechanics for solving the problem a couple of years ago. Quite interesting for anyone in supercomputing, or just plain old curiosity.
http://www.youtube.com/watch?v=WQw7c-PliB4 [youtube.com]
How much computing power is this, really? (Score:5, Informative)
35 years is about 300k core-hours, a standard measure of computing resources. This is a big pile of computer time, but is not unreasonable.
So how much does this cost?
A typical supercomputer, Ranger [utexas.edu], cost $59 million to build and operate for four years. It's got about 60k cores, so $59 million delivers 240k core-years; they used 35 core-years to do this computation. Doing the division, you get $9000 of computer time -- not all that bad. Plugging in the cost numbers for another production supercomputer, Kraken [sciencedaily.com], gives a slightly lower cost.
Re:35 years of computer time (Score:2, Informative)
Re:Thank God! (Score:3, Informative)
"It's a problem that can't be prevented" and "it's a problem that can't be solved" are two rather different things. So it's caused by undesirable mutations as a result of radiation/chemicals/viruses... doesn't mean we can't fix it once it happens. That being more or less the definition of a cure - a fix you apply to a disease after you already have that disease.
I doubt we'll ever have a vaccine for cancer, for the reasons you mentioned, but a cure... a cure could be achieved.
Although rather than 1 cure for all cancer, it'd be more like hundreds of cures for all the different ways a cell can malfunction in a cancerous way. There may be a similar end result, but there's a lot more than 3 specific mutations that can produce a cancer.
Re:Why approximate numbers? (Score:4, Informative)
Re:35 years?!!! (Score:3, Informative)
Obviously the "computer" is one of Google's datacenter machines, which you could equate to a modern enterprise level server. Being too specific doesn't help nearly as much as you think it does. Furthermore:
1 computer running for 35 years = 35 computer years.
35 computers running for 1 year = 35 computer years.
70 computers running for 6 months = 35 computer years.
140 computers running for 3 months = 35 computer years.
420 computers running for 1 month = 35 computer years.
12,600 computers running for 1 day = 35 computer years.
Google gave them 35 computer years worth of time on one of their clusters, for all we know it could have been an hour of total time on the cluster (though that would be 300,000+ machines, so probably not). It probably wasn't more than a few months of actual time calculating.
Re:They're counting double moves as one (Score:3, Informative)
Re:Thank God! (Score:5, Informative)
That's where you are wrong. There is a lack of resources, funding, and computers cycles. There have been cycles running for years. I know cancer researchers, and I've donated time, money, and my computer cycles
While all research could use more funding, cancer research has to be one of the best-funded research fields out there. It's either that or defense. It lacks funding like I lack funding because I can't buy a mansion.
Could you be more specific as to what those cycles were for? I'm guessing they were for protein folding, which is essential and good research but is not going to directly find a cure. If google had run all it's computers on protein folding, we'd likely be only marginally closer to a cure for cancer.
The limiting factor in cancer research is -not- computing time. A bigger one is the fact that there are many different types of cancer, and the biggest one is that it's incredibly difficult to kill millions of any one type of cell without killing a lot of other cells in a human body. For most of our history, we had no idea how to specifically kill bacterial cells in a human body. It's still an issue.
Great job though moderators, bump up misinformation. You'd rage too if you were 34 and had to deal with this shit. And watch, I'll get marked as Troll again, even though I'm not and have a great post history. Whatever.
You're also going to get modded troll because you were asking for it. If you're 34 you should have at some point learned how to calm down and not take things so seriously.
Re:Another way of thinking about this. (Score:3, Informative)
Note that the arrangement is not fully arbitrary: there are some arrangements which it is impossible to reach. Not only of the stickers, either (everyone knew that you could make a cube unsolvable by moving the stickers around, right?): it is possible without moving any of the stickers to arrange the pieces themselves in such a way that it is impossible to reach the solved state without taking the cube apart again.
However, among reachable arrangements, your statement is valid. I suspect you probably knew that, but other people mightn’t have.
Re:Schrödinger's solution: (Score:3, Informative)
In fact, Schroedinger's cat story was meant to show that quantum physics was just a model, and particles were not really in two different states simultaneously. But most people understood it the wrong way, and now most mentions of the cat experiment promote the oposite idea of what was the initial goal.
Lower bound = upper bound (finally!) (Score:5, Informative)
Actually, this is a much more important result than the summary claims. Until now, there was always a gap between the proved lower bound and upper bound on necessary moves. They now proved that the known lower bound (20, proved in 1995) is also an upper bound (ie. there is no position which requires 21 or more moves to solve) and thus concluded research that lasted for 30 years.
This article could very well be listed on the Slashdot main page, it has nothing to do in Idle. The algorithms that were designed during this research are nothing to laugh at and will surely advance other research fields as well.