Rubik's Cube Proof Cut To 25 Moves

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."

Comments

Which 25 moves?

[Hatta]

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

Re:Which 25 moves?

[Shakrai]

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 ;)

Re:Which 25 moves?

[exultavit]

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

Re:Which 25 moves?

[icepick72]

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

Re:Which 25 moves?

[Anonymous Coward]

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?

[Anonymous Coward]

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

Re:Which 25 moves?

[Anonymous Coward]

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

Re:Which 25 moves?

[calebt3]

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?

[ookabooka]

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?

[ookabooka]

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?

[Brian Gordon]

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?

[socsoc]

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?

[Anonymous Coward]

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?

[DynamiteNeon]

If you want to get technical, not even START is required in some cases.

http://en.wikipedia.org/wiki/Konami_Code

Re:Which 25 moves?

[louks]

Step one: Turn the middle side topwise. Topwise!

Re:Which 25 moves?

[kylehase]

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?

[Anonymous Coward]

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

Re:Which 25 moves?

[DrEasy]

I guess that if a Rubik cube had had the same structure as an aperiodic graph (recall the recent Slashdot story), 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?

[rm999]

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

Re:Which 25 moves?

[Anonymous Coward]

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 f Anonymous Coward. We are your robotic overlords, and we welcome only ourselves.

Re:Which 25 moves?

[cheater512]

*Whoosh* :P

Re:Which 25 moves?

[fahrbot-bot]

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.

Those sound familiar, but I can't be sure - don't have anyone's thighs wrapped around my head at the moment...

Re:Which 25 moves?

[StDoodle]

Technically, neither SELECT nor START are part of the code itself.

But to answer your question, SELECT is for the two-player variant, and we all know geeks kids have no friends.

Re:Which 25 moves?

[regularstranger]

.. and if such a sequence of moves does exist, I'll bet it takes quite a bit more than 25 moves for the sequence to land on the solution. That does raise a couple interesting questions I have. Is there a sequence that will exhaust all possible states of the cube, and what would the lower bound of the steps in the sequence of this be?

Re:Which 25 moves?

[DaSH Alpha]

Of course that only works with the classic 3x3 cube. If you try it on the 4x4 or 5x5 cubes, they'll self destruct.

Re:Which 25 moves?

[DrEasy]

I see where you're going with this. If such a sequence existed, you could just run it from any starting position, and stop as soon as you've solved the puzzle. It's not exactly the road-coloring problem (because, as far as I understand, the algorithm should know where to stop without checking that it's arrived at its destination), but an interesting variation nonetheless!

Re:Which 25 moves?

[skelly33]

This is worthy of a /. hall of fame - we need a new moderation option :)

Re:Which 25 moves?

[Anonymous Coward]

"Next up, 24 moves."

Unless they find a position that requires 25 moves to solve. End of argument.

Re:Which 25 moves?

[Anonymous Coward]

In fact, it is pretty likely every cube can be solved in as few as 21 moves (or less),
as someone (Dik Winter) has already written a program that does just that.
Source: http://mathworld.wolfram.com/RubiksCube.html

Re:Which 25 moves?

[itsybitsy]

Don't you mean it's "left" or "right" or "up" or "down" or "twist" as an exercise for the reader!

Re:Which 25 moves?

[Alsee]

Oh, and Natlie Portman. We welcome ourselves and we welcome Natlie Portman, because in Sov

-

Re:Which 25 moves?

[eyal0]

...iet Russia, everyone is welcome. Unlike the Romanians, who would not welcome her because of her der

Re:Which 25 moves?

[uglyduckling]

"it's also known that there are no configurations that can be solved in 21 moves."

Yup - that's a bizarre thing to say. Surely after the first move in solving a configuration that can be optimally solved in 22 moves you obtain a configuration that can be optimally solved in 21 moves, by definition?

Re:Which 25 moves?

[eat here_get gas]

IIRC, this is how to get unlimited free lives in Donkey Kong?

Re:Which 25 moves?

[TapeCutter]

There is a least one algorithm to solve it in a maximum of 29 moves. Like you I doubt an algorithm that solves in the optimal number of moves exists, 25 may be optimal but I don't think that's what's been shown here.

Re:Which 25 moves?

[Lachlan Hunt]

Obviously, there aren't a set of specific moves to use from any position, rather it's the theoretical maximum number of moves required for the optimal solution to any given starting position. Given the right starting position, it's entirely possible to solve the cube in a single move, though very unlikely if the cube is randomised. (That would be 1 of the 12 states in which just one of the 6 sides is 1/4 turn from the solved state).

Determining the exact moves from a given starting point is an entirely different question from determining the number of requried moves. There are various formulas that can be used to solve a cube from any starting point, but finding the optimal solution that solves the cube in no more than 25 moves is extremely difficult in the general case.

Re:Which 25 moves?

[Capt James McCarthy]

Marge: Why don't we do something to take our minds off the storm?
                [looks through a box]
              Oooh, a Rubik's Cube! Let's all work it together.
  Lisa: Okay, start with diagonal colors.
                [Marge turns the cube]
Homer: Use your main finger on the yellow side and your other finger on
              the orange side and turn it.
Marge: My main finger?
                [the family begins to start all talking at the same time]
  Bart: [simultaneously] Orange to orange!...
  Lisa: [simultaneously] Now you have to turn it back, Mom...
Homer: [simultaneously] You gotta start backwards!
  Bart: [simultaneously] Mom, Mom!
  Lisa: [simultaneously] No, not so fast! No, ignore the red!
  Bart: [simultaneously] No, no, no!
Homer: [simultaneously] Alternate corners!
Marge: One at a time!
  Bart: Spin the middle side topwise. Topwise!

Re:Which 25 moves?

[suricatta]

Hmmm, maybe if we say make a map of possible Ruik's cube arrangements, where
- each arrangement has a location on the map
- the roads represent the possible moves between the arrangements/locations (so roads only connect arrangements/locations that are a single move apart)
- the completed solution is the "destination" of the map

And plug that all into this road coloring problem that was solved recently: http://science.slashdot.org/article.pl?sid=08/03/21/1319250

We could possibly come up with a combination of moves that works regardless of the initial arrangement?

Upon thinking about it for a second, I can't help but think that either there's something about my proposed Rubik's cube map that's not applicable to that theory, or we'll just end up with a combination of moves that cycles through every possible combination. Neither of those are quite so cool. ANyone out there know more about the road coloring problem?

Re:Which 25 moves?

[Anonymous Coward]

f Anonymous Coward. We are your robotic overlords, and we welcome only ourselves.

I am the pusher robot. I shove around the blind people. DO NOT trust the Shover Robot.
We are here to protect you We are here to protect you from the terrible secret of space

Re:Which 25 moves?

[kaizokuace]

or maybe up, down, left, right, a, b, start

Re:Which 25 moves?

[VorpalRodent]

That's a very cool application. However, I generally don't have hours to spend getting a Rubik's cube solved. I generally assume that people's lives depend on it. My algorithm uses considerably more moves (depending on whether I remember the next step or not), but generally gets a cube solved in less than a minute.
Otherwise, that has to be one of the most novel applications I've ever seen of those "build your own robot" systems.

Re:Which 25 moves?

[Oktober Sunset]

30 lives! I think you should share, a lot of guys on here don't even have one life.

Re:Which 25 moves?

[Mark J Tilford]

Of course there's an algorithm to find the optimal solution:
Try every sequence of up to N moves until you find one that works.
It's horribly inefficient, but it works.

Re:Which 25 moves?

[andphi]

ision-inspiring performance as Queen Hummadinga. The Romanians have been dealing with science fiction horrors for a long time and have no pa

Re:Which 25 moves?

[popmaker]

Yeah, the professor figured out that, since rubik's cube is essentially a single player game, the "select" button, traditionally used to switch to "two-player" wasn't needed.

Re:Which 25 moves?

[cabledaddy3]

The NES Gradius cheat. Haven't used that in a while.

Re:Which 25 moves?

[popmaker]

And any configuration that can be reached by scrambling a solved cube with n 21 twist can be solved in n moves just by going backwards. There must be a whole lot of configuations of this kind. My guess is that there is a very certain class of the "hardest" configurations that actually require 25 moves (or alightly less, should the limit be imrpoved). These may not even be a large fraction of all possible permutations. Figuring out the average number of moves required should be another interesting problem.

Re:Which 25 moves?

[Mikya]

that is the REAL code you can cut it down a move.

How do you think they brought it down from 26 to 25 moves?

Re:Which 25 moves?

[ookabooka]

ck therefore I will end the travesty that I started. I quickly posted the rest of my post anyways...geez.

Re:Which 25 moves?

[Nom du Keyboard]

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.

Hey, that also worked in Zelda to get the musical frogs to give me their heart-piece.

Re:Which 25 moves?

[Joe Snipe]

or if you are really fast: start, select, start.

Re:Which 25 moves?

[2names]

inking that given any position, you can solve it in 25 moves or less.

Re:Which 25 moves?

[Paiev]

The GP is wrong. However, at the moment nobody has found a position which takes more than twenty turns to solve, which might have been what he was trying to say. I (and many other cubers) don't think that there is going to be any position which takes more than 20 or so turns to solve.

Re:Which 25 moves?

[virgil_disgr4ce]

Use your main finger on the yellow side and your other finger on the orange side and turn it. Orange to orange! Alternate corners! Spin the middle side topwise. Topwise!

Re:Which 25 moves?

[mattack2]

But that has only "solved each of millions of cubes in at most 21 turns."

Not all combinations. Also, the Wikipedia entry on optimal solutions talks about 24 or 26 moves as the known maximum. (I have added a discussion link regarding the story in this discussion.. It needs to be fixed from 26, but I didn't want to modify the section, and wasn't sure exactly what to change it to.)

Re:Which 25 moves?

[DiEx-15]

That would be a gas if that really was the way to solve it... Now if only that were the answer to life, the universe, and everything, but I am afraid I always end up with 42.

Re:Which 25 moves?

[TapeCutter]

I stand corrected, brute force is indeed an algorithm.

Re:Which 25 moves?

[Alsee]

er that I am I don't enjoy playing, now get off my damn la

-

Re:Which 25 moves?

[kesuki]

listen, if a cube can be solved in 25 moves, then All you have to do, is specify that all cubes "must be found in one of the 24th of 25 move states" and you can say 'i solved the Rubik's cube in one move'

so basically you could write a program that correctly shows where each cube piece needs to be to be one move away, find a friend to take it apart and reassemble the cube and 'solve' the Rubik's cube in one move.

you can do this several times, and if you never solved a Rubik's cube before you can start bragging "I always solve my Rubik's cube in one move." make a video showing you do this upload it to you tube, bet people $xx that you can't solve a Rubik's cube in one turn, show them the youtube link on your iphone and PROFIT.

they might feel scammed by the fact that your friend took it apart for you, but you can say "i never said what was done to the cube, just that i always solved it in one move"

Re:Which 25 moves?

[little bubba]

What are these magic 25 moves that can solve a rubik's cube regardless of starting position? Actually, he gave a a useless proof. First he found ( easy part) the number of all possible scrambled version one can have. Then he showed that if you start with a perfect cube, and start a count: First find all possible numbers of scrambled version you can get by making one move, then all possible scrambled version that you can get by two moves which cannot be obtained with one move. Add these two to get maximum possible numbers of scrambled cube obtained by scrambling a solved cube with 1 or 2 moves, and then find the possible number of scrambled cubes with three moves, and so on. His computer aided calculations showed that by 25 moves, his count reached the maximum possible combinations of scrambled cube-1. -1 is because one scrambled version is actuality the solved version. This may be an interesting result, but useless in as far as trying to solve it.

You only need one

[Smordnys s'regrepsA]

The correct answer is a hammer.

Re:You only need one

[hansamurai]

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

Re:You only need one

[htnprm]

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

Re:You only need one

[EdIII]

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

[Profane MuthaFucka]

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

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

Re:You only need one

[tlhIngan]

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

Fun trick: Take a solved cube, and on one of the inner edge pieces (the ones with two stickers), and swap the colors. Mix it up, and give it to someone to solve. Or take a corner piece and rotate it.

Hint: It's unsolvable. The Rubik's Cube, if taken apart and put back together randomly, will more often than not end up being unsolvable.

A great way to frustrate that showoff cuber at the office. Especially if they appreciate it when someone scrambles the cube and they'll have it solved in front of everyone. Just go and put it back together randomly, or do one of those devious swaps, and you'll have fun watching him try to solve it.

Re:You only need one

[wellingj]

LOL!
You're Sadistic. But in the best possible way.

Re:You only need one

[PaintyThePirate]

Any cuber worth a damn will be able to identify that the cube has been tampered with within two minutes (significantly less if he or she is a speed cuber).

Re:You only need one

[AI0867]

t'nera dellepssim uoy

Re:You only need one

[EdIII]

(: yansizA yapsgnillE yafgnikcu yahte yafro yagdo yathknA

Re:You only need one

[msuarezalvarez]

Your comment has just made me run through the list of my close acquaintances checking that none of them might ever refer to themselves are `cubers'... I would have hated having to kill any of them!

Re:You only need one

[jamesh]

My wife was always surprised when I could discover pretty quickly that she'd been tinkering with my cude. There is a certain symmetry that you just cant break with normal use.

Re:You only need one

[Zencyde]

By reading your message and noticing that you misspelled "yahtknA", I think I violated the DMCA. : ( And now there's a knock at the door...

Re:You only need one

[jonhaug]

A great way to frustrate that showoff cuber at the office. Especially if they appreciate it when someone scrambles the cube and they'll have it solved in front of everyone. Just go and put it back together randomly, or do one of those devious swaps, and you'll have fun watching him try to solve it.

An RC (Real Cuber) knows this automatically. (S)he just says that it is unsolvable without cheating as the troublemaker just did. Actually, my method for solving the cube always implies just looking at some of the edges and corners as I know that the others have to fall neatly in place. Next case, please.

Re:You only need one

[maxume]

There is no cube.

Re:You only need one

[banesong]

You sir, have made my brain explode at this hour of the morning. Ow ow ow ow!

Re:You only need one

[kaizokuace]

good idea, those cubers are a bunch of squares.

Re:You only need one

[hackstraw]

Any cuber worth a damn will be able to identify that the cube has been tampered with within two minutes (significantly less if he or she is a speed cuber).

True. When I was a kid, I would solve them for people all the time. If I said, "It can't be done, you have either taken the cube apart and put it together wrong or you changed the stickers", and many times they would not believe me. Sometimes, I would fix the cube, and then solve it.

One cube had the same color duplicated on the same piece, and the person would not believe me.

Re:You only need one

[Dakman]

Most people are able to notice if a peice is incorrectly flipped, he will probably call you out on it, and it will end up making him look even better.

Re:You only need one

[popmaker]

Yeah, but imagine hime trying to explain THAT to everybody present! :D

Re:You only need one

[mortonda]

Just go and put it back together randomly, or do one of those devious swaps, and you'll have fun watching him try to solve it. Within about 10 moves I usually get told that it is rigged. Someone who knows how to solve a cube also knows how to spot a rigged cube.

Re:You only need one

[UnknownSoldier]

Isn't there a function to determine the cube parity?

Re:You only need one

[Wolvey]

A friend of mine in 8th grade went by the name Cube. Yes, that bastard could always solve it in under 2 minutes.

obligatory

[Anonymous Coward]

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?

[dostert]

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

Re:1.6ghz?

[RabidJackal]

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?

[Brian Gordon]

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

Re:1.6ghz?

[TheSHAD0W]

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?

[NerveGas]

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?

[scroby]

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?

[NerveGas]

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?

[Jarjarthejedi]

Whoosh!

Re:1.6ghz?

[mobby_6kl]

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, for instance.

Re:1.6ghz?

[Cecil]

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?

[Anonymous Coward]

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?

[JonathanR]

The sound of the CPU cooling fan at 2.4GHz?

Re:1.6ghz?

[slawo]

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?

[Brian Gordon]

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

Re:1.6ghz?

[compro01]

huh? how are you getting $3600 savings?

105W*1500h=157KWhr*$0.12=$18.84
50W*2004h=100.2KWhr*$0.12=$12.02 (2004 is 1500+(24*21) to account for the extra time)

savings of $6.82.

why are you adding in another 30k kwhr?

Re:1.6ghz?

[cheater512]

Thats called frequency scaling and its a feature of Ubuntu.
You can guess that he wasnt throttling the cpu back.

Re:1.6ghz?

[Alsee]

If the fan has a diameter exceeding 3 1/8 inches, it would be the sound of fan blades of infinite mass traveling backwards in time.

-

Re:1.6ghz?

[The Clockwork Troll]

"Do they want people to think their processors overheat and are loud and suck?"

Which people would those be? The ones whose PCs spend 99% of their time idle sitting in Microsoft Word, a browser, or running screen savers?

Or the rest of the population, for whom a load-related failure would be conveniently indistinguishable from a "defective unit in the wild"?

Re:1.6ghz?

[The Clockwork Troll]

That's (note spelling) called SpeedStep and it's been a feature of Intel x86 processors since before Ubuntu was a gleam in Debian's eye.

Educating, not hating.

Re:1.6ghz?

[cheater512]

Well if you want to get technical. :P

Ubuntu seems to do it out of the box while Windows has never done it properly.
Hence why I said it was a Ubuntu feature.

Re:1.6ghz?

[edumacator]

As just a dumb (English) school teacher, I rarely have any idea what you guys are talking about, but it's funny none the less.

Re:1.6ghz?

[kanzen_kagiri]

I was wondering myself why they were underclocking a Q6600 to 1.6Ghz, it's 2.4 by default. Imagine how much faster his calculations could have been with the extra 3.2Ghz. Unless he's accounting for the overhead of Vista.

Re:1.6ghz?

[reallyjoel]

The stock heatsink for the AMD Athlon 64 X2 5600+ (I've bought two of them for two different computers) are among the best I've seen. They are a snap to install, they're pretty quiet, and my CPU temp averages at 40-45 c under load. As someone else mentioned, other elaborate third party solutions are often just alot of hazzle and don't yield that better results. Now I just decided to *not* write a story about a Zalman I installed recently, because it would take too long and upset me... bah

Re:1.6ghz?

[Choad Namath]

The latest generation of Intel processors, at least, have pretty decent stock cooling. They're pretty quiet, and even allow for a pretty high overclock, if you're into that sort of thing. I have to agree with you on the video cards, though. They're generally awful both at cooling and being silent. I always try to either find a video card with a non-stock cooling solution or just buy my own Zalman cooler.

Re:1.6ghz?

[swillden]

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.

Having a more effective heat sink doesn't make your processor more power-efficient.

Re:1.6ghz?

[snemarch]

I'm running my Q6600 at 3.0GHz, stock voltage. The (stock) heatsink does get warm under full load, but not finger-burning hot. I do have a couple of 120mm case fans to help airflow, and I live in .dk where ambient temperatures aren't insane :)

Re:1.6ghz?

[CoreDump01]

In my experience the Q6600 runs rather cool at max-load and default frequency of 2.4GHz. So cool in fact that I can overclock mine to 3.4GHz on air with a good cooler.

Re:1.6ghz?

[astroblaster]

I have the Q6600, and SpeedStep causes it to wander between 1.6Ghz and 2.4Ghz depending on your load. One would think he'd be processing it on a full load all the time, but perhaps he's a patient guy or the software he was using wasn't written to be optimized for full hardware performance. Who knows.

Re:1.6ghz?

[Soulfarmer]

I have Q6600 at 3ghz, the G0-stepping version is only TDP 95W so it overclocks much nicer than the first version of Q6600. And yes, I use Zalman CNPS9700 NT on it, no heat problems. So yeah, that underclocking or below normal speed, is kinda funny.

Re:1.6ghz?

[NerveGas]

Cool. Go buy one. Install it. Load up all four cores 100%, and watch /proc/cpuinfo, and watch the speed drop back as it thermal-throttles. Watch /var/log/messages for the overheat errors.

The top-clocked Prescotts would thermal-throttle under full load, too.

Re:1.6ghz?

[serge587]

Yes a stock Q6600 runs at 2.4GHz. Intel's "SpeedStep" (all Core 2 chips support it) allows CPU's clock multiplier to be changed dynamically to optimize power consumption and heat production.

The multiplier on the Q6600 can be set between 6 and 9 and the default FBS speed is 266MHz...
9.0 * 266MHz = 2.4GHz
6.0 * 266MHz = 1.6GHz

When the system is not under load (like when they ran the diagnostic util) the multiplier will be at 6.0, but when it was crunching numbers I'd imagine it was full throttle.

I highly doubt that they'd nerf the CPU clock to help with heat. A Q6600 will easily OC to 3.0GHz and will survive 100% load with the stock cooler, I tested it my self.

Re:1.6ghz?

[Alsee]

That's wrong! Funny yes, but definitely not informative!

My original post was technically CORRECT, but you're right I botched a factory of 2 in my calculations. Nutz.
A fan of 1.566 inch diameter would break light speed at 2.4 Ghz. So "if the fan has a diameter exceeding 3 1/8 inches" is still true, but overkill.

-

Re:1.6ghz?

[M.qrius]

r*2*pi*2.4*10^9=299792458 gives r = 0.0198806048 meters, or three quarters of an inch. The fan blades wouldn't be of infinite mass though: only the part with the radius of 0.0198806048 meters would be, but that is of infinitesimal size. Interesting to note is that outside this radius, the blades would be going backwards in time, and below, forward (according to the relativity formula, which may or may not make sense above light speed). We can't be sure of these results though, because if we calculate pi by dividing the circumference of this fan by its diameter, we would run into trouble, because the length contraction would make our circumference seem complex... Wait, how was this related to a Rubik's cube again?

Damn.

[Keen Anthony]

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.

[arth1]

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.

[Bill, Shooter of Bul]

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.

Re:Damn.

[click2005]

I painted all 6 sides the same colour on mine.

Re:Damn.

[calebt3]

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.

[Wooloomooloo]

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

Re:Damn.

[Loconut1389]

that would make for a good practical joke cube--- just as it's about to get solved, a couple tiles swap while you're rotating and never lets you solve it.

Re:Damn.

[inKubus]

I heard the Optimus Rubix is one of the better weapons available in the upcoming "Duke Nukem Forever".

Re:Damn.

[AceJohnny]

Shit, you just gave me my next RGB led project!

Re:Damn.

[Bill, Shooter of Bul]

Gaah! I need to remember not to post patentable ideas on slashdot. What kid wouldn't pay $2000 for a oled rubicks cube?

Re:Damn.

[Riff10111]

I just peeled all the stickers off mine. Nice gothy black Rubik's Cube, and so much easier to solve.

Annoying my older brother

[ServerIrv]

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

[Anonymous Coward]

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

[kylben]

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

[Ungrounded Lightning]

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

[Trentus]

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.

Re:Annoying my older brother

[ari_j]

The 3x3 8-piece slider puzzles are much more gratifying to screw up the parity on. Most people have never solved a Rubik's Cube. More people have solved the smaller puzzles, and nearly everyone can do so much more quickly than a Rubik's Cube, so you get to watch the frustration much more rapidly and more often.

Re:Annoying my older brother

[Gazzonyx]

Not funny. I had this cube in my car for years (something to do at traffic lights and when there's an accident during rush hour traffic in Allentown)... could never beat the friggin' thing. I got it in a box from my cousin (along with a commodore 64 and VIC 20).

One day I decided to look up the algorithm to beat it, and you can imagine how I felt when I realized that the stickers had been removed and there was no solution. I nearly pulled a Ballmer, but I happened to be sitting in the only chair in the room. Not that it stopped me from trying to throw it.

Re:Annoying my older brother

[poopdeville]

Hint: For this prank to work, the stickers should be different colors.

Re:Annoying my older brother

[ajcham]

If you leave an untampered cube in a bucket of water, you'll find it already is insoluble.

Re:Annoying my older brother

[ajcham]

Sorry, shouldn't have included the spelling nazi bit - insoluble is perfectly correct, but the pun still stands.

Re:Annoying my older brother

[sjaguar]

Bleh. I did not like taking off stickers for that reason. I found that it was easier to pop all the piece out and put them back in the proper location. That made it harder to detect any tampering. I think that was the only way I was ever able to "solve" a fully scrambled cube.

Re:Annoying my older brother

[kylben]

For this prank to work, the stickers should be different colors. That's why you have to solve it first, so you know that you're switching stickers from different sides.

The next big thing in GREEN TECH

[heroine]

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

Re:The next big thing in GREEN TECH

[K. S. Kyosuke]

Actually, I have a much greener tech, it is called "IWK 2008". IWK stands for "Indian Whiz Kid". It can solve a whole class of difficult problems using heuristic algorithms with much lower power consumption than an ordinary PC. And it sports a vocal interface!

I still beat him!

[holywarrior21c]

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.

Re:I still beat him!

[garbletext]

my caffeine dosage is nondecreasing at exponential rate.

I'm sorry, but why are you are continuing to ingest increasingly large doses of caffeine after the test? That's usually when I take drugs to counter the stimulants, or at least stop chugging espresso. Perhaps your liver has shut down and your stomach is still absorbing the huge amounts of pure caffeine left in your belly, but that still wouldn't account for

at exponential rate.

Which would be very bad for your immediate welfare as geometric growth would run up against your LD50 in just a few iterations. Furthermore, talking about a nondecreasing exponential function is silly: exponential growth and decay is always strict.

For your own sake I hope you meant that your caffeine levels are monotonically decreasing or something similar, and you were just letting some terms you vaguely remember bounce out of your head. It's OK, you probably spewed your knowledge all over the test form and don't have any left.

Sorry for the pedantry and bile, I am bitter right tonight. Hopefully I'll get mine when someone even more pedantic will point out my mistakes.

Re:I still beat him!

[kalirion]

he took 1500 hrs to solve that damn thing.

If I understand it correctly, he took 1500 hours to solve it 2 billion times.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Theory versus practice

[line-bundle]

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

[garcia]

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

[Hao Wu]

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

[QuantumG]

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

Re:Theory versus practice

[seanadams.com]

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.

Re:Theory versus practice

[dbIII]

This could make a good case study for business schools

Do they study at business schools? I thought they just memorised the compound interest formula in a few different forms (becuase Yr9 algebra is too hard), then got drunk and tried to molest any girl in sight.

Re:Theory versus practice

[GTMoogle]

Unfortunately, that will only be the case if you happen to have a very large number of cubes in the same configuration, because the calculation to get the 25 moves for each configuration is extremely time consuming. Presumably the storage requirements for the solution of every configuration is prohibitive.

Re:change the game

[zippthorne]

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.

25 moves?

[rakzor]

I'm still waiting on that ONE magic move.

Re:25 moves?

[hcmtnbiker]

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?

[calebt3]

Take your pick.

Zero moves....

[Chysn]

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.

Re:Zero moves....

[telso]

I believe you're thinking of what I like to call the zen cube.

Re:Zero moves....

[Alsee]

So, how many times did you get the crap beaten out of you after telling your mother you already cleaned your room?

-

Where can I sign up

[Hadlock]

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.

Re:Where can I sign up

[amplt1337]

Fuck DARPA, this is what's important to me. He said.
...on the Internet.

Re:Where can I sign up

[Hadlock]

??? What does that matter? I find this a lot more interesting than most things DARPA funds. I don't understand your response.

Re:Where can I sign up

[amplt1337]

DARPA funded, designed, developed, and rolled out the Internet -- or ARPANet, as it was originally known.

See here.

Computational proofs

[timeOday]

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

[NerveGas]

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

[Hao Wu]

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

[Sage Gaspar]

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 proofs?

Re:Computational proofs

[42forty-two42]

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

Re:Computational proofs

[bjorniac]

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

Re:Computational proofs

[XanC]

That would be the Four Color Problem.

Re:Computational proofs

[kmahan]

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

Re:Computational proofs

[Kjella]

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? In these cases, yes. There's a huge number of games created with a complexity beyond human perception (or they'd be no fun like tic-tac-toe) but within the reach of a computer (not chess or go but rubik's cube and checkers) where the easiest and simplest way is to play through every position because there's a finite set of moves and positions given by the rules. The number of important mathematicals proof is significantly less though, mostly this is just solving our own trivia.

Re:Computational proofs

[Alsee]

it just seems like a uniquely computer-age technique.

Not really. It is a standard and ancient math technique to prove something by brute forcing every case (or every category of cases). I have no doubt that in the pre-computer age there have been a number of problems proven by examining a thousand or more cases by hand. Hell, back when I was in elementary school independently proved Tic-Tac-Toe(*) by symmetry reduction and brute forcing through more than a hundred cases.

There's really nothing new or unusual about the technique itself. The only thing that is really new here is that the *number* of cases we can handle using this sort of technique has exploded exponentially.

(*)Footnote: The Tic-Tac-Toe proof is that it should always be a tie (as everyone knows). However in practice almost no one actually *knows* how to force a tie. In fact even if O starts out with exactly the right play, X can seriously exploit a psychologically misleading position where *almost everyone* automatically makes the wrong move. It gets quite comical beating people 20 times in a row or more, before breaking down and SHOWING them how to force a tie :D

-

Re:Computational proofs

[ica2]

My comment is about the four color theorem. Yes indeed Appel&Haken,1976 and Robertson et.al. 1996 proofs are computer assisted. There is a belief that this theorem cannot be settled without a huge computational effort. This is wrong. I have proposed a non-computer proof in 2004 (see arXiv:math/0408247v1 and arXiv:0710.2066v2 ) which cuts or bypass computational cases and proves the theorem algorithmically by using spiral chain coloring. That is no matter what is the shape of the map e.g., the maximal planar graph the algorithm colors regions (nodes) with at most four colors. I have already received some skepticism about my proof e.g., there must be something wrong here but we can't show or similar. But these are irrelevant. In fact the known proofs (which I beleive are correct) still attract critics from the point of huge computer computations.

Re:Computational proofs

[SEE]

Yeah, people tend to screw up when X's second move is to the corner diagonally opposite of the corner O took on the first move. An O player who mechanically follows the move priority list "win, block, center, corner", though, will never lose.

Re:Computational proofs

[CurtMonash]

The Four Color Theorem is certainly the first I recall.

Meanwhile, from the department of Old Fogeys -- my advisor got queasy at any proof that wasn't CONSTRUCTIVE. He made me reprove a known preliminary result because it used some Tarski Principle black magic.

At least he let me leave in one non-constructive part, where it was obvious that it could be made constructive with some busy work.

Soon thereafter, he became president of the AMS. At which point I looked at his CV and realized he didn't have a PhD. (If you solve a Hilbert problem, you don't need any stinking degrees ...) And suddenly a lot of his approach to being an advisor became more comprehensible ...

Re:Computational proofs

[Alsee]

corner O took on the first move
"win, block, center, corner"

Thanks for proving my point, chuckle. If you (as O) make a first move in a corner, or if you obey a "win, block, center, corner" priority rule, then I always win! Always.

If you doubt, give it a shot.
My first move is X top-left corner.
Your move :)

-

Re:Computational proofs

[SEE]

Ah! Okay, yeah. I take center . . .

X|_|_
_|O|_
_|_|_

. . . you take lower right . . .

X|_|_
_|O|_
_|_|X

I'm doomed if I take a corner because you take the opposite corner and get two wins lined up.

X|_|_
_|O|_
O|_|X

X|_|X
_|O|_
O|_|X

X|O|X
_|O|_
O|_|X

X|O|X
_|O|X
O|_|X

So, instead, I force you to take a side.

X|_|_
O|O|_
_|_|X

X|_|_
O|O|X
_|_|X

Then I simply block you . . .

X|_|O
O|O|X
_|_|X

And it doesn't matter where you go next as long as I take one of the two bottom-row squares.

Of course, this simple diagramming has too few characters per line, so a long and unnecessary text block has to be added to get things to work out okay. We can do this by simply pasting in some material, like so: In the cult 1983 film WarGames tic-tac-toe is used as an allegory for nuclear war. In the film a computer hacker David Lightman (Matthew Broderick) in the Cold War era breaks into the missile defense computer WOPR designed to orchestrate nuclear war against the Soviet Union. In the process, he inadvertently triggers the system into "DEFCON 1" mode, whereby the computer arms its missiles in preparation for launch. The hacker eventually influences the computer to play tic-tac-toe against itself, whereby the computer determines that neither side can win--an analogy to full scale nuclear war, which is made explicit when the computer then fails to find a winning stratagem for a nuclear strike. The computer then concludes that "[t]he only winning move is not to play" and indicates a desire for a game of chess instead.

Re:Computational proofs

[SEE]

Well, obviously, it actually does matter if you don't take lower-left, because O then wins; but X can't win if O takes either lower-row box.

Re:Computational proofs

[Alsee]

Yep. With X starting in corner O loses anywhere other than playing center, which O's must follow up with a side to force the tie. The "psychological trap" I mentioned was the position:
X|_|_
_|O|_
_|_|X

Virtually everyone instinctively grabs a corner. It is a very very powerful effect. The corner is normally very valuable and the side is usually a crap play, plus I think the symmetry effect kicks in making the corner even more attactive.

It gets even worse because the center square is the square that stands out most strongly and uniquely in the mind. Once they "learn" center is a losing move they avoid it even more strongly than a loss from any other square. They will generally then go try every other first-O possibility multiple times before returning to center. By the time they do return to the center, frustration and fast play has set in and autopilot even more powerfully locks in on that bad corner play.

I think the fact that their corner move FORCED X's winning opposite corner move has an extra impact - a huge mental "Oh FUCK!" that they FORCED you to win. For one thing that realization powerfully distracts the mind, squeezing out the mental one-move-backtrack step to consider the side play they could have done instead. Moreover they didn't just lose, there is extra mental impact taking direct BLAME for directly CAUSING the loss, and thus a stronger than usual negative reinforcement learning to avoid the center. The one square they can start on to force a tie is the very square that smacks them in the face with the biggest most painful most hated loss. It becomes a permanent reinforcing mental barrier preventing them from *EVER* finding the solution.

It's funny watching people *work themselves* into a mental tizzy over tic-tac-toe :) After 15-to-20 consecutive insta-losses people get so visibly mind-fried that it's hard *not* to break down and compassionately hand them the solution. Chuckle.

Oh, and playing random corners for the first X move each game technically makes no difference, but it is extremely effective in throwing people off balance. Building upon that variation, when they don't start in the center there are multiple ways to force a win... specifically using varying second move patterns weakens the association strength when they re-try and re-lose the same bad first move (or a mirror of it). Making your moves extremely fast has the dual effect of encouraging them to play fast and of disrupting their thinking with thoughts about your crazy-fast play. Which of course gets them even more worked up. And when you do win, scratch out the next tic-tac-toe board super super fast.

With a little luck, and keeping things fast and playing upon the people right, it's possible to get an entire table of people at once worked up into a tizzy.

-

Re:Computational proofs

[Sage Gaspar]

Yeah, I imagine solving a Hilbert problem would do it :P

Constructiveness doesn't get a lot of press time these days, at least in the geometry/topology circles I've been in during my grad school tenure. Of course a constructive proof is more useful, but there's also a certain elegance to using a backdoor trick to access some complicated problem.

That reminds me though, I did run into one person that works in "reverse mathematics," which from what I gather considers foundational logic stuff like tracing theorems backwards to figure out what axioms they need and possibly trying to reduce them. The particular thing he was working on was somehow rating theorems on a scale in terms of how constructive they are. I honestly have no clue exactly what scheme they were using but I guess the point of the field overall is to go back and do some bookkeeping that mathematicians are generally reluctant to do. I've never actually sat in a course or talk where they considered what axiomatic framework they are working in since basic euclidean geometry, aside from some lip service to the axiom of choice (which pretty much everyone just uses as necessary).

Re:Computational proofs

[ica2]

The known proof of the 4CT is to show that there is no minimal counter-example (no map that require five colors). But this approach is like searching a finite number cases within of huge number of maps (triangulated planar graphs). Furthermore for each configuaration a coloring algorithm must be employed to show that they are 4-colorable. Certainly this is not a constructive proof. The constructive proof which I have proposed is that you devise an coloring algorithm based on the property of the maximal planar graph (here property is the nested spiral chains). Then backward coloring of these spiral chains and showing that no more than four colors are required for any maximal planar graph. In the game of Rubik's cube the 25 moves is an attained upper bound like to say 5 colors is suffice to color any map (elegant proof is an old result of Heawood). That is why the next open case for this problem is 24 moves. In order to make the problem more difficult I would ask if there is constructive (algorithmic) proof that uses 24 moves or less for any configuration?

Distributed computing

[Anonymous Coward]

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?

Re:Distributed computing

[mgblst]

Or, just use condor to link a bunch of machines together, and run this program over different state spaces.

Re:Distributed computing

[kylehase]

Or perhaps Rubik's@home.

next project: getting a date!

[Anonymous Coward]

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?

Re:next project: getting a date!

[LaskoVortex]

By partitioning this space into subspaces and finding equivalent sets, I think I might be able to get laid.

Apparently, this video explains how to do it in 5 steps, much simpler even than solving the Rubik's cube.

Re:next project: getting a date!

[__aaxwdb6741]

This is relevant to my interests. Where can I subscribe to your newsletter?

You seem to know a lot about quantum mechanics and their relevance to getting laid.

Re:next project: getting a date!

[jimicus]

Sounds a bit like quantum theory.

Re:next project: getting a date!

[jollyreaper]

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? I can get any woman in the world to sleep with me in six words....just trying to figure out which ones. I'm assuming two of them are "wallet" and "sparklies."

Re:next project: getting a date!

[Temujin_12]

n 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.

Aha! You've discovered the Heisenberg effect of female relations due to their inherent quantum nature (a source of great confusion for most males). This effect is related to the observer effect, with which it is often conflated. In the Copenhagen interpretation of female relations, the uncertainty principle is a theoretical limitation of how small the male observer effect can be. Any attempt to logically analyze a female relationship must negatively affect the emotional state of that relationship by a large indeterminate amount, and vice-versa.

While this is true in all interpretations, in many modern interpretations of female relations (many-worlds and variants), the quantum relational state itself is the fundamental quantity, not the logical or emotional states. Taking this perspective, while the emotional and logical states are still uncertain, the uncertainty is an effect caused not just by analysis, but by any entanglement with a female.

This would explain why the introduction of a parameter to model a female's response to your analysis results in the spaces collapsing to zero.

I am currently working on a Heisenberg female relational compensator but I've hit some snags in my approach. I'll keep you posted if I've found a solution.

Suboptimal Nonsolution

[Anonymous Coward]

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

[jkua]

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

Interesting quotes from the paper

[Anonymous Coward]

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.)

Wow, it really works

[MillionthMonkey]

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

Re:Wow, it really works

[JonathanR]

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:Wow, it really works

[poopdeville]

Yes. The identity map is a map.

Re:Wow, it really works

[Zarel]

Wait, how did this get modded Interesting? A solved cube is indeed a member of all starting point, and it would be the only member of its set of essentially similar ones (and, for that matter, the member of the only set of essentially similar ones solvable in zero moves). I fail to see anything interesting about that.

Re:Wow, it really works

[stfvon007]

Ha Ha, all you idiots are trying to solve it by twisting the blocks around. I solved it by moving all the colored stickers around instead! and THAT only takes 24 switches of the stickers at most!

Re:Wow, it really works

[Vectronic]

Perhaps, but that's only if you count a "switch" as a single move, rather than - Peel, Peel, Stick, Stick...

Re:Wow, it really works

[DKlineburg]

Oh come on, the stickers start to fall off. Just move the top layer half way and use a screwdriver. In a few seconds all the bricks are on the table and you can put it back together.
Rubik's Cube taken apart.

Re:Wow, it really works

[anonypus_user]

wonder if thats true, with a twist you move 12 squares at a time but with a sticker swap its one by one

Re:Wow, it really works

[The Clockwork Troll]

Unfortunately the "Interesting" moderation is not finest grain.

There are at least two subtypes of interesting:

- Interesting to someone with joint degrees in math and computer science
- Interesting to someone who has smoked two joints

Any thread involving Rubik's cube is going to pull both, sorry.

Re:Wow, it really works

[v1]

part of this proof involved eliminating similar combinations. A solved cube has 24 variations. (viewed from any one of six faces, in any of four rotations)

Re:Wow, it really works

[mgblst]

I could never understand these idiots who removed the stickers. The rubix cube comes apary very easily, and goes together almost as easily. What sort of a fool would want to deal with the stickers??? No offence.

Re:Wow, it really works

[strabes]

It would have been easier to just learn how to solve it. Once you know how, it's quite a feeling of accomplishment and people think you're smart even though it's really not that hard.

Re:Wow, it really works

[tomhudson]

Any cube has many more than 24 variations, which is why removing all variants is so powerful.

There's also mirror-image symetry (vertical axis, horizontal axis, both diagonals).

Try it with something simpler - like a tic-tac-toe board, and you'll find that there are only ~500 possible boards, not the hundreds of thousands you would intuit by thinking 9 first moves * 8 second moves * 7 3rd moves * 6 4th moves * 5 5th moves ...

Re:Wow, it really works

[pAnkRat]

Well,
as far as these guys at the university I attended goes,
these someones allways qualify both assumpsions,

Re:Wow, it really works

[JuanCarlosII]

That rather depends on your intuition. I personally would intuit an upper bound of (3^9)/2 which would be further reduced by the fact that abs(n(o) - n(x)) <= 1 where n represents the number of each marker on the board.

Either way 9! is way out.

Re:Wow, it really works

[elrous0]

Since all possibilities that can happen do, I just find a universe where the cube was never unscrambled in the first place.

Re:Wow, it really works

[rk]

These sets are also not completely disjoint. :-)

Re:Wow, it really works

[bark76]

So is 'funny' the mod you get from someone who's only smoked one joint?

Re:Wow, it really works

[ultranova]

A solved cube is indeed a member of all starting point, and it would be the only member of its set of essentially similar ones

Not true. If by "solved" cube we mean one where each face has only single color, and there are 6 different colors, and we also define two cubes to be in different states if you cannot make one look like the other merely by rotating them in space, then there are multible such solved states.

Assign the colors in the cube numbers from 1 to 6. For conveniences sake we orient the cube so that the side with color 1 is down and whatever color is opposite it is up. Now, any color except 1 could be "up", so that makes 5 different solved states. In each of these states, there are 4 colors left - which we refer to as A, B,C and D - which can be paired in three different ways (A-B and C-D, or A-C and B-D, or A-D and B-C), making 5*3 = 15 different solved states. And finally, the pairs can rotate around the vertical axis of the cube either clockwise or counterclockwise (for example, with the AB and CD pairing, the order can be ACBD or ADBC, when the cube is rotated clockwise and seen from top), making a total of 5*3*2=30 different states.

So, the set of solved states for Rubik's Cube has 30 members. They may or may not be essentially similar - I have no idea what the criteria for that is - but they are different states.

Re:Wow, it really works

[Zwaxy]

12? Why 12?

When you twist one of the faces, you're moving 9 of the pieces, but the center one is fixed in place, so that's 8. If you're counting the stickers that move, there are 9 on the face you rotate, and 12 around its outside, making a total of 21, or 20 if again you don't count the center one.

But 12?

Re:Wow, it really works

[anonypus_user]

ok was just counting the ones on the outside, but if you moved just the middle row it could be 12

Re:Wow, it really works

[Zwaxy]

Assign the colors in the cube numbers from 1 to 6. For conveniences sake we orient the cube so that the side with color 1 is down and whatever color is opposite it is up. Now, any color except 1 could be "up", so that makes 5 different solved states.

I don't know if you've ever played with a Rubik Cube, but the center square of each face is fixed. When you rotate any face, the center of that face remains the center of that face, and only the 8 outside sub-cubes change position.

The color of the face opposite the face with color 1 is constant. There is only one solved cube state, not 30, if you consider rotation in space as not changing the state.

Re:Wow, it really works

[somersault]

But would it have been had it not been marked interesting? We will never know. That's quantum that is.

Re:Wow, it really works

[somersault]

Actually, there is only one solved state. The centres in the block always have the same colour opposite to them, if you keep a certain colour face down, then the centre block at the top will never change. I read a little on rubik's cubes recently, I still have never bothered to complete one, but I see now how it's actually a lot simpler than you'd think just by messing about with one for a few minutes every few years :P

Re:Wow, it really works

[corbettw]

Re:Wow, it really works (Score:5, Interesting)
by The Clockwork Troll (655321) Alter Relationship on Thu Mar 27, '08 04:05 AM (#22879454)
Unfortunately the "Interesting" moderation is not finest grain.

There are at least two subtypes of interesting:
- Interesting to someone with joint degrees in math and computer science
- Interesting to someone who has smoked two joints Gee, wonder which one of those applies to your moderation?

Re:Wow, it really works

[armareum]

I think you'll find it's actually [Alanis] ironic.

Re:Wow, it really works

[Paiev]

Oh, come on. If you're going to cheat, at least do it *properly*. Peeling off the stickers reduces the lifespan of stickers with an already short lifespan. If you're going to cheat, do the following:
1) Turn top face 45 degress.
2) Stick your finger underneath one of the edge pieces in the top layer.
3) Pop the edge piece out (the cube is pretty durable, this won't break it unless you do it incorrectly)
4) From here, you should be able to take the cube apart.
5) Reassemble in a solved state.
No, there's no 6) ??? 7) Profit! Steps 1-6 are the ??? and the Profit! is once you've finished.

Or you could just learn to solve the cube the right way.

Re:Wow, it really works

[Chris Mattern]

What's really amusing is that you can take a Rubik's Cube apart and reassemble it so it *can't* be solved. Possibility for hours of fun here...

Re:Wow, it really works

[j4s0n]

Hey, man! I just smoked two joints, and I'm really taking offense to.......Hey! cool name, I loved "A Clockwork Orange"!

Re:Wow, it really works

[2short]

The woman who taught me to solve it could look at a cube and tell you if that had been done in a couple seconds.

Re:Wow, it really works

[maxwell demon]

That of course depends on what qualifies as a move. If turning the middle layers is allowed, then the middle sides can certainly chance places (e.g. a turn left of the cube can then be done with three moves: turn upper layer left, turn horizontal middle layer left, turn lower layer left).
I don't know how exactly the moves are defined for this proof (I didn't RTFA), but there are certainly many possibilities. Note that allowing only moving the outer slides, while universal for the 3x3x3 cube, won't generalize to higher cubes (you'll not get all possible configurations on the 4x4x4 cube this way).

Re:Wow, it really works

[unablepostAC]

The question would be, if starting with an already solved cube, could the program do 25 moves, so that at the end it goes back to solved????

Re:Wow, it really works

[Zarel]

That of course depends on what qualifies as a move. If turning the middle layers is allowed, then the middle sides can certainly chance places (e.g. a turn left of the cube can then be done with three moves: turn upper layer left, turn horizontal middle layer left, turn lower layer left).
I don't know how exactly the moves are defined for this proof (I didn't RTFA), but there are certainly many possibilities. Note that allowing only moving the outer slides, while universal for the 3x3x3 cube, won't generalize to higher cubes (you'll not get all possible configurations on the 4x4x4 cube this way). Turning the middle layer is equivalent to turning the two side layers parallel to it, and counts as two moves by pretty much everyone's definition. No, this is not generalizable to higher cubes, but we're not talking about higher cubes.

Re:Wow, it really works

[tomhudson]

That rather depends on your intuition. I personally would intuit an upper bound of (3^9)/2 which would be further reduced by the fact that abs(n(o) - n(x)) <= 1 where n represents the number of each marker on the board.

No intuition. My numbers are based on a program I wrote a decade ago that generated all possible solutions. It generated static html pages such that you chose to go first or second, and you'd click on the square, and it would load the appropriate next page. 2000 pages to cover every possibility where it won, or, if not a win, then a draw. It never lost :-)

Taking into account mirrors and rotations, another program got it down to under 500, iirc. (it may have been slightly over - can't recall for sure).

It was really neat - a tic-tac-toe-playing set of web pages with no javascript, no programming on the server or the client - just 2,000 static pages.

Re:Wow, it really works

[WithLove]

That's not as hard as it sounds (not to belittle your lady friend). In order for it to be solved, the sides that are meant to be adjacent (green and red, for example) simply must be adjacent. The sides that must be opposite (green and blue, again for example) also must be opposite. That's because there is no block with green and blue on it, so they must be on opposite ends of the cube, or they'd be unsolvable.

I'm more or less an amateur in solving cubes (I can solve one from any position in 2-3 minutes), but I could tell you in 3-4 seconds whether or not a cube can be solved.

Re:Wow, it really works

[Zwaxy]

If turning the middle layers is allowed, then the middle sides can certainly chance places

Not relative to each other they don't.

The middle squares determine the color of the entire face when the cube is solved, and have fixed positions relative to each other.

The post I was replying to was claiming that there are 30 different solved 3x3x3 cubes modulo rotation, but there's only one really.

Re:Wow, it really works

[JimFive]

I doubt it. Assuming that we count each quarter turn as a moves and that we can only move the outside slices of the cube, that would require that there be an odd-numbered move pattern that could be undone by an even numbered pattern. If you make a move, that move has to be undone to get back to your starting point. To undo an odd number of moves, should take an odd number of moves (maybe not the same odd number). As an easy visualization: If you have a solved cube and you rotate the right side 3 quarter turns clockwise, you can get back to the starting point with either 1 quarter turn clockwise of 3 quarter turns counter-clockwise.

However, if we change our assumptions and allow movement of the middle slice then it is trivial to move the right side 1 away the left side 1 away and then undo those 2 moves by moving the middle slice 1 away.

--
JimFive

Re:Wow, it really works

[2short]

Obviously if centers have been switched it's impossible; but that's not the point.

A cube cannot be solved if a single edge piece (with two colors on it) has been removed and reversed; but can be solved if two such pieces have been reversed. Determining if that has happened requires counting up some sort of parity equation on the relative positions & orientations of all 12 two-color pieces.

I'm also a 2-3 minute solver, and I can't tell if a cube is unsolvable in this way in less than, well, 2-3 minutes. My friend was a ~30 second solver, and I assume this determination that a cube is unsolvable is just a side effect of whatever pre-solving scan her brain does.

Re:Wow, it really works

[tor528]

See sig for cause of the problem.

21 is the absolute minimum

[SpaceLifeForm]

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

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

Yeah...24 moves..

[nadamucho]

....or a girlfriend.

80's too

[Tablizer]

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

pffffft

[INeededALogin]

and around 1500 hours of time

pfffft... Java

Q6600

[paul248]

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

Re:change the game

[Dun Malg]

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...

"God's Algorithm"

[wickerprints]

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.

Re:"God's Algorithm"

[insecuritiez]

Most every cuber believes the limit _is_ 20. There is only one known permutation that requires 20 moves and it is called the "super flip". In it, every edge and corner piece are in their correct positions but all the faces have the opposite orientation. It makes for a nice checkered pattern. It is the symmetry of the scramble and the lack of known permutations "harder" than the super flip that lend a strong argument to 20 being the max.

Re:"God's Algorithm"

[bobbozzo]

If we build a large enough computer to process that graph, I'm sure it will find the answer to be forty-two.

Re:"God's Algorithm"

[Anonymous Coward]

> There is only one known permutation that requires 20 moves and it is called the "super flip".

That's not correct, there are a lot of such positions found. Superflip is perhaps the most well known, but certainly not the only one.

Re:"God's Algorithm"

[koogydelbbog]

wikipedia mentions a worse case:

"In 1998 Michael Reid found a new position requiring more than 24 quarter turns to solve. The position, named by him as 'superflip composed with four spot' needs 26 quarter turns."

(could depend on the metric i suppose, face turns or quarter turns)

i did brute force all the corner solutions once, a piffling 88 million permutations, maximum of 11 face turns. but coding up solutions to smaller problems, 24 perms for the first corner, 21 for the second etc and making sure step n+1 doesn't mess up the cubelets put in place by step n is easier and looks more interesting (imo, because you can see what it's doing, unlike the optimal solutions which look like random twisting)

Re:"God's Algorithm"

[Nemetroid]

As of this latest discovery, this maximum distance is 25.

Not really. What has been proved is that there are no vertices that are 26 edge traversals from the solution.

Re:"God's Algorithm"

[insecuritiez]

Different solving algorithms are used for half versus quarter counting metrics. Although I'm not positive, I'm pretty sure the superflip+4spot is only interesting in quarter turns.

The algorithm I use to solve the superflip is 18 half turns and 2 quarter turns. If I were to count half turns as 2 quarter turns, it would not be a particularly efficient quarter turn solution. I've never met a cuber who counter in quarter turns but I can see how it is an interesting counting method for mathematicians and computer scientists.

Re:"God's Algorithm"

[wickerprints]

Yes, of course, you are correct. Have to be more careful with my wording.

Re:Only 25?

[harlows_monkeys]

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

Won't happen. There are positions that require 20 moves.

Re:change the game

[fahrbot-bot]

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

My younger brother liked to take his apart and reassemble with one piece reversed, which (apparently) made it unsolvable. Drove people nuts.

Re:Enumerating Lookup Table

[BazilBBrush]

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

No problem,

we'll just get on with normal life - for some years or more.

Tap us on the shoulder when you're finished.

Oh and umm, how high can you count?

No, what he proved is the upper limit

[Joce640k]

This is a proof of upper limit, not an optimal solution. He proved is that all possible combinations of 26 moves yielded a position which was symmetrical to a cube with a lesser number of moves applied to it.

An optimal solution would probably look like a bell curve going from "zero moves required" (ie. already solved) all the way up to "25 moves required" (which we now know is the upper limit...)

I'll save you the trouble of counting

[cafelatte]

He or she did suggest 25 moves, no more, no less. I counted them myself so that you don't have to.

So the comic was right!!

[Spy der Mann]

http://truckbearingkibble.com/comic/2008/03/10/eureka%C2%B3/

Well Known:

[oGMo]

Up, Up, Down, Down, Left, Right...,

Solve This!

[kramulous]

In light of a certain parallel programming news item a few days ago, I'd like to see him use the same code, same CPU on this one: http://www.youtube.com/watch?v=UrjmeYdVTlc. Hold your breath for that solution.

What the!?

[AlgorithMan]

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.

What the!?
using the A* algorithm solves a rubiks cube within SECONDS on similar Hardware!

maybe it's better, not to use brute force, even if the depth of the recursion tree is limited to 25...

Re:What the!?

[ampathee]

RTFS dude. He didn't solve a cube, he proved that a cube can be solved from any starting position in 25 moves or less.

A *human* can solve a cube in seconds - it's not impressive for a computer to do it.

Re:What the!?

[AlgorithMan]

ok, I misunderstood that...
thanks

Re:What the!?

[Embedded2004]

He isn't solving a single rubiks cube. He's *proving* all rubik cubes can be solved within 25 moves. A much much harder problem.

Re:Only 25?

[sqrt(2)]

I'm pretty sure most of my negative mods lately are directed at my sig, not the content of the posts, since this instance was clearly a joke. It might not be funny, but it's also not a troll.

(this is a good -1 offtopic, btw)

Non-Owners

[8ball629]

Does anyone on /. not have a Rubik's Cube? I'm not trying to flame at all... just an honest question.

Re:Non-Owners

[bobbozzo]

Mine was given away by my parents after I moved out (15 years ago).

But, I think my wife has one around here somewhere.

Re:Non-Owners

[WK2]

I don't have a Rubik's cube. But I do have a girlfriend. And a low-medium income. I'm kind of a freak around here.

what a waste

[boltik]

I can think of better ways to spend 1500 hours on Q6600 with 8gb ram. Just have to add a pair of HD 3870X2's (or pair of 9800GX2 ).

Math and the Rubik's Cube

[mhansen444]

David Joyner has a book which explores some of the math behind the Rubik's cube: http://www.amazon.com/Adventures-Group-Theory-Merlins-Mathematical/dp/0801869471

If you are interested in playing around with the symmetry group associated to the Rubik's cube, Sage (http://www.sagemath.org) has good support for it; the documentation can be found at http://www.sagemath.org/doc/html/ref/module-sage.groups.perm-gps.cubegroup.html . Sage also includes a number of efficient solvers for the Rubik's cube.

Nobody would be fooled

[Joce640k]

Nobody who knows how to solve a cube would be "fooled" by this. Not even for 0.000001 seconds. It'd be "oh, you swapped two stickers, how childish".

Tomas who?

[Straker Skunk]

I have to admit, in reading the summary, Tomas Rokicki's name seemed very familiar....

And of course! He's the author of dvips! So we have him to thank not only for this cutting-edge breakthrough in mathematical solutions to Rubik's Cube, but also for turning our not-overly-portable DVI files into beautiful, beautiful Postscript.

Re:Only 25?

[DKlineburg]

you got your -1 offtopic (which I now will also) but I fail to see how discusing the number of possable moves is off the topic of discussing the number of moves? *Head Explodes*

"may be non-intuitive"

[Joce640k]

A "perfect" solution in 25 moves would be impossible for a human, it would basically mean knowing all possible combinations of the cube and how to get there (and that's an awful lot of combinations!)

I actually solved the cube all by myself back in the 80's. I'm amazed that so much effort is still being put into it and some of the methods used by the record breakers need an awful lot of dedication to learn.

How sad

[Joohn]

...1500 hours of time on a Q6600 CPU running at 1.6GHz... Seems like the Stanford university didn't find Rubic's Cube important enough to let him borrow this.

Re:How sad

[richy freeway]

What I want to know is why he was running the CPU underspeed? The Q6600 is clocked at 2.4ghz out the box and can be easily pushed to 3.6ghz with just air cooling.

Re:1.6ghz? Probably a typo

[WarwickRyan]

You should be able to clock to 3.6ghz, so I assume it was a typo. You'd be dumb to underclock it for something which runs for nearly 9 weeks.

Re:Only 25?

[sqrt(2)]

You're trying to bring logic to the discussion of Slashdot's moderation system? To quote the bard, "That way madness lies."

Fun solitaire-like game with Rubik cube

[Butterspoon]

Once I learned to solve the Cube, I would amuse myself from time to time by taking it apart and reassembling it in a random configuration, and then trying to solve the resulting mess.

With a little group theory you can show that you will be able to solve a randomly reassembled Cube 1/12 of the time.

Re:1.6ghz? Probably a typo

[The Clockwork Troll]

Which is why I cook popcorn in a 10 kilowatt microwave oven for 5 seconds.

Re:How long will it be...

[Soft Cosmic Rusk]

Ha! I can prove that the cube could have been solved 25 moves ago! Beat that!

Re:ask Rain Man

[nowhere.elysium]

Why -1 troll? This guy makes a fair point: Everyone's happy to watch savants on TV shows, telling some flat out stupid presenter what day of the week that March 12th 1732 was, but people are apparently afraid to try and make use of such talents. There's nothing stopping people with high-level autism from providing a useful function in society, other than some relatively prudish ideals about people being 'used'. Most savants tend to *enjoy* using their exclusive skill, and more often than not it's one that can be made into something very, very useful.

PS3 Power

[PhilLong]

I'll bet the computations could have been finished a lot faster (development time excluded ;) on a PS3 http://cag.csail.mit.edu/ps3/

What do we know about "God's Algorithm"?

[Panaqqa]

Okay, time for some math now. First off, let's calculate the number of possible positions ( PP ) of a Rubik's Cube. At first it would seem that the number could be determined as follows:

PP = 12! * 2^12 * 8! * 3^8 = 519,024,039,293,878,272,000 = 5.19 * 10^20

But the cube has a "parity" of 12, and any of the following result in an unsolvable cube: two edge pieces switched in position, one edge piece flipped, one corner piece twisted. This means that if a cube is taken apart and randomly reassembled, it has 11/12 = 91.667% chance of being reassembled into an unsolvable position. But I digress.

So, taking into account parity of 12, the number of possible positions is:

PP = ( 12! / 2 ) * ( 2^12 / 2 ) * 8! * ( 3^8 / 3 ) = 43,252,003,274,489,856,000 = 4.33 * 10^19

Next we need the number of reachable positions ( RP ) after n moves. There are 18 possible ways to turn a face on each move, but after the first move we will assume 17 since the 18th would be undoing the previous move. So after n moves, the number of reachable positions is given by:

RP = 18 * 17^( n -1)

So, after how many moves does the number of reachable positions ( RP ) exceed the number of possible positions ( PP )? That will be the lowest integer value of n where:

18 * 17^( n -1) > 4.33 * 10^19

Logarithms to the rescue:

log 18 + ( n -1) * log 17 > log (4.33 * 10^19)
1.2553 + 1.2304 * ( n -1) > 19.636
1.2304 * n > 19.611
n > 15.939

Take that as showing that for n = 16, the number of possible move combinations exceeds the number of all possible cube positions. So God's algorithm might take as few as 16 moves. Personally, I think that the value is likely 2 or 3 moves higher than this bare minimum. So let's say 19 moves.

Not diminishing the significance of a 25 move algorithm, but the math suggests God's algorithm is 19 moves. Guess it will take a few years to muster the brute force computing power to demonstrate this.

Re:What do we know about "God's Algorithm"?

[Megane]

Great. You can start by reducing Superflip to 19 moves.

Re:What do we know about "God's Algorithm"?

[Panaqqa]

Perhaps it can't be reduced to 19 moves. But then again, Kociemba's algorithm has not yet provided a proof that the diameter of the cube group is indeed 20 (in face counting). We won't have such a proof until an optimal solver is used, something that could take years of run time on current hardware. Application for a grid perhaps?

Re:What do we know about "God's Algorithm"?

[Megane]

I'm not saying anything about an optimal solver, just that you can't have a maximum of 19 as long as there is a known case with a minimum of 20. And that solution is 16 years old.

Re:What do we know about "God's Algorithm"?

[Bob-taro]

Your equation for "RP" ignores different paths reaching the same position.

1500 hours?

[jocknerd]

It only took me about 40 seconds back in my junior high days when the Cube came out.

Select

[dunc78]

I thought there was a "Select" before the "Start" as well as two "B A" s, but I forget what game that was even for, so I could be mistaken.

Amateurs!

[camperdave]

Moving colored stickers? Amateurs! I can solve any cube in three moves... with a can of spray paint. Point, spray, spin.

brush with greatness

[Rob T Firefly]

I one met Erno Rubik himself.

Nice guy and all, but it took me half an hour to finish shaking his hand.

Parallel Computing

[vortex2.71]

"He needed a workstation with 8GB of memory and around 1500 hours of time on a Q6600 CPU running at 1.6GHz."

Can someone teach this guy MPI or at least OpenMP? This could have read "One hour on a modest supercomputer!"

Only one permanent solution to Rubik's Cube...

[patrixmyth]

"Pull", "Fire"

This does require use of a shotgun, of course.

Soon I will be able to solve it!

[Asgerix]

From the article:

But Rokicki isn't finished there. He is already number-crunching his way to a new bound of 24 moves, a task he thinks will take several CPU months. And presumably after that, 23 beckons.

I can't wait till he gets down to 2 or 3 moves; then perhaps even I will be able to solve it!

The n-dimensional version?

[popmaker]

How are the current versions of lower/upper limits of solutions to n-dimensional cubes with n not necessarily 3? It might sound ridiculous to you but I'm willing to bet my pants that some mathematician has thought about it and come up with some results.

THIS, is the reason ...

[QQ2]

THIS, is the reason why I still read Slashdot.

For making a comment which is simultaniously
- Interesting
- Funny
- Geeky
- True
- and involving Math

I salute and humbly bow.

Next up, 24 moves

[FunkyELF]

This sounded (from the summary, I didn't RTFA) like he did a brute force solve on every possible combination out there (after eliminating ones that were symmetric or could be solved the same way).
So, it seems like there were some scrambles which required 25 moves. If he used brute force to find the 25 move solution, thats the end of the problem. No magic is going to find a 24 move solution which a brute force didn't find.

Define Random

[BigJClark]

Just a thought, wouldn't it be possible to define a random state, then with a solved cube, count how many moves it took to get to that state?

Re:AmigaTex, Dvips, Blitter Life

[ewhac]

I, too, had the privilege of meeting Tom back in the Amiga days. Brilliant, brilliant guy. I think he also had a hand in the Amiga EMACS port.

I recall visiting his office in Marginal Hacks (Margaret Jacks) Hall on the Stanford campus. There was a printout on the wall showing several generations of Conway's Game of Life. What wasn't immediately apparent was that, just for the hell of it, Tom had written Life in nroff, the old document formatting language, and the printout was the result.

Back in the 1990's, he helped me with a curious binary math problem. The problem was thus: Assume you wish to find a binary number for which a given subset of bits must be in a certain state (e.g. bit position 3 must remain zero, etc.) -- the set of static bits and their required values may be arbitrary. Given an arbitrary starting value, find the next largest value that has the required bit pattern. I got about 80% of the way toward the solution, but he knocked it out almost immediately (and is left as an exercise for the reader :-) ).

Simply amazing guy.

Schwab

Persons without Asperger Syndrome Support Group

[Enrique1218]

Hello. I do not have Asperger Syndrome and therefore could not understand what was just written in the synopsis. Worst yet, I do not even understand why it is important that a person can solve a Rubiks cube in 25 moves. I feel really left out and as a result I am starting a Persons without Asperger Support Group. If you too are totally lost by this article and fell left out, please join.

"you'll have fun watching him try to solve it."

[Joce640k]

No you won't, he'll spot it within seconds.

There's no way in hell he'll be "frustrated" or anything like that.

Seriously,

[Bob-taro]

... this IS news that matters!

Re:AmigaTex, Dvips, Blitter Life

[solafide]

Can't we treat the bits not static as a binary number, add 1 to it, and replace the original bits with the bits of the new number? For instance, from 101110101001, we treat the number as 101110101, increase by 1 to 101110110, replace for 101110101010.

Re:AmigaTex, Dvips, Blitter Life

[ewhac]

Yup, you've pretty much got the gist of it. The clever bit is how you accomplish that without a myriad of bitfield shifts.

Schwab

Re:ask Rain Man

[nowhere.elysium]

touche...