Slashdot Mirror
Rubik's Cube Now Solvable in 20 Moves
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.
Enough with the Rubik's cube junk, someone please tell us how to unhook a bra with *1* move.
"I'm just here to regulate funkiness."
Moves 1 through 19: repeatedly hit cube with hammer
Move 20: reassemble the smashed bits into a solved cube.
Warning: Your cube may or may not remain functional through use of this solution.
1. Allocate computer time to cancer. 2. ??? 3. Cure cancer!
I know it won't stem the tide, but this is good research. I'm sure there are a million other algorithms in the world that can benefit from this. Shortcuts they had to invent to make sure they were using minimal processing time, full understanding of how much money and time it really took to get this process done to make other projects more practical, etc etc. This sort of thinking, even if silly on its own, has a broad range of applications.
Cancer is unlikely to be cured via brute-force computing. If you've got a computational problem that would help towards a cancer cure, have you asked Google to donate time for it?
Oh, they had that for centuries.
The shortest path between any two configurations (be them solved or not) on a graph of all possibilities will be no greater than 20.
Yes, you're right, we should devote all our time to getting ourselves to live longer, and none of our time to making our lives more interesting and enjoyable. That'll make a lovely world, won't it.
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. Computer-hours are nothing line man-hours or horse-power. At least those have good limits to their vagueness. Computer-time might as well be arthropod-lengths (are we talking dust mites or ancient giant sea-scorpions?).
Step 2 would be "Not die until step 3", I think.
They give the distance and number of positions for the cube here: http://www.cube20.org/ What I don't understand is why they have only approximate number 20 moves - from the article on the link above I understand that they solved all of the 20-moves combinations so they must know the exact number of those combinations
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
These two are still running:
http://www.worldcommunitygrid.org/research/hcc1/overview.do
http://www.worldcommunitygrid.org/research/hfcc/overview.do
Thank God!
And cancer? Still unsolved. I'll bet computer time could be used for that too.
It can be shown that a cure for cancer can easily be derived from a method of solving any Rubik's cube in 19 moves.
Thank God! And cancer? Still unsolved. I'll bet computer time could be used for that too. (sorry, bullsh*t like this hits very close to home for me recently. Nothing like having people dying, and then hearing how we are using resources for utter crap)
I don't think the limiting factor in cancer research is lack of computer time. If it were something so simple, getting the resources wouldn't be a problem.
Your raging is pointless.
Does this mean that it was somebody's JOB at Google to figure this out?
The Generation
I'd say something witty here, but I'm not that bright.
If you've got a computational problem that would help towards a cancer cure, have you asked Google to donate time for it?
No, he'd rather just complain. It's much easier to criticize researchers than to do the research yourself.
Yes, you're right, we should devote all our time to getting ourselves to live longer, and none of our time to making our lives more interesting and enjoyable. That'll make a lovely world, won't it.
That's what the lifestyle police are pushing for.
Eat food that tastes like cardboard, run like rabbits, and take pills based on how long they'll help you live (never mind quality of life - e.g. so hormone therapy for women is out - can't have 1 more heart attack per hundered even if it makes life bearable for the other 99) and you'll live longer or at least it will feel like it.
Just because it CAN be done, doesn't mean it should!
I wouldn't say they're cheating, but I am a bit dissatisfied with their way of counting moves. Rotating a face by 180 degrees is not an elementary move to me. I'd like to know god's number in elementary moves.
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.
My Slashdot Journal! YAY!
Yes, you're right, we should devote all our time to getting ourselves to live longer, and none of our time to making our lives more interesting and enjoyable. That'll make a lovely world, won't it.
I agree completely. After watching so many people "live" well past their prime I'd much rather have a good life and a fast death.
They say a little knowledge is a dangerous thing, but it's not one half so bad as a lot of ignorance. - Terry Pratchett
100 man hours? Is that like 9 pregnancy months?
I've also been working on solving the Rubik's cube for 35 years. It's taken me 63,412,452,120 moves and I have one side solved and a line on another side.
:wq
Thank God! And cancer? Still unsolved. I'll bet computer time could be used for that too. (sorry, bullsh*t like this hits very close to home for me recently. Nothing like having people dying, and then hearing how we are using resources for utter crap)
Guess you should be using your spare cycles to help cure cancer. Lead by example instead of using your resources for the utter crap that is posting on slashdot!
making our lives more interesting and enjoyable
It appears that you have never watched me attempt to solve a Rubik’s cube.
Alexander Peter Kristopeit bought his basement from his mommy for one dollar.
To answer that question, you need to ask whether there is something inherently special about the “solved” state.
Or, to put it differently:
1) Begin in state A
2) Re-arrange stickers into a corresponding state X, such that state A maps directly to state X in a particular transformation system
3) Solve from state X to S (max. 20 moves)
4) Re-arrange stickers using the same transformation system in reverse, obtaining state B, which mapped to state S in that transformation system
Now, if your transformation system was consistent, you should be able to omit steps 2 and 4, going straight from A to B in 20 moves.
QED.
Alexander Peter Kristopeit bought his basement from his mommy for one dollar.
When I was about six years old, my cousin challenged me to solve a scrambled Rubik's Cube. The family figured it would keep me busy for hours.
I solved it in the fastest possible way: I pulled off every sticker and put them on the right sides.
Problem solved; it wasn't MY fault they didn't define the problem properly.
---
ECHELON is a government program to find words like bomb, jihad, plutonium, assassinate, and anarchy.
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, 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, gives a slightly lower cost.
Get out of 2names' head, Randall!
http://xkcd.com/457/
I am an ACCA student. Got a query on Accountancy/Finance? Maybe I can help!
"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.
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.
Security is mostly a superstition... Avoiding danger is no safer in the long run than outright exposure. - Helen Keller
There's a movement in health research now geared at extending what they call "healthspan" rather than just "lifespan" -- not "how long does this dude keep breathing", but "how long can we keep this dude active and happy"?
Turns out that many of the things that make people live longer also make their late years healthier. My grandfather is 94 and still travels the world with his girlfriend (a spry young 75, but he'll never see her again now that she's taken up Farmville). He got prostate cancer a few years ago (and colon cancer a few decades ago), received aggressive treatment for it, and is now cancer-free and healthy.
Old does not *have* to mean feeble. Sometimes it does, of course, and that's bad; this is why we should look at healthspan rather than lifespan.
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.
Indeed... once you pop one of the corners out with a flathead screwdriver, the rest come out pretty easily. The bad part is that after a few times doing this, the plastic becomes a bit worn and the edges won't hold the cubes in as well. It becomes patently obvious that the cube has been disassembled; a few more times and the cube starts to fall apart when turned and twisted normally. Or maybe I just got cheap models as a kid.
It's REAL science! Hemp also cures cancer and water fluoridation is really dumping toxic waste in our water supply. The moon landings were faked too because they took too many nice pictures, and the smallpox vaccine is actually made from cowpox, so there's no chance it could possibly create the same antibodies needed to kill smallpox. Also, joint pain can be cured remotely by any well-trained chiropractor.
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.
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.