Beta
×

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

Thank you!

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

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

Rubik's Cube Algorithm Cut Again, Down to 23 Moves

timothy posted more than 6 years ago | from the at-this-rate-one-will-soon-be-enough dept.

Math 202

Bryan writes "The number of moves necessary to solve an arbitrary Rubik's cube configuration has been cut down to 23 moves, according to an update on Tomas Rokicki's homepage (and here). As reported in March, Rokicki developed a very efficient strategy for studying cube solvability, which he used it to show that 25 moves are sufficient to solve any (solvable) Rubik's cube. Since then, he's upgraded from 8GB of memory and a Q6600 CPU, to the supercomputers at Sony Pictures Imageworks (his latest result was produced during idle-time between productions). Combined with some of Rokicki's earlier work, this new result implies that for any arbitrary cube configuration, a solution exists in either 21, 22, or 23 moves. This is in agreement with informal group-theoretic arguments (see Hofstadter 1996, ch. 14) suggesting that the necessary and sufficient number of moves should be in the low 20s. From the producers of Spiderman 3 and Surf's Up, we bring you: 2 steps closer to God's Algorithm!"

cancel ×

202 comments

Sorry! There are no comments related to the filter you selected.

I still can't do it. (5, Funny)

ASMworkz (1302279) | more than 6 years ago | (#23675935)

Call me when it's down to 10 moves! :)

Re:I still can't do it. (5, Funny)

Hankapobe (1290722) | more than 6 years ago | (#23675965)

Call me when it's down to 10 moves! :)

I can do it in one .... I outsource it.

Re:I still can't do it. (5, Funny)

Kjella (173770) | more than 6 years ago | (#23676131)

I can do it in zero, I just declare that it's fine just the way it is and accuse anyone that tries to argue otherwise for being segregationists trying to keep all the different colors apart.

Re:I still can't do it. (-1)

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

That reminds me of a story... back in 1998, I was interning for slashdot, hanging out at the geek compound. Cowboy Neal walked in and tossed a rubik's cube my way. "Jay-Bone, does that smell funny to you?" I took a sniff, "Ugh, it smells like shit!" That's because I shoved it up my ass! bwahahahah!"

Re:I still can't do it. (1, Insightful)

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

Fuck you crafty man and making me read the whole thing before I realized you suck.

Re:I still can't do it. (1)

Ethanol-fueled (1125189) | more than 6 years ago | (#23677503)

I took a sniff, "Ugh, it smells like shit!" That's because I shoved it up my ass! bwahahahah!"
So you managed to fit a whole rubik's cube up your ass? CowboyNeal mustnt've been too impressed.

Re:I still can't do it. (4, Funny)

fizzup (788545) | more than 6 years ago | (#23676177)

Call me when it's down to 10 moves! :)

I can do it in one .... I outsource it.

I can solve it faster .... I defenestrate [merriam-webster.com] it.

Re:I still can't do it. (4, Funny)

Daimanta (1140543) | more than 6 years ago | (#23676357)

Yes, but does the window run Linux?

Please, disregard the previous sentence.

Please, disregard the previous sentence.

Re:I still can't do it. (3, Funny)

Herkum01 (592704) | more than 6 years ago | (#23676649)

When I was a kid I had a rubix cube which one day resulted in this,

Angry Kid + Teacher(target) + Rubix Cube = defenestrate + one half rubix cube + dozens little pieces of a cube.

Afterwards I felt pretty bad about the whole thing...

Re:I still can't do it. (4, Funny)

Fishead (658061) | more than 6 years ago | (#23676699)

I like to buy a new one, solved, and in the package, then using some CA (krazy glue) glue it together so nobody can "un-solve" it.

Re:I still can't do it. (1)

hurfy (735314) | more than 6 years ago | (#23676527)

One is easy

http://www.puzzle-shop.de/aggie-cube.html [puzzle-shop.de]

lol, have that one on my shelf still sealed like that too. Totally amazed i remembered the name to google....

Are the ones that need to be a specific direction a lot more moves? The Pacman cube i have is a killer cause all the little ghosts and stuff started out upright 20? years ago and have been laying down sideways ever since :(

Re:I still can't do it. (1)

HouseOfMisterE (659953) | more than 6 years ago | (#23677811)

Haha, that "Aggie Cube" is pretty darn funny. When I was young I had a book of Texas A&M Aggie jokes. The jokes were probably Pollack jokes with the target changed to "Aggie", and I didn't even know anything about the team, but the jokes made me laugh. There are three or so new sequences to learn in order to properly reorient the center squares on your Pacman cube. The page from which I learned these moves is no longer available, but this page looks like it may be of help to you: http://www.alchemistmatt.com/cube/rubikcenter.html [alchemistmatt.com]

Easy (4, Funny)

camperdave (969942) | more than 6 years ago | (#23676969)

Call me when it's down to 10 moves!

Step 1: Drop cube in can of paint. Done.

Re:Easy (2, Funny)

felipekk (1007591) | more than 6 years ago | (#23677281)

Actually, that's more than 10 moves:

1 Drive to Home Depot
2 Buy bucket and paint
3 Drive back home
4 Open the paint enclosure
5 Drop paint into bucket
6 Clean the floor
7 Clean yourself
8 Drop the cube
9 Pickup the cube
10 Realize that white paint won't make it look solved
11 Drive back to Home Depot
12 Buy a new bucket and dark paint
13 Drive back home
14 Open
15 Drop
16 Clean yourself (you actually learned not to mess the floor)
17 Drive to Toys-R-Us
18 Buy another Rubik's cube
19 Drive back
20 Drop the cube
21 Pick it up

Solved!

Re:Easy (1, Funny)

KDEWolf (972921) | more than 6 years ago | (#23677723)

Call me when it's down to 10 moves! Step 1: Drop cube in can of paint. Done.
Step 2: ?????

Step 3: Profit!

That's quick (5, Funny)

ricebowl (999467) | more than 6 years ago | (#23675947)

And here I used to think my method was faster; but since there's more than 23 stickers on the cube I guess it ain't any more...

Re:That's quick (3, Funny)

Hankapobe (1290722) | more than 6 years ago | (#23675987)

And here I used to think my method was faster; but since there's more than 23 stickers on the cube I guess it ain't any more...

Try spray paint.

Re:That's quick (0)

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

four side masking operations times five of the six sides and six spraying operations with six different cans of paint, that's more than 23 too.

Re:That's quick (0)

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

And here I used to think my method was faster; but since there's more than 23 stickers on the cube I guess it ain't any more...

Try spray paint.

I have an improvement on your spray paint algorithm. Drop it in a can of paint.

Re:That's quick (4, Funny)

Tumbleweed (3706) | more than 6 years ago | (#23676065)

And here I used to think my method was faster; but since there's more than 23 stickers on the cube I guess it ain't any more...

This would definitely faster than my method of taking it apart and reassembling it in the correct order.

Re:That's quick (5, Funny)

Chris Burke (6130) | more than 6 years ago | (#23676829)

I just buy a new one.

Do the math, quick! (5, Funny)

HiggsBison (678319) | more than 6 years ago | (#23677579)

And here I used to think my method was faster; but since there's more than 23 stickers on the cube I guess it ain't any more...

So that would be, um, each face is three by three, um, nine stickers on each face. Then multiply that times the number of sides, so six times nine would be, uh, ...

Forty two.

Re:Do the math, quick! (1)

MadnessASAP (1052274) | more than 6 years ago | (#23678139)

I think perhaps it's time you went back to calculators boy and leave the mental math to us professionals. The answer is 54.

I can always do it.... (4, Funny)

Brad1138 (590148) | more than 6 years ago | (#23675995)

in 48 moves or less. Luckily the center sticker is always in the right place so I don't need to move that one.

Re:I can always do it.... (1)

omnipresentbob (858376) | more than 6 years ago | (#23676643)

How inefficient of you to move a sticker more than once!

Re:I can always do it.... (3, Insightful)

tangent3 (449222) | more than 6 years ago | (#23676989)

With 6 colours and 9 squares per face, there will always be 2 squares of the same colour per face, so it can always be done in 42 moves or less.

Re:I can always do it.... (0)

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

After you've fixed 2 faces, you're down with 4 colors and 9 squares per face, so there will be 3 squares of the same color.
After you've fixed 4 faces, you're down with 2 colors and 9 squares per face, so there will be 5 squares of the same color.
After you've fixed 5 faces, the 6th face is magically solved.

Total: Sum(9-ceil(9/n),n=6..1) = 7+7+6+6+4+0 = 30 sticker swaps or less.

- Smarterassthanyou

Re:I can always do it.... (1)

syousef (465911) | more than 6 years ago | (#23677637)

in 48 moves or less. Luckily the center sticker is always in the right place so I don't need to move that one.

You don't need to remove all 48 stickers. At least one of the outer 8 stickers will match the center on at least one side. So you don't have to unstick them all. So I can do it in 47 moves or less. Nyer!

I have a theory (-1, Offtopic)

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

EARTH HAS 4 CORNER
SIMULTANEOUS 4-DAY
TIME CUBE
IN ONLY 1 EARTH ROTATION.
4 Corner Times CUBES EARTH.
If a God existed, he would be EVIL
to DENY 4 Opposite Corner Days
Simultaneously within a 4 Quadrant
Earth Rotation. It's Simple Math,
IF NOT FOR Academic Lobotomy.
AS ONE, YOU DO NOT EXIST,
neither does the Earth or any God.
All exist as unified mirror Opposites
with a Zero value Existence. As ONE,
  Created Opposites cancel to nothing.

Re:I have a theory (0)

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

Thanks for clearing that up for me^H^H^Hus.

Or... (5, Insightful)

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

"Combined with with some of Rokicki's earlier work, this new result implies that for any arbitrary cube configuration, a solution exists in either 21, 22, or and 23 moves"

Or 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9 or 10 or 11 or 12 or 13 or 14 or 15 or 16 or 17 or 18 or 19 or and 20 moves.

Re:Or... (0, Insightful)

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

I doubt that it is 1 for any arbitrary configuration.

Re:Or... (1, Informative)

CrazedWalrus (901897) | more than 6 years ago | (#23677017)

Of course it can be. Take a solved cube and rotate it one single move. That's an arbitrary configuration, and it's solvable in one move. (Or are we using a definition of "arbitrary" I'm not familiar with?)

Re:Or... (0)

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

Keyword: Any

Re:Or... (2, Informative)

FrangoAssado (561740) | more than 6 years ago | (#23677383)

Well, he did say any arbitrary configuration.

It is currently known that there is at least one configuration that is not solvable in 20 moves or less.

The point being: it is possible to solve a cube from any arbitrary configuration in N moves, where N is 21, 22 or 23 (it's not yet known which).

Re:Or... (1)

MisterBlueSky (1213526) | more than 6 years ago | (#23677355)

No, it says 21, 22 or 23 moves. This statement is more narrow than the one you are suggesting, and thus more interesting.

Re:Or... (1)

linhares (1241614) | more than 6 years ago | (#23677421)

"Combined with with some of Rokicki's earlier work, this new result implies that for any arbitrary cube configuration, a solution exists in either 21, 22, or and 23 moves" Or 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9 or 10 or 11 or 12 or 13 or 14 or 15 or 16 or 17 or 18 or 19 or and 20 moves.
You must be new here. What is meant is that there is ALWAYS a solution within those bounds. Of course, it was not explicitly stated...

Re:Or... (0)

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

"Or 1 or 2 or 3..."

+4 Insightful? Give me a break.

I'd think it would be fairly trivial to imagine a configuration where it would require more than one move to solve the cube, and probably just as easy for one that can't be solved in a half dozen. The 21-23 range may be more difficult to imagine, so a formal "proof" of an upper bound in this range might be more in order.

18 moves is the limit (4, Informative)

BadAnalogyGuy (945258) | more than 6 years ago | (#23676047)

Mathematically, the limit is a hard 18 (by faces): 6^2 / 2. alternatively by squares per face: ((9 * 6) / 3) ^ 2 / (2^2)

The math isn't hard. It's finding those correct 18 moves that is.

Re:18 moves is the limit (2, Informative)

BadAnalogyGuy (945258) | more than 6 years ago | (#23676137)

Sorry, that second one is from another algo.

It should be 2(3^3)/3

Re:18 moves is the limit (4, Informative)

IWannaBeAnAC (653701) | more than 6 years ago | (#23676193)

No, that is just a lower bound: by counting the number of possible configurations it can be shown that there exists at least one configuration that takes 18 or more steps to solve. It says nothing about an upper bound, which could (and is!) somewhat larger.

Re:18 moves is the limit (1)

kestasjk (933987) | more than 6 years ago | (#23676839)

And who said abstract math isn't useful?

Re:18 moves is the limit (1)

collinstocks (1295204) | more than 6 years ago | (#23677231)

But is it really a lower bound? I can think of many configurations that take fewer than 18 moves.

Re:18 moves is the limit (1)

linhares (1241614) | more than 6 years ago | (#23677445)

lower bound to ANY configuration possible imaginable in the freaking universe, not that easy one you have in mind.

Re:18 moves is the limit (3, Insightful)

Sunthalazar (69878) | more than 6 years ago | (#23677513)

There are 2 statements.

1) "there exists" a configuration for which the minimum number of steps is "18".

2) "for all" configurations, "there exists" a solution that takes less than XX steps to solve.

We are trying to find the answer to #2. We know that #1 exists, so we know that the lower bound of a perfect solver (#2) is 18.

The article seems to be saying that the upper bound of #2 is 21-23.

Re:18 moves is the limit (0, Insightful)

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

There exists at least one combination that takes at most 0 steps to solve

Re:18 moves is the limit (2, Interesting)

mikael (484) | more than 6 years ago | (#23676435)

But there is more than one solution - the centre cube on each face can have any one of four orientations. If you were to paint arrows onto each cube, scrambled the cube, and then solved it, the arrows would not necessarily be aligned with the rest of the cubes on that side.

So there might be actually 4^6 solutions (4096).

Solvable? (5, Interesting)

CastrTroy (595695) | more than 6 years ago | (#23676071)

The summary says for every solvable cube. What does that mean. Every configuration is a solvable one. If you remove a corner and rotate it, and place it back in the cube, the cube is no longer solvable, but I would argue that it's no longer a rubik's cube either.

Re:Solvable? (5, Funny)

pwnies (1034518) | more than 6 years ago | (#23676149)

It may not be a rubiks cube, but it would be quite humorous if strategically placed in an "Obsessive Compulsive Puzzle Solvers Anonymous" meeting.

Re:Solvable? (0)

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

I think most people at such meetings would eventually realize it's not solvable.

Re:Solvable? (4, Insightful)

ampathee (682788) | more than 6 years ago | (#23676265)

Not really. Anyone who could solve a cube would find the rotated corner in a minute or two. My group of friends were into rubiks cubes a few years ago, and that trick got old fast.

Re:Solvable? (3, Funny)

Fred Ferrigno (122319) | more than 6 years ago | (#23677063)

My friends decided to flip two pieces without telling me, thinking that would really annoy me. They were quite disappointed when I solved the cube, as the second flip perfectly counteracted the effect of the first.

Re:Solvable? (2, Insightful)

Kjella (173770) | more than 6 years ago | (#23676279)

Not for very long. While nowhere near the minimum number of steps, there are fairly simple techniques to solve a Rubik's cube so they'd quite quickly conclude it's been tampered with.

Re:Solvable? (1)

Your Pal Dave (33229) | more than 6 years ago | (#23676655)

Yeah, when they first come out with books containing solutions I decided to fix a cube so that it was unsolvable and leave it out for someone who had memorized the solution to try and solve it. They always figured out the tampering within a minute or so.

Sadly, it was not nearly as amusing as I had hoped.

At least I still had my RPN calculator to lend to the smartass premeds in chem lab. (Furious punching of keys followed by "Where's the Equals?")

Re:Solvable? (1)

compro01 (777531) | more than 6 years ago | (#23677431)

At least I still had my RPN calculator to lend to the smartass premeds in chem lab. (Furious punching of keys followed by "Where's the Equals?")
I had a guy try that on me. He was rather put out when he found I knew how to use it.

Re:Solvable? (1)

Chris Burke (6130) | more than 6 years ago | (#23678119)

When I forgot my trusty TI-81 in a calculus class, a friend tried to do that to me by handing me an HP calculator. I was very confused at first, and my friend had a laugh, but he didn't know how much assembly programming I had done and manipulating stacks wasn't exactly foreign to me.

That's my "i'm smart" story since I have to admit I was never very good at Rubik's Cube. :(

Re:Solvable? (2, Funny)

Deanalator (806515) | more than 6 years ago | (#23676713)

I once spent and hour or so working on a cube before I realized that one of the two color pieces had two colors from opposite sides of the cube :-(

It is pretty annoying when people do the sticker trick to only solve one side of a cube.

Re:Solvable? (1)

greg1104 (461138) | more than 6 years ago | (#23676203)

But if you're given an arbitrary cube, how do you know if it's been tampered with such that it's no longer solvable? It may be the case that the simplest way to determine that, that works in every case, is to try and solve the cube and discover you can't. I don't believe it's a trivial problem to stare at a cube and figure out if a simple change like a rotated corner has been made to it.

Re:Solvable? (0)

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

Actually, it's somewhat trivial. Not trivial as in mathematically trivial, 0 solution to nth-order homogeneous differential equation, but simple.

Simply learn how to solve a cube blindfolded, and the technique involved with memorizing the cube will also allow you to see where pieces have been swapped, flipped, or rotated.

Warning: Slow-loading page ahead.
http://www.cubefreak.net/blindfoldcubing_guide.html

Re:Solvable? (2, Informative)

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

Nah. It's pretty easy to tell if a scrambled cube is solvable. You can see which individual edge pieces are "flipped" and which corner pieces are correct or rotated (either clockwise or counter-clockwise). In a solvable cube, you must have either 0 flips or an even number of flipped "edge" pieces. If you assign a value of 1 to clockwise turned corner pieces and a value of 2 to counterclockwise pieces, adding up the values must be divisible by 3. Assuming these criteria are met, a scrambled cube can be deemed as "solvable". This is determined in a manner of seconds for us blindfold solvers but can be learned by just about anyone in less than an hour.

Re:Solvable? (2, Insightful)

Kjella (173770) | more than 6 years ago | (#23676249)

Probably because it's more work to find what all the permutations starting from a solved rubik's cube are, instead you start with a general cube and quickly eliminate the unsolvable ones. Techincally you're solving a slightly more general problem with the rubik's cube as a special case, so "solvable cube" is probably correct in the paper but equals rubik's cube in practical life.

Re:Solvable? (1)

brady8 (956551) | more than 6 years ago | (#23676335)

"Solvable" in this context means that that particular configuration is one of those possible configurations you can end up with on a physical Rubik's cube. Since we're dealing with a computer simulation, the complete set of configurations would include many "unsolvable" ones - those which are the computer equivalent of the illegal moves that the parent suggests - removing a corner and rotating it, etc.

Definitions (1)

Ghoser777 (113623) | more than 6 years ago | (#23676385)

It really depends if solvability is implied in the definition of a rubik's cube. The game of Solitaire is not always winnable from initial given cards - does that mean that the dealt cards aren't a legal Solitaire game, or just not winnable?

Re:Definitions (1)

hobbit (5915) | more than 6 years ago | (#23676703)

Solitaire is different to the Rubik's cube in that you can shuffle a pack of cards into an unwinnable game of solitaire, but you can't shuffle a Rubik's cube into an unsolvable configuration -- you have to take it apart for that.

Re:Definitions (1)

fmoc-86 (1279012) | more than 6 years ago | (#23677973)

I think they are analogous at that. Only, the composing parts of the thing you play with are of different structure.

Re:Definitions (1)

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

A Rubik's cube is one of 12 possible (similar looking) cubes you can make if you start with all the pieces taken apart. The set of all possible cube configurations is separated into 12 orbits and a Rubik's cube can only reach configurations within the orbit that it's already in when it's solved. I wouldn't call the other 11 cubes Rubik's cubes. You start by scrambling a solved cube like a normal person, not assembling an unsolved cube from parts to see if you're going to "win" or "lose" with the cube you made. It's not like Solitaire at all.

Re:Solvable? (1)

mdmkolbe (944892) | more than 6 years ago | (#23678011)

Every configuration is a solvable one.

If you take a cube apart and put it back together in random order, it may not be solvable. IIRC there are twelve sets of configurations where it is possible to get between configurations in the same set, but not between configurations not in the same set. (This obviously ignores configurations where you just took the stickers off and repasted them.)

LET THERE BE THREE moves... (3, Funny)

davidsyes (765062) | more than 6 years ago | (#23676101)

1. Pour paint on Cube
2. Let Dry
3. PROPHET

I can do it in 2... (3, Funny)

El_Oscuro (1022477) | more than 6 years ago | (#23676191)

  1. Take apart
  2. Put back together (wait... why are there parts left over????)

Re:I can do it in 1 (0)

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

1. Solve cube

Re:I can do it in 1 (0)

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

I commend you for your CISC style of cube solving!

Re:I can answer that!! (0)

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

(wait... why are there parts left over????)

Captain obvious sez: YOUR DOING IT WRONG! :)


I'll take my +5 Wiseguy now, KTHXBIE

Re:LET THERE BE THREE moves... (4, Funny)

GoodNicksAreTaken (1140859) | more than 6 years ago | (#23676391)

3. PROPHET
That must be part of the God's algorithm the summary mentions.

Re:LET THERE BE THREE moves... HEHEHE (1)

davidsyes (765062) | more than 6 years ago | (#23676697)

hate to quote Kirk... but, "What does God need with a..." Rubik's Cube?

Re:LET THERE BE THREE moves... HEHEHE (1)

Tango42 (662363) | more than 6 years ago | (#23676833)

This is Slashdot - you're allowed to quote Kirk.

"God" is loaded. (0, Troll)

Besna (1175279) | more than 6 years ago | (#23676113)

Just don't use it. Barking may be useful for dogs, but we don't bark either.

chuck norris could... (0)

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

I bet Chuck Norris can solve any rubik's cube in 1 move tho...

That's great. (1)

raehl (609729) | more than 6 years ago | (#23676255)

Maybe he should next try and find the minimum number of edits to fix the grammar in a Slashdot article submission.

After that, solve for the max number of edits a Slashdot editor will actually do before just posting the article anyway.

but rubik's hypercube remains unsolved (1)

circletimessquare (444983) | more than 6 years ago | (#23676291)

that 4th dimensional rotational axis means you have to reach forward in time in order to solve one side in the present, without affecting any other sides you solved in the past, meaning you can't twist it to the present, without affecting what you've already solved in the future

rubik's hypercube has me stumped

Re:but rubik's hypercube remains unsolved (0)

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

Would the stumping ever stop if you never solved it?

Re:but rubik's hypercube remains unsolved (1)

m1ss1ontomars2k4 (1302833) | more than 6 years ago | (#23676591)

Actually, quite a few people have solved it.

Re:but rubik's hypercube remains unsolved (1)

icegreentea (974342) | more than 6 years ago | (#23676767)

A 4 spatial dimension hypercube as been solved. There are giant algorithms that allow humans to solve them given enough time (I think its around 1000 moves). A 5d version is also around (and also solved. by computers only I think).

Only one move required... (5, Funny)

FoolsGold (1139759) | more than 6 years ago | (#23676515)

Blend the fucker - http://www.youtube.com/watch?v=NrqHHBibRvs [youtube.com]

There, saved you from another 22 pointless moves.

Re:Only one move required... (1)

surfchicky23 (1293696) | more than 6 years ago | (#23677463)

I'd rather do an extra 22 moves then wreck my blender! I need a smoothie!

Slightly offtopic (2, Interesting)

KokorHekkus (986906) | more than 6 years ago | (#23676573)

I actually found one of the solutions (obviously not uniquely) for the Rubiks Cube myself. It ended up to be the "corners first"-type of solution which I think is quite a natural way to reach a solution (it's basically a divide and conquer algorithm). If you can put the corners in their right place you only need to use a 8 move permutation to solve the rest which I call "the cross"-pieces.

So I'm curious if anyone else has experienced this as being the obvious but not perfect solution?

Re:Slightly offtopic (1)

KokorHekkus (986906) | more than 6 years ago | (#23676587)

Ehum, of course I meant the same 8 move permutation applied many times, not just once. Sorry.

Necessary can be zero (1)

againjj (1132651) | more than 6 years ago | (#23676651)

suggesting that the necessary and sufficient number of moves should be in the low 20's
The necessary number of moves can be zero, for example for a solved cube. Instead, it should read that the minimum sufficient number is at least 20. http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube [wikipedia.org] And of course, this is talking about face turns; the numbers for only quarter turns are higher.

Fuck off - this shit is boring. (-1, Troll)

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

Fuck off - this shit is boring.

Good thing I didn't pay attention in the 80's... (0)

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

Because the Internet was coming and I knew that I'd have to sit through the 80's over and over again for the rest of my life.

Brute force (1)

Tango42 (662363) | more than 6 years ago | (#23676851)

This is just using a powerful computer to solve it by brute force... it's not really an algorithm, it's just a proof of a new upper bound.

(I know, technically speaking, brute force probably does count as an algorithm, but it's not a very impressive one.)

Re:Brute force (2, Informative)

rokicki (132380) | more than 6 years ago | (#23676985)

This result required the use of *many* computers to solve *many* positions (approximately four million billion positions), and each found solution was 20 moves or less.

Yes, in some terms it was brute force, but consider how big a number four million billion is, and how long it takes to solve just a single position in 20 moves or less.

Re:Brute force (1)

mdmkolbe (944892) | more than 6 years ago | (#23678073)

The art in using brute force is in pruning down the search space.

For example, calculating the optimal tic-tac-toe game by hand is a lot easier once you notice and exploit the symmetries.

Some "brute force" algorithms move from exponential to cubic or better once you trim them down properly. So any new tricks for improving brute force are of interest.

Re:Brute force (1)

phliar (87116) | more than 6 years ago | (#23678147)

Beauty is in the eye of the beholder....

This is not about using brute-force solvers. Given some problem space, there are many interesting things to think about: optimal algorithms -- in time, and in memory -- of course; but also exploring the structure of the space itself. Interesting symmetries, upper and lower bounds on path and cycle lengths, ... . The possibilities are boundless.

And no one would consider using a brute-force solver, but writing one would be interesting. Give it a try.

Hofstadter (2, Informative)

pez (54) | more than 6 years ago | (#23676923)

Perhaps slightly off-topic, but the Hofstadter cited (via Metamagical Themas) is the same Douglas Scott Hofstader that wrote Goedel, Escher, Bach -- one of the greatest books ever written.

Re:Hofstadter (1)

Myrddin Wyllt (1188671) | more than 6 years ago | (#23677705)

Any relation to Douglas Richard Hofstadter, who wrote a different book with the same title. (Or was it the same book with a different title...)

He's never off-topic here; reading slashdot is the best example of Hofstadter's Law known to man.

Slashdot (0)

mangu (126918) | more than 6 years ago | (#23677301)

News for Nerds -> Check


Stuff that Matters -> Whut?

Ghetttoooo (1)

billcopc (196330) | more than 6 years ago | (#23677897)

I don't care how smart this guy thinks he is, somebody please buy him a freakin' domain name.

Recapping what it means (5, Informative)

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

When the limit was proved to be no worse than 25, there were lots of comments on Slashdot that misunderstood various aspects of what this means.

Here are clarifications for some common points of confusion:

1. What Tom has shown, that "an arbitrary cube can be solved in 23 moves", it means the nastiest legal cube needs no more than 23 face turns to solve. Obviously many starting configurations can be done in less.

2. This type of research doesn't tell you WHICH 23 moves. Only that it's 100% certain that there exists a 23-moves-or-shorter solution, for any legal cube.

3. It's easy to figure out the total number of permutations of the cube. Given that, it can be determined that 17 face-turns doesn't produce enough different permutations, but 18 does, so there is a definite lower bound of 18 moves, that is, there exists at least some configurations that MUST be 18 moves or more away from solved.

4. Specific configurations have been found that provably need 20 face turns to solve. So the worst-case will never get better than that.

5. It may be possible to narrow the limit further, showing that all cubes can be solved in 22 face turns or less. Maybe 21. Maybe 20. It will never get lower than that.

Put succinctly, as of today, the worst-case number of face-turns to solve a cube is no worse than 23. It's been known for a while that the worst case is no better than 20.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

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

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

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

<ecode>    while(1) { do_something(); } </ecode>