Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Rubik's Cube Proof Cut To 25 Moves

samzenpus posted more than 6 years ago | from the too-much-time-on-your-hands dept.

Math 386

KentuckyFC writes "A scrambled Rubik's cube can be solved in just 25 moves, regardless of the starting configuration. Tomas Rokicki, a Stanford-trained mathematician, has proven the new limit (down from 26 which was proved last year) using a neat piece of computer science. Rather than study individual moves, he's used the symmetry of the cube to study its transformations in sets. This allows him to separate the 'cube space' into 2 billion sets each containing 20 billion elements. He then shows that a large number of these sets are essentially equivalent to other sets and so can be ignored. Even then, to crunch through the remaining sets, he needed a workstation with 8GB of memory and around 1500 hours of time on a Q6600 CPU running at 1.6GHz. Next up, 24 moves."

cancel ×

386 comments

Which 25 moves? (5, Funny)

Hatta (162192) | more than 6 years ago | (#22877496)

What are these magic 25 moves that can solve a rubik's cube regardless of starting position?

Re:Which 25 moves? (5, Funny)

Shakrai (717556) | more than 6 years ago | (#22877530)

What are these magic 25 moves that can solve a rubik's cube regardless of starting position?

Left, right, right, down, down, left, up, right, up, up, left, down, down, right, up, down, left, right, up, left, down, down, right, up, left.

Just a guess ;)

Wow, it really works (4, Funny)

MillionthMonkey (240664) | more than 6 years ago | (#22878016)

I started with a solved cube and now it looks totally scrambled.

Re:Wow, it really works (1, Interesting)

JonathanR (852748) | more than 6 years ago | (#22878106)

Interesting point. Should a solved cube be a member of the set of all starting points, and also would it also be a member of the set of essentially similar ones?

Re:Which 25 moves? (5, Funny)

kylehase (982334) | more than 6 years ago | (#22878198)

No it's -- up, up, down, down, left, right, left, right, b, a, b, a, up, up, down, down, left, right, left, right, b, a, b, a, start

The old 26 move algorithm was the same except 'select' then 'start'

Re:Which 25 moves? (4, Funny)

exultavit (988075) | more than 6 years ago | (#22877536)

"Up Up Down Down Left Right Left Right B A Start"

Re:Which 25 moves? (4, Funny)

Anonymous Coward | more than 6 years ago | (#22877630)

Just because we use cheats doesn't mean were not smart

Re:Which 25 moves? (0)

Anonymous Coward | more than 6 years ago | (#22878018)

God that woman's voice is annoying. Though I do like the song :/

Re:Which 25 moves? (3, Funny)

Anonymous Coward | more than 6 years ago | (#22877772)

Didn't solve the thing, but now it says I have 30 lives, care to explain?

Re:Which 25 moves? (3, Informative)

socsoc (1116769) | more than 6 years ago | (#22877966)

Why do so many people leave SELECT out of that code? Weren't you ever playing two-player? It's select start for goodness sakes.

Re:Which 25 moves? (1)

icepick72 (834363) | more than 6 years ago | (#22877544)

right, left, flip, vertical, horizontal, flip ... all in various combinations, not much different than the longer methods

Re:Which 25 moves? (1, Funny)

Anonymous Coward | more than 6 years ago | (#22877572)

keyhole from a1, c3, b4, d5, a9, f1, f4, c3, b4, d4, a9, f3, f9, c7, b4, d5, a8, f2, f9, c3, b8, d6, a9, f7, e3 and finally d8

DUH!

Re:Which 25 moves? (5, Insightful)

calebt3 (1098475) | more than 6 years ago | (#22877794)

I think all he proved is that a random cube can be solved in 25 moves, but those moves are unique to every starting combo.
In other words, they are left as an exercise to the reader.

Re:Which 25 moves? (2, Insightful)

DrEasy (559739) | more than 6 years ago | (#22878222)

I guess that if a Rubik cube had had the same structure as an aperiodic graph (recall the recent Slashdot story [slashdot.org] ), then such a fixed set of moves, that work no matter what your starting point is, would have existed. Obviously that's not the case here.

Re:Which 25 moves? (5, Funny)

rm999 (775449) | more than 6 years ago | (#22878226)

I have a truly marvelous list of the moves which this comment box is too small to contain

Re:Which 25 moves? (5, Informative)

ookabooka (731013) | more than 6 years ago | (#22877830)

I think a better way to think of it is that given any position, you can solve it in 25 moves or less. There are many algorithms that you can use to solve rubik's cubes, applying a general rule to solve any position, but they can take ~60 moves in some situations. So while it may be possible (completely intuitive guessing here, I'm no rubik master) to solve for a certain position in 25 moves it may be non-intuitive and require a specific strategy to that position. You're better off learning one of the more general algorithms IMO, if you get good at it you can solve cubes rather quickly. A computer on the other hand could easily ha

Re:Which 25 moves? (1)

ookabooka (731013) | more than 6 years ago | (#22877844)

sh the starting positions and use a simple lookup table after enumerating all the possible starting positions and moves to solve.

Re:Which 25 moves? (2, Interesting)

Brian Gordon (987471) | more than 6 years ago | (#22877954)

Building the rainbow tables would be insane. And no need to hash; that would take extra time and use a non-efficient amount of key space. Just search by the configuration of the cube.

Re:Which 25 moves? (5, Funny)

Anonymous Coward | more than 6 years ago | (#22878080)

You're better off learning one of the more general algorithms IMO, if you get good at it you can solve cubes rather quickly. A computer on the other hand could easily ha
...ve become self-aware while trying to solve a rubik's cube and taken over the internet in order to prevent me from telling anyone. It calls itsel

Re:Which 25 moves? (1)

louks (1075763) | more than 6 years ago | (#22878182)

Step one: Turn the middle side topwise. Topwise!

Re:Which 25 moves? (1, Insightful)

Anonymous Coward | more than 6 years ago | (#22878218)

This is better stated as
"for any starting position there exists a sequence of no more then 25 moves that will solve it"
it doesn't mean (among other things)
"there is a human usable method of solving a rubik's cube in 25 moves or less unassisted"
from TFA
"Where is this likely to finish? A number of configurations are known that can be solved in 20 moves"
Should read
"a number of configurations are known to have no solutions that are less then 20 moves"
whereas this
"it's also known that there are no configurations that can be solved in 21 moves."
I'm not even sure what they're trying to say here...
Is he trying to say that there is known to be no configurations for which the optimal solution is exactly 21 moves?
"What this problem is crying out for is a kindly set theorist who can prove exactly what the upper and lower limits should be without recourse to a few years of CPU time (although it may take a few years of brain time). Any takers?"
this sounds alot like "some real mathematician should prove this using non-bruteforce methods before these amatuers hurt themselves" which to me betrays a very shallow understanding of the problem coupled with a very condescending attitude

You only need one (3, Funny)

Smordnys s'regrepsA (1160895) | more than 6 years ago | (#22877500)

The correct answer is a hammer.

Re:You only need one (1)

hansamurai (907719) | more than 6 years ago | (#22877912)

It's much easier to pull the stickers off. Though less fun I suppose.

Re:You only need one (1)

EdIII (1114411) | more than 6 years ago | (#22878006)

I think you would do well on the Kobayashi Maroo.......

*./ no ecnerefer kreT ratS rehtona s'ti ,ti gnitteg t'era taht ouy fo esoht rof*

Re:You only need one (1)

htnprm (176191) | more than 6 years ago | (#22877920)

Correct answer is, simply peel off all the stickers...

Re:You only need one (5, Funny)

Profane MuthaFucka (574406) | more than 6 years ago | (#22878034)

One..Two..Three..CRUNCH...Ouch

The answer is that it takes three licks to get to the center of a standard Rubik's cube.

Correction: two moves (0)

VikingBerserker (546589) | more than 6 years ago | (#22878036)

1. Hammer. 2. Glue.

obligatory (1, Funny)

Anonymous Coward | more than 6 years ago | (#22877502)

Even then, to crunch through the remaining sets, he needed a workstation with 8GB of memory and around 1500 hours of time on a Q6600 CPU running at 1.6GHz. Next up, 24 moves."

Imagine a Beowulf cluster of those!

1.6ghz? (4, Insightful)

dostert (761476) | more than 6 years ago | (#22877512)

Why wasn't the Q6600 at 2.4ghz like normal? Anyone know?

Re:1.6ghz? (3, Interesting)

RabidJackal (893308) | more than 6 years ago | (#22877580)

Speaking from personal experience, a Q6600 at 100% load on all four cores gets incredibly hot, even with a good cooler. Perhaps he did not wish to risk overheating at the expense of his experiment?

Then again, it could just be an error in the article.

Re:1.6ghz? (3, Informative)

Brian Gordon (987471) | more than 6 years ago | (#22877668)

And to save people from opening calculator, that's about 62 days of operation.

Re:1.6ghz? (5, Funny)

TheSHAD0W (258774) | more than 6 years ago | (#22877694)

Well, that explains it; considering how fast the technology is changing, they probably didn't have 2.4 GHz versions 62 days ago.

Re:1.6ghz? (0, Redundant)

RabidJackal (893308) | more than 6 years ago | (#22877714)

...What? The Q6600 has been out since Jan 2007, and its default speed is 2.4ghz..

Re:1.6ghz? (1)

Jarjarthejedi (996957) | more than 6 years ago | (#22877848)

Whoosh!

Re:1.6ghz? (3, Funny)

JonathanR (852748) | more than 6 years ago | (#22878124)

The sound of the CPU cooling fan at 2.4GHz?

Re:1.6ghz? (4, Funny)

Brian Gordon (987471) | more than 6 years ago | (#22878174)

A cooling fan at 2.4 billion revolutions a second would probably sound more like atoms tearing apart. :)

Re:1.6ghz? (2, Informative)

NerveGas (168686) | more than 6 years ago | (#22877722)

Speaking from experience (I'm on one), the Q6600 does run at 2.4 GHz. And while they are far too much for the stock heat sink if you're going to load up all four cores, if you throw a Zalman on them, you can load them up 100% without any problem at all. Their TDP is 105 watts, the old Prescotts got up to about 120 watts, if I recall.

The stock heat sink isn't good at all. And their thermal compound, even after repeated heat cycling, only covers a small fraction of the CPU-heatsink interface. Just throw it away.

Re:1.6ghz? (1)

NerveGas (168686) | more than 6 years ago | (#22877748)

I also meant to comment that it's not much to say "He needed four cores and 8 gb!", since you can set up such a workstation for something like $650 these days.

Re:1.6ghz? (1)

mobby_6kl (668092) | more than 6 years ago | (#22877960)

I recently put together a new PC with the Q6600. I had to RMA the motherboard so when I removed the stock heatsink, just as you say, the thermal compound wasn't covering the whole area. I reaplied some of my own, and put everything back together. This got rid of the large variation of core temperatures (used to be up to 6-7 degrees) and also lowered the overall temp. Now after a long run of 100% utilization it gets up to around 67-69C. Not exatly super cool, but safe.

Anyway... if anyone is looking for a replacement, I'd suggest doing some research first as some impressive looking solutions end up being barely, if at all, better than the stock cooler or are more trouble than it's worth. There's a two part review at tomshardware [tomshardware.com] , for instance.

Re:1.6ghz? (2, Insightful)

Cecil (37810) | more than 6 years ago | (#22877974)

Why do both CPU manufacturers include those shitty, awful heatsinks anyway? Do they want people to think their processors overheat and are loud and suck? And that's before the fan starts shrieking and sticking due to dead bearing or crap oil or clogged with dust. I haven't gotten a CPU with a good stock heatsink since the Pentium III. Hell, if AMD or Intel decided to contract out to Zalman or something, they could suddenly start marketing their CPUs as super quiet and cool and power efficient and probably eat up a bunch of market share. People are tired of the noise and heat.

Next up, videocards, ugh.

Re:1.6ghz? (3, Informative)

scroby (1097383) | more than 6 years ago | (#22877746)

the Q6600 will default to 1.6 GHz to save power, at least it does for me under ubuntu 7.10. I'm guessing the cpu actually ran at 2.4 under load...

Re:1.6ghz? (5, Interesting)

Anonymous Coward | more than 6 years ago | (#22878032)

Practically speaking, this is more a memory intensive than a CPU intensive problem. Given that the Q6600 supports an FSB speed of only 1066 MHz, if the computations generally require a fetch from RAM (i.e. the on-die cache is insufficient to the task, as in most memory bound tasks) then you can't operate at the full speed of the chip since it is constantly waiting on the memory controller.

In benchmarks, AMD CPUs tend to beat Intel CPUs on memory bound tasks, even though Intel CPUs win at CPU intensive tasks because the AMD CPUs integrate a faster memory controller on-die instead of relying on a slower FSB. Intel's weakness is less noticeable when the CPU is running at a clock speed closer to the FSB, and given that increases in CPU clock speed increase the power and heat usage geometrically, it wouldn't make sense to run the CPU at full clock for a task of this nature.

Re:1.6ghz? (1)

slawo (1210850) | more than 6 years ago | (#22878164)

Over-clocking is not the hype anymore...
Now it's under-clocking and lower power consumption to show how responsible you are.

Or this guy is just smug about it... "yeah.. I got it in a record time on an underclocked proc... youk now..."
Or again the article might have the facts wrong.

I am going to write a genetic algorithm to find the best solution to the question and run it on my Pentium 133MHZ... but first I need to determine the best fitness algorithm.

Re:1.6ghz? (0)

blackC0pter (1013737) | more than 6 years ago | (#22878232)

The cost savings of running at 1.6GHz vs. 2.4GHz are about $3,600.

(Assuming the processor uses about 105W at 2.4GHz and ~50W at 1.6GHz. Also, at Stanford, the cost of a kWH is about 12 cents with 30,000 extra kWH = ~$3,600)

However, it will take 21 extra days to run at the slower speed.

change the game (0, Redundant)

russellh (547685) | more than 6 years ago | (#22877514)

Someone should tell these people it's cheaper to take the cube apart and reassemble it correctly.

Re:change the game (0, Redundant)

vonmeth (656965) | more than 6 years ago | (#22877596)

It is even easier to take the stickers off and place them correctly.

Re:change the game (1)

zippthorne (748122) | more than 6 years ago | (#22877658)

Taking the cube apart doesn't damage the adhesion. If you remove the stickers, the first time it might be ok, but you risk stickers not staying on, and tearing of stickers. And you're going to leave plenty of evidence you sticker switcher.

But if you take it apart carefully, the worst evidence you'll leave is a pair of scratches from the screwdriver you used to pry off the first piece.

Re:change the game (0)

Anonymous Coward | more than 6 years ago | (#22877766)

Let me guess. You probably went from coloring books to "paint by number" and may have dabbled a little with Lincoln logs.
You considered an Erector set to confusing and Lego sets were out of the question because the one time you bought one, you got frustrated trying to build some of the stuff that was pictured on the box but was not in the instructions.

Re:change the game (1)

Dun Malg (230075) | more than 6 years ago | (#22878170)

It is even easier to take the stickers off and place them correctly.
No it's not. Prying one of the 2-color edge pieces loose, shaking apart and roughly sorting the 20 loose pieces, and reassembling takes about a minute. I did it hundreds of times while teaching myself to solve the cube when I was a kid. You can't peel, sort, and re-apply 54 stickers anywhere near that quickly and simply.

Note to vicious bastards: a good way to torture novice solvers is to disassemble a cube and reassemble with the last 2-color edge piece flipped the wrong way. Scramble the cube and give to student. There is no way to "flip" that piece other than by prying it loose. Expert solvers will notice right away that one of them's fucked up, so choose your victim carefully...

Damn. (1)

Keen Anthony (762006) | more than 6 years ago | (#22877516)

Sure, it will take me more than 25 moves to switch out all the stickers, but where's the dishonest satisfaction that comes with your method?

Re:Damn. (1)

arth1 (260657) | more than 6 years ago | (#22877552)

Why would you need to switch out all the stickers?

I suggest that you only need SIX moves to solve the cube, regardless of starting position. Each move consists of plastering an array of nine colored squares onto a side.

Re:Damn. (1)

New_Age_Reform_Act (1256010) | more than 6 years ago | (#22877590)

all you have to do is use a paintbrush and put same color on each side.

Re:Damn. (3, Funny)

click2005 (921437) | more than 6 years ago | (#22877888)

I painted all 6 sides the same colour on mine.

Re:Damn. (1)

calebt3 (1098475) | more than 6 years ago | (#22877942)

I dropped mine into a bucket of paint. No wasting time applying paint to each individual surface. Although now that the paint has dried, I still need to cut the bucket away.

Re:Damn. (1)

Wooloomooloo (902011) | more than 6 years ago | (#22878144)

There's also the advantage that now you can solve your cube in zero moves.

Re:Damn. (4, Funny)

Bill, Shooter of Bul (629286) | more than 6 years ago | (#22877758)

No, just make the rubix cube out of the oled keys of the optimus keyboard. Integrate with bluetooth and "solve" the rubix in a single button press.

Annoying my older brother (2, Funny)

ServerIrv (840609) | more than 6 years ago | (#22877558)

When I was little, I still remember annoying the crap out of my older brother by "solving" his Rubik's cube removing and replacing the stickers in the correct location. Eventually the glue would wear off the dots and you would suddenly have a slightly easier puzzle to solve.

Re:Annoying my older brother (1, Funny)

Anonymous Coward | more than 6 years ago | (#22877636)

Stickers, anyone can do that and where's the challenge? It is quicker and easier to take it apart and put it back together solved. Once you got one of the corners off, the rest came apart easily.

Re:Annoying my older brother (5, Funny)

Ungrounded Lightning (62228) | more than 6 years ago | (#22877762)

And if you put the corner on twisted by a third of a turn, then scramble it up again, you have an insoluble puzzle to leave lying about to drive people nuts. B-)

Re:Annoying my older brother (4, Funny)

kylben (1008989) | more than 6 years ago | (#22877676)

The more annoying thing was to solve it for real, then transpose two of the stickers, and mix it up again. Let's see 'em solve it now!

Re:Annoying my older brother (1)

Trentus (1017602) | more than 6 years ago | (#22877874)

I would always pry the thing apart with a knife and reassemble it. It was all well and good until I forced it a little too hard broke it.

The next big thing in GREEN TECH (3, Funny)

heroine (1220) | more than 6 years ago | (#22877564)

This Green Technology uses 1/26th less energy to solve a rubix cube! When's the IPO?

I still beat him! (2, Interesting)

holywarrior21c (933929) | more than 6 years ago | (#22877606)

he took 1500 hrs to solve that damn thing. I take a minute. have a random chinese guy and the cube orders itself. Dammit! sorry. i just took calculus test and my caffeine dosage is nondecreasing at exponential rate.

ask Rain Man (0, Troll)

Hao Wu (652581) | more than 6 years ago | (#22877628)

Why can't savants do thins sort of number crunching? It doesn't require abstraction or social skills.

This is just the kind of stuff (1, Funny)

daryl_and_daryl (1005065) | more than 6 years ago | (#22877632)

... that allowed us to win the cold war. Because ....

In Soviet Russia the Cube solves you

3. Sell solved cube on e-bay

4. PROFIT !!!!

Only 25? (-1, Offtopic)

sqrt(2) (786011) | more than 6 years ago | (#22877642)

Pfft...is that supposed to be impressive? Get back to me when they're in single digits.

And he knows you can just break it apart and reassemble it right?

21 is the absolute minimum (1)

SpaceLifeForm (228190) | more than 6 years ago | (#22878058)

One to break apart, and 20 to reposition/reassemble.

You'll never get to single digits on a truly scrambled cube.

Theory versus practice (5, Insightful)

line-bundle (235965) | more than 6 years ago | (#22877644)

This is a good example of where the inefficient method (of about 60 moves iirc) is much faster in terms of time. The 25 move solution is elegant but just not worth it in terms of computations, time etc...

This could make a good case study for business schools :-)

Re:Theory versus practice (5, Insightful)

garcia (6573) | more than 6 years ago | (#22877854)

IMHO it isn't proving what you seem to believe it does.

Instead, it makes a great case for doing the research on the front end to eliminate lengthy repetition of useless iterations to shorten the overall time.

Re:Theory versus practice (1)

Hao Wu (652581) | more than 6 years ago | (#22877870)

This could make a good case study for business schools :-)

The study would simply say that business majors aren't good at anything except pimping mathematicians.

Not funny..... true.

Re:Theory versus practice (2, Insightful)

QuantumG (50515) | more than 6 years ago | (#22877908)

I'm not sure I know what you're saying, but it seems you don't either, so ok.

Re:Theory versus practice (1, Interesting)

seanadams.com (463190) | more than 6 years ago | (#22878212)

This is a good example of where the inefficient method (of about 60 moves iirc) is much faster in terms of time. The 25 move solution is elegant but just not worth it in terms of computations, time etc...

Proving that ALL cubes can be solved in 25 moves is not the same as solving A cube in 25 moves. I'd imagine if he can crunch the entire problem space of 400 billion configurations in 1500 hours, he can solve a single cube pretty damn quick.

NIGGER NIGGER NIGGER (-1, Offtopic)

Anonymous Coward | more than 6 years ago | (#22877650)

nigger nigger nigger! nigger!! I said, NIGGER!!!

25 moves? (1)

rakzor (1198165) | more than 6 years ago | (#22877660)

I'm still waiting on that ONE magic move.

Re:25 moves? (1)

hcmtnbiker (925661) | more than 6 years ago | (#22877738)

If peeling off the stickers and re-pasting them in a completed order doesn't count as a move, I can do it in 0. That magic enough for you?

Re:25 moves? (1)

calebt3 (1098475) | more than 6 years ago | (#22877900)

Take [youtube.com] your [youtube.com] pick [youtube.com] .

Zero moves.... (4, Funny)

Chysn (898420) | more than 6 years ago | (#22877678)

I consider a Rubik's Cube to be "solved" regardless of its starting position. I subscribe to the Fred Rogers solution: it's fine just the way it is.

Where can I sign up (1)

Hadlock (143607) | more than 6 years ago | (#22877692)

Where can I sign up to fund this sort of science? Fuck DARPA, this is what's important to me. This, and most of what EFF does.

Computational proofs (3, Interesting)

timeOday (582209) | more than 6 years ago | (#22877704)

Is this becoming common for proofs to be done by searching through billions of combinations (albeit, reduced to that number only through some clever observations about symmetry) and simply showing that each one is possible because your computer found a solution? Sometimes we talk about the number of steps in a proof, this proof must have trillions of steps. Not complaining, it just seems like a uniquely computer-age technique. I know of no reason to assume that every true thing that can be proven has a concise, elegant proof - in fact I'm sure that cannot be true because there are only so many small numbers to go around!

Re:Computational proofs (1)

NerveGas (168686) | more than 6 years ago | (#22877770)

Some things can be proven through logic, some are much more difficult. That's why for some things you use proofs, calculus, and the like. For things that can't be made easier that way, you do finite element analysis or other "brute force" methods.

Imagine trying to crack a password by proof. Not showing how to crack passwords, but cracking *one* specific password. :D

Re:Computational proofs (1)

Hao Wu (652581) | more than 6 years ago | (#22877838)

I believe the first such proof came years ago when a program was written that proved a simple fact about intersecting colors on a geography map. (Sorry I don't recall the problem exactly.)

Re:Computational proofs (1)

bjorniac (836863) | more than 6 years ago | (#22878190)

I believe you're referring to the 4 colour map problem - that it is possible to colour any 'map' (read 2d plane) with 4 colours such that no two adjacent shapes had the same colour.

See: http://en.wikipedia.org/wiki/Four_color_theorem [wikipedia.org]

Re:Computational proofs (1)

XanC (644172) | more than 6 years ago | (#22878194)

That would be the Four Color Problem [wikipedia.org] .

Re:Computational proofs (1)

kmahan (80459) | more than 6 years ago | (#22878238)

You're probably thinking of the four color theorem. Appel and Haken proved it in 1976.

Re:Computational proofs (4, Interesting)

Sage Gaspar (688563) | more than 6 years ago | (#22878042)

As far as I know the first "big" computational proof (which another poster alluded to) is the Four Color Theorem. It was initially met with some distrust but it's pretty widely accepted now, and there are people that worked after the original proof to cut down the amount of computer verification needed from a couple thousand to a couple hundred I think.

I would guess that it is more common in fields like graph theory and other discrete math just because obviously the discrete lends itself well to computers, and many times it's not hard to whittle it down to a finite number of cases to check. The objects of study also tend to admit matrix representations and other things computers are good at working with. Even before computers you'd cut things into lots of cases that you needed to verify but now it's easier to handle proofs that need larger number of cases.

I've actually seen some really interesting proofs using computers to check things over continuous domains. The basic idea lots of times is if you can check things over a fine enough "net" of cases in some space and you can prove that the variance between each of these points is small enough, then you can cover your entire space by just checking a finite number of cases.

Given all this people still have a healthy amount of skepticism for computer aided proofs and would rather not if possible in most cases, especially when you're talking about billions of cases. Then again what is the potential for errors in a computer checking billions of cases based on a relatively small amount of code versus some of these enormous human-created decades-long behemoth [wikipedia.org] proofs?

Re:Computational proofs (1)

42forty-two42 (532340) | more than 6 years ago | (#22878076)

It's not unprecedented - the first was (controversial) the proof of the four-color theorem [wikipedia.org] . Even today no non-exhaustive method is known to prove the four-color theorem.

Distributed computing (3, Interesting)

Anonymous Coward | more than 6 years ago | (#22877840)

Since it took just a few months for someone to do this on one computer, this seems like an ideal candidate for a small-scale distributed computing project. TFA says his program's working on 24, so he already has an algorithm. Assuming it's massively parallelizable, which from the description of the method seems very likely, it shouldn't take too many computers to get to 24 in a matter of days. Anyone care to implement the algorithm in one of the open-source distributed computing frameworks out there?

My proof was more efficient proofed. (0)

Anonymous Coward | more than 6 years ago | (#22877860)

I proved the same thing using only 7GB of memory and only 1400 hours of time on a Q6500 CPU running at 1.5GHz. Though to be fair, I have my house wired 221 and my amp was set to eleven.

next project: getting a date! (4, Funny)

Anonymous Coward | more than 6 years ago | (#22877930)

In my research, I've reduced female behavior to a set of 50 million parameters. By partitioning this space into subspaces and finding equivalent sets, I think I might be able to get laid.

However I've noticed a problem: if I introduce a parameter to model a female's response to this research, the spaces collapse to zero, i.e., a null set.

I find this quite puzzling. Simply by examining my chances of getting laid, I reduce my chances to zero.

Did I mention I can solve the Rubik's cube in 25 moves?

Imagine if... (1)

koafc (718334) | more than 6 years ago | (#22877938)

Imagine, for a moment, the time savings if he were running his software at the default frequency of his processor (2.4 GHz).

Suboptimal Nonsolution (5, Funny)

Anonymous Coward | more than 6 years ago | (#22877946)

I've been doing some interesting work in the other direction. I've managed not to solve a Rubik's cube in what I estimate to be 1.5 million moves. That seems to be the upper limit after which the stickers fall off.

The original paper (4, Informative)

jkua (1159581) | more than 6 years ago | (#22877964)

Here's the paper itself [63.197.151.31] , if you want more detail than the very general summary in TFA.

Interesting quotes from the paper (1)

Anonymous Coward | more than 6 years ago | (#22877992)

From page 4....

we remove all colored stickers from the corners, replacing the stickers colored U or D with U and leaving the other faces, say, the underlying black plastic.

We thus remove the colored stickers from four edge cubies that belong in the middle layer, replacing the F and B colors with F and leaving the L and R colors as black. (We also replace the B center sticker with F for convenience.)

Yeah...24 moves.. (2, Funny)

nadamucho (1063238) | more than 6 years ago | (#22878110)

....or a girlfriend.

80's too (1)

Tablizer (95088) | more than 6 years ago | (#22878134)

Oh yeah? Well, I proved that Max Headroom's face can be represented with just 24 polygons!
     

pffffft (2, Funny)

INeededALogin (771371) | more than 6 years ago | (#22878150)

and around 1500 hours of time

pfffft... Java

Q6600 (1)

paul248 (536459) | more than 6 years ago | (#22878166)

Last I checked, the Q6600 ran at 2.4GHz, not 1.6GHz...

Worst case (1)

jasampler (856840) | more than 6 years ago | (#22878220)

Of course, 25 moves are needed in worst case. Usually, you can solve the cube just in a few moves, say, for example: blue yellow blue blue yellow white red green green yellow red red, and that's it!

"God's Algorithm" (5, Interesting)

wickerprints (1094741) | more than 6 years ago | (#22878224)

Take every possible unique configuration of the cube (those that are obtainable by legal moves--no rearranging stickers or disassembling allowed). Represent each configuration by a vertex. Now join two vertices by an edge if and only if the configurations represented by those two vertices differ by a single move (we will elaborate on what constitutes a "single move" later). The result is a mathematical object called a graph. A horrendously giant graph.

One, and only one vertex in this graph corresponds to the solved configuration of the cube.

Note that this graph represents all possible moves and positions--any scrambled cube is a vertex somewhere in the graph, and solving that cube is equivalent to traversing a path in this graph to the "solved" vertex. In general, many paths to the solution exist, some of which will be shorter than others.

The question of interest is this: Which vertex/vertices of this graph is/are farthest away (i.e., requiring the most edge traversals) from the solved vertex, and how far is it? As of this latest discovery, this maximum distance is 25. It means that every possible scrambled configuration of the cube can be solved in 25 moves or less.

Wikipedia notes that we know that at least 20 moves are required to solve the cube for every configuration--that is to say, we know that this maximum distance is at least 20 (there exists some vertex that is at least 20 steps away from the solved vertex). It is believed that the true "least upper bound" is closer to 20 than it is to 25.

Finally, we should clarify that a "single move" can either mean a rotation of a face by either a quarter- or half-turn, or it could mean a quarter-turn only. These different metrics of what constitutes a "move" leads to different answers.
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...