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.
I got a team working on solving Rubik's cube in 1 move.
The proof only need 30 years of computering to be proven, however as we only got one computer we won't release is before 2040 (and then we'll claim we were that close to the solution, but due to a timestamp bug we had to restart from scratch in 2038).
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?).
35 "computing years" is not the same as normal years. It's like saying 100 man hours. It can be 35 computers for 1 year, or 7 computers for 5 years.
Step 2 would be "Not die until step 3", I think.
If we're comparing things like that, then I think you better quit the internet and donate your computer/internet subscription money to cancer research. Much more useful than this comment.
It was supposed to solve it, not rearrange the stickers.
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.
They started it on an ENIAC emulator and then sped it up according to Moore's Law.
All very proper.
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.
it was probably 35 CPUs running for a Year. or 70 running for 6 months. article is BS
It pays to be obvious, especially if you have a reputation for being subtle.
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!
...But why the hell is the demo avi on the web page (cube20.org) showing the process in reverse?
Python: 'And then suddenly you have a language which says "we're all stuck with whatever the whiniest coder wants".'
Actually, I was at a high-performance physics computing conference this summer in which a genetic oncologist talked about some of the computational challenges in cancer genomics and said, basically, "There's lots of room over here if you physics folks want something else to chew on." It won't be cured by brute-force computing alone, but there are certainly computational challenges where a few million core-hours would be welcome.
Besides, manually traversing the enormous tree of possible Rubik's Cube states to get to the solution in 20 moves will make any person's life seem much, much longer!
You know, there is a difference between trolling and pointing out the flaws in your reasoning. Just saying.
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.
No no no, Brin started the computation 35 years ago on his TRS-80, then upgraded hardware as his career started taking off.
Python: 'And then suddenly you have a language which says "we're all stuck with whatever the whiniest coder wants".'
Or 1 computer for 1 day if the reference computer is an 8086. Or more likely if you are google, 12,775 computers for 1 day.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
From the article (www.cube20.org): "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."
Maybe read the article next time.
Computers are useless. They can only give you answers - Pablo Picasso
Knowing Google it was probably more like 3500 computers for 3.5 days.
1) Turn the lights off.
The cube now exists in an entangled solved/unsolved state.
Alexander Peter Kristopeit bought his basement from his mommy for one dollar.
From the old article, Posted by timothy on Friday June 06 2008:
[...], which he used it to show [...]
Who the heck is IT the inventor of that strange kind of grammar ????
The computational resources are available. If the researcher needs clock time, he can talk to the folks at TeraGrid, among others. Of course, the researcher you mentioned was doing something similar to what OP wants, although more politely and probably the "correct" way, which is to try to get people who are working on problem X to work on cancer instead. At least the oncologist was "walking the walk" in that he is actually working on his topic of interest instead of just complaining that there is no cure for cancer.
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.
Which, most likely, ends up being 140 years (as the computer has 4 cores) and not 35 but, as someone already mentioned, this sort of metric is close to meaningless.
Folding@Home
Dilbert RSS feed
Step 1: Remove the stickers.
Step 2: Reapply the stickers,
Get a small titted girlfriend. They don't wear bras.
Excuse me, but please get off my Pennisetum Clandestinum, eh!
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.
My condolences for your loss, but do you really believe that Google would have found the cure for cancer by now if only they hadn't spent time on this? Big achievements are incremental; someday we might turn this into something bigger or we'll find out it was a waste of time, but it shouldn't be hated simply for being done. How many people here would love to find a way to solve a Rubik's cube in 19 moves? Would you give them the same reaction?
I'm sure this will be difficult coming from someone on the Internet but you should focus on how the person lived, not how they died. And if cancer research is really important to you, donate time, money, emotional support, whatever you can in hopes that it helps the next person because like big achievements, big changes are incremental.
They say a little knowledge is a dangerous thing, but it's not one half so bad as a lot of ignorance. - Terry Pratchett
Exactly, but if you use 9 women you get that baby in 1 month!
Security is mostly a superstition... Avoiding danger is no safer in the long run than outright exposure. - Helen Keller
Plot the count vs. distance table on a chart and set the count to a log scale. Up to 17 it's almost perfectly linear. I wonder why that is?
-S
--- What parts of "shall make no law", "shall not be infringed", and "shall not be violated" don't you understand?
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.
I always hear about people switching stickers, so I have to ask this... has anybody else physically disassembled the cube and put it back together? It's a surprisingly fun process.
They say a little knowledge is a dangerous thing, but it's not one half so bad as a lot of ignorance. - Terry Pratchett
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!
If it's anything like when I try to solve it, then it involves hammer and tape.
Do you have a problem with the phrase 'man hours' too?
100 man hours = 1 man, 100 hours or 10 men, 10 hours or 100 men, 1 hour.
35 computer years = 1 computer, 35 years or 5 computers, 7 years or 35 computers, 1 year.
(although it's more likely 'processor hours,' but the theory still holds.)
He didn't need compute time; he was giving a talk to a bunch of physicists about something that a) they don't know much about, but would find interesting, and b) they could go work on if they get bored with quarks, and would probably bring a fresh perspective to since they have different skills.
(And, in a sense, he *did* talk to the TeraGrid folks, since some of the largest TeraGrid users were there.)
Reach around the supermodel. Gasp clasp the thumb and index finger with thumb on the inside. Snap your fingers with clasp between. Bra or Swimsuit top should spring apart followed by a giggle from your target. At this point if you have mastered this move you should be able to get her to do anything you wish, just ask.
6.8SPC TR of 550, l xwind at 6, drift rt at 26" drops 77". AT has 503 ft-lbs at 1403 fps. FT 0.86
"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.
Great, now I know I'm even WORSE at solving it than ever...
Dan
You've got a point. On the other hand, I'm constantly shocked at things like how US Cancer Research gets ~$4.81bn yearly , while I.E. the cosmetics industry, just on cosmetic products, just in the US, chew ~$41bn yearly.
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.
Sorry. US yearly spending on cosmetics is 41bn EUR. So it's more than 10 times as high as Cancer research.
Also interesting, In 2009, Colipa bragged how they spent 25mn EUR on research for finding alternatives to animal testing. 0.06% of their yearly income.
I am sure Google would of donated many many times the amount of computer cycles to curing cancer if they were asked.
I would be surprised if they really needed cycles much, it should not be hard to run some drive and get millions of people to donate their excess cycles to research.
and it really does not cost that much to buy computers, if they wanted to do it themselves.
But I do not know, it is possible no one in the cancer research field has tried very hard.
But in the end of the day it is not googles fault or anyone else if researchers have not made it a point to go looking for people to donate computers time.
Troll is not a replacement for I disagree.
Let's see... Three moves shaved off every 2 years... That means that by the year 2024, we'll be able to solve any Rubix Cube in 1 move (or less!).
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.
While I believe people should be allowed to make there own decisions regarding the risks of this kinds of treatments. I also believe that it is vital that the risks are well understood by those making the decision. My aunt died of cancer that was suspected to be related to hormone therapy... while it improved her quality of life for a time the cancer (and subsequent treatments) drastically decreased it.
I don't give a damn for a man that can only spell a word one way.
Mark Twain
"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."
Similar concept to those male sexual de-sensitizing products on the market that help improve a guy's stamina in bed. Have sex all night long and not feel a thing! What a concept!
I was taking more issue with the part of your post where you said, "there are certainly computational challenges where a few million core-hours would be welcome." Now, a few million core-hours isn't cheap, but if you have a good idea and you can sell it (to the grant agencies or someone who has a huge cluster), then getting the requisite compute time is certainly do-able. Furthermore, going back to OP's post, the researchers who did this Rubik's cube stuff were not competing for the same pool of resources as oncologists (i.e. it's not likely that Google had some cancer research they put on the back burner because finding God's Number was more pressing, and I couldn't tell who was funding this research, but it looks like it may have been a volunteer effort).
As you mentioned, the bottleneck is people. And the oncologist you mentioned was going about recruiting people in the right way, by saying something to the effect of, "here are a set of problems you have the skills to solve, you may be interested on these issues, and there is funding for you to do research in this field." That works a lot better than telling a bunch of mathematicians that they are wasting their time and that they should work on curing cancer while you are not an oncologist yourself (this is referring to OP).
Sure it is, Dr. Fruitloop.
How many moves does it take to solve Farmville?
Though I'm not sure that answer matters much to its developers either.
This result has a much greater range of interest than one might suppose. The Rubik's Cube is a physical example of a problem in group theory (a group appropriately now known as the Rubik's Cube Group : http://en.wikipedia.org/wiki/Rubik's_cube_group), and completely solving this group (and thus all simpler sub-cases) is a matter of some significant interest in pure and computational mathematics.
The Rubik's Cube Group also has a physical analog in the subatomics physics of quarks. See: Golomb, S.W., "Rubik's Cube and a Model of Quark Confinement", American Journal of Physics, Vol. 49, No. 11, pp. 1030-1031, November, 1981. Analogs can provide powerful tools for visualizing other physical systems.
Starships were meant to fly, Hands up and touch the sky - Nicky Minaj
purchase scissors
every day http://en.wikipedia.org/wiki/Special:Random
Imagine the number of clicks this has generated net-wide on various pages created to attract clicks and think of how many of those are hooked into Google's massive adware fabric.
It could be someone at Google's job to figure everything out.
You'll have to point out these lifestyle police. I've never seen them for some reason.
What a fool believes, he sees, no wise man has the power to reason away.
P.S. Be prepared for 2012.
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.
Water Fluoridation really is a waste though. It only helps kids, and they are going to lose their teeth anyways.
I can’t comment but on two of those, first being the moon landing photos, which were of course not faked (and much evidence exists to support this).
Secondly, the fluoridation of water... if you look into the studies which were done to determine whether the effect of fluoride on teeth has any correlation to the occurrence of dental caries (tooth decay), you will find that (as any good researchers should) the researchers used a control group: the cavity rate amongst children in a number of cities in which the water was not fluoridated was also recorded. The result of the study? As predicted, the cavity rate declined in the cities where the water supply was fluoridated. And the cavity rate declined by a statistically identical amount in the cities where the water supply was not fluoridated. Conclusion: Fluoride prevents cavities. Wait, what?
P.S. As I work in the drinking water industry, I happen to know that fluoride is indeed a highly toxic waste, but dilution is the solution. That, and human bodies make really good filters.
I'm sure there aren't any other applications of the technology being used here. Completely useless doing research unless it cures cancer. What a bunch of... Trolls? Let's shut down Google and enter in that Cancer Cure equation. About time that thing got solved. I just love how computers can solve everything on their own. Makes me feel so obsolete.
You have to be smarter than the machine you're working with.
.
But... but... but... google hasn't been around for 35 years....
What does Vinay Deolalikar have to say about this?
Hint: If a woman really likes her bra, destroying is is not going to go over well. Good bras are extremely expensive (upwards of $60) and well endowed girls have a hell of a time finding bras that they find both attractive and comfortable. If you ruin the bra, don't expect a 2nd date.
Science doesn't happen overnight!
It's not a waste, since the fluoride itself would otherwise be a waste product. Water fluoridation is a way of dumping chemical byproducts in a manner and proportion which is a net benefit to the recipients as well as the disposers. A true win-win scenario, at least in the average case.
"They were pure niggers." – Noam Chomsky
... and you'll live longer or at least it will feel like it.
So much truth in one sentence: "make your life a misery, you'll live every painful second of it and feel like you lived a thousand years!"
Much easier than living 55 fulfilling and happy years and dying with a smile on your face surrounded by people you love.
And for added fun, put it back together with a single edge flipped (or a single corner rotated), then jumble it up and leave it in the vicinity of a smart-arsed kid who thinks he knows how to solve it :-)
[ ]Half Empty [ ]Half Full [x]Twice as big as it needs to be
Ah, yes, you're correct: there are challenges where a bunch of compute time would be welcome, but that time is available, as you point out. (If MILC can get a billion hours over eight years to simulate quarks, someone can get a few million to do cancer research).
Cancer is already solved, it's called THC. (Well, that's what I read anyway, don't know if it's true)
Wood nymphs don't WEAR bras!
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.
I can see how this research could be helpful
I agree, lets call shenanigans.
My commodore 64 could have done it 34 years....
...is to not play.
“Common sense is not so common.” — Voltaire
that's a sad day for Tomas Rokicki and John Welborn what are they gonna work on now?
Naturally since I'm not an MD you have every right to laugh.
But considering the typical corporate trend to rake in profits and stomp all over the consumer in almost every other industry, would you be surprised if I was telling the truth?
There is a vaccine for cervical cancer, but this is Slashdot. No one here knows anything about that sort of thing.
Technically, though, it's a vaccine for a virus that happens to cause cancer. There are non-viral forms of cervical cancer that Gardasil does not prevent.
The vaccine is for HPV, which can cause cervical cancer. The vaccine is not for cervical cancer.
Slashdot's rate-of-post filter: Preventing you from posting too many great ideas at once.
Those would actually be more prevention than cure. They're not 100% effective prevention, which is why no-one calls a low-carb diet a vaccine against cancer (unless of course they're trying to sell books about their patented low-carb diet).
If you've already got cancer, it's really much too late to start limiting your radiation exposure. The other things are probably a good idea in any case but seem rather insignificant in the face of that cancer you hypothetically already have.
The standard cures for cancer at the moment would be surgery, chemo and radiotherapy. The research ongoing is into more effective means of killing cancer that include a smaller side-component of killing things that aren't cancer (it's really very easy to kill a cancerous cell, doing so without killing the patient is the challenge)
So, basically, Google could cure cancer in like, say 6 months. Or even 6 Years. But they don't. Because Big Pharma says no. What a bunch of jerks.