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

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

Comments

I still can't do it.

[ASMworkz]

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

Re:I still can't do it.

[Hankapobe]

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.

[Kjella]

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.

[fizzup]

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

Re:I still can't do it.

[Anonymous Coward]

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

Re:I still can't do it.

[Daimanta]

Yes, but does the window run Linux?

Please, disregard the previous sentence.

Please, disregard the previous sentence.

Re:I still can't do it.

[hurfy]

One is easy

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

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.

[Herkum01]

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.

[Fishead]

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.

[Ethanol-fueled]

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.

[HouseOfMisterE]

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

Re:I still can't do it.

[Obstin8]

Ha, that made me laugh. At an old biotech I used to work at the IT department had a standard '3-D' response to any issue.

• D1: DIFFUSE: Yes, we are caring and totally empathize with your situation
• D2: DEFER: But you must understand that that our hands our tied because the (x) has said (y)
• D3: DEFENESTRATE: Therefore, we must decline your request at this time.

It worked like a friggin' charm every time. And we'd gang up on the poor hapless PHB. A senior IT guy would walk in, ready to FIX THE PROBLEM. The first thing he'd ask for was a status update. We'd invariably respond with "Well, it's a D2 right now, but we're still looking into it", and he'd quickly bump it up to a "D3". Then we'd go for a nice extended lunch, and the PHB would be left scratching his head wondering where all his clout had evaporated to.

Fuck, I loved IT before it all caved in and we became computer janitors.

Re:I still can't do it.

[khallow]

This method has firm group theoretic underpinnings too. An alternate way to view this excellent solution is to realize that moves don't matter. Thus, you can say all states of the Cube linked by moves are equivalent in their state of fineness and hence the entire orbit is a single equivalence class of acceptability. This reduces the overly complex and uninteresting problem to a trivial one. Perfectly mathematical thing to do.

Re:I still can't do it.

[this great guy]

What did the verb "defenestrate" apply to ?

• 1. the cube
• 2. the kid

Re:I still can't do it.

[SQLGuru]

This post intentionally left blank

Re:I still can't do it.

[paniq]

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. Actually it is much more fun to glue the cube when it is unsolved, leave it lying around on cocktail parties, and count the innumerable fruitless attempts to solve it. Its colorful chaos will remain a splinter in the mind of every party guest throughout the festivities.

Re:I still can't do it.

[ladybugfi]

No, the correct answer is

• 3. The teacher

Re:I still can't do it.

[Anonymous Coward]

please mod parent down (fascist troll).

Re:I still can't do it.

[Richy_T]

Pshaw, everyone knows that teachers should be disposed of on the top of bonfires.

Rich

Re:I still can't do it.

[MarkCollette]

You should leave it just one or two moves from being solved, before gluing it, to make it all the more of a frustration.

Re:I still can't do it.

[Anonymous Coward]

how gay are you.... i've been solving the cube for about a year now. and i have a SuB-20sec average.

if you have nothing positive to say dont say anything at all! ! ! ! ! ! ! ! ! ! !

That's quick

[ricebowl]

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

[Hankapobe]

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

[Tumbleweed]

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

[Anonymous Coward]

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

[Chris Burke]

I just buy a new one.

Re:That's quick

[Anonymous Coward]

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

[Anonymous Coward]

Fact: The cube can only be disassembled without breaking it when it's solved ;P

Re:That's quick

[gartogg]

Fact: You are wrong.

Re:That's quick

[BForrester]

That's assuming you remove *all* of the stickers and then replace *all* of them again.

Of the 54 squares on the cube, I think you can assume that there will be two of the "proper coloured" stickers per face. That scenario saves you 12 moves, leaving you with only 42 stickers to replace - in the worst case.

42 moves isn't 23, but you can impress your friends (and prolong sticker life) without having to take a math class.

Re:That's quick

[nizo]

If you had the original rubix cube, the white center square would pop off, allowing you to unscrew it and easily take apart/reassemble the cube. Way better than the new cheap ones that you have to pop apart and hope you don't break in the process.

I can always do it....

[Brad1138]

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

[omnipresentbob]

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

Re:I can always do it....

[tangent3]

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

[Anonymous Coward]

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

[syousef]

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!

Re:I can always do it....

[DrEasy]

Now what would be the upper bound on solving the cube by moving the stickers around? What's the worst initial position?

Re:I can always do it....

[harry666t]

MAN, that's Forty Six & Two!

Re:I can always do it....

[Anonymous Coward]

Yes, but it's not necessarily the case that one of those two squares will be the center square, meaning that solving in that manner will result in the colors being on the wrong sides -- which, arguably, is an incorrect solution.

Re:I can always do it....

[Sethus]

CMON SLASHDOT!

You're bound to have a couple sides that have more than one of the same color on it. Clearly, this would be solved in less than 42, someone (preferably someone at work, because it amuses me) figure it out.

Slashdot needs an equation. It demands it.

Re:I can always do it....

[Richy_T]

Not true. There's a move which rotates the center squares between three of the faces (and the opposite three also). Now, that would mean having to only move the six center stickers but it invalidates your argument.

Rich

Re:I can always do it....

[MoriaOrc]

I'll take a crack at it!

On any given face, there must be at least 2 stickers that share a color (6 colors, 9 possible positions). In the worst case, you get a face with 3 colors "double" (there are two stickers of that color on that face) and 3 colors "single" (they are the only sticker of that color on that face). Furthermore, in this situation, since each color has 9 stickers on the cube, each color must be doubled on 3 faces and singled on 3 faces.

If we are starting with a valid rubix cube (actually solvable), then I need to make some assumptions. If not, then stickers can obviously be arranged in this worst-case format.
It is possible for all faces to be in the worst position simultaneously (the 3x2, 3x1 as above) - if false, the maximum bound would be lowered.
In this situation, each color has at least one unique face where it is doubled (that is, it isn't possible for four colors to only occupy three faces as "doubled") - if false, the maximum bound is lower.

In that case, each face would require exactly 7 moved stickers. Multiplied by 6 faces, 7x6 = 42.
...
Maybe the Hitchhikers guy was on to something there..

Another fun problem:

Re:I can always do it....

[MoriaOrc]

(d'oh, proof-reading for the win)
I was going to say.

Another fun problem:
-See if this position is reachable with a valid rubix cube.
-See if the upper bound is affected if you make sticker swaps mandatory (that is, you can't hold stickers "off the cube," only swap their positions on the cube).

Re:I can always do it....

[syousef]

I think you completely misunderstood my argument.

If you're cheating and peeling stickers you don't have to worry about the transforms or legal moves. On each face, you just pull of the stickers that don't match the center sticker instead of all 8.

As far as I'm aware there's no configuration of the cube where one face doesn't have a center piece the correct colour AND any one of the other faces matching on any one of the six sides. No I can't prove it mathematically but I don't think I've seen a cube jumbled that way.

Or...

[Anonymous Coward]

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

[Anonymous Coward]

I doubt that it is 1 for any arbitrary configuration.

Re:Or...

[CrazedWalrus]

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

[Anonymous Coward]

Keyword: Any

Re:Or...

[MisterBlueSky]

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

[FrangoAssado]

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

[linhares]

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

[Anonymous Coward]

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

Re:Or...

[harryjohnston]

He said "I doubt that it is 1 for any arbitrary configuration." That translates to "there is no configuration which can be solved in 1 step" which obviously isn't true. What he presumably meant to say was "I doubt that it is 1 for *all* configurations." (The word "arbitrary" is redundant.)

Re:Or...

[vux984]

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

So if you have a solved cube and make 1 move... the distance back to solved is 1 move.

To do it in 21 22 or 23 moves ... seems a touch less interesting. back-forth-back-forth...x21

Re:Or...

[Anonymous Coward]

Actually, that sentence wanted to say "The smallest N such that (EACH valid configuration is solvable in N moves or less) is one of 21, 22, and 23."

Re:Or...

[this great guy]

You could share the script you used to output that sentence...

#!/bin/sh echo "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...

[Anonymous Coward]

"Any" is one way of expressing the universal quantifier verbally. Another way would be "for all." So think of his original statement as "I doubt that it is 1 for all arbitrary configurations," and he is absolutely correct.

Re:Or...

[Anonymous Coward]

or 0

Re:Or...

[jibjibjib]

echo -n "Or ";for i in `seq 19`; do echo -n "$i or "; done; echo "and 20 moves."

Re:Or...

[paniq]

"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. note he said "arbitrary", which means that the minimum number of moves must be applicable to any state the cube is in. Of course you can be lucky to have a cube in front of you which just requires e.g. 2 turns to solve, but that doesn't apply to any other configuration.

Re:Or...

[kalirion]

Scripts are for wusses. I'm doing this as a web service.

Re:Or...

[Anonymous Coward]

bash# echo or\ {1..20} moves

Re:Or...

[Anonymous Coward]

...Or 0...

Re:Or...

[musselm]

Or zero moves!

Re:Or...

[Anonymous Coward]

But by following the cited work, you could have read that "there is some cube configurations requiring at least 20 moves to solve". :)

18 moves is the limit

[BadAnalogyGuy]

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

[BadAnalogyGuy]

Sorry, that second one is from another algo.

It should be 2(3^3)/3

Re:18 moves is the limit

[IWannaBeAnAC]

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

[mikael]

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

Re:18 moves is the limit

[kestasjk]

And who said abstract math isn't useful?

Re:18 moves is the limit

[collinstocks]

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

[linhares]

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

[Anonymous Coward]

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

Re:18 moves is the limit

[Sunthalazar]

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

[BadAnalogyGuy]

That's not actually true. The proof for this is that there is no solved configuration of a Disney character cube which has a scrambled character image. In the solved configuration, all pieces are in a very specific location (the orientation of the cube itself notwithstanding).

Try it.

Re:18 moves is the limit

[bwroberts]

In fact, Rokicki has shown that there exist configurations requiring at least 20 moves to solve. That's why the author said that for any arbitrary cube configuration, it takes 21, 22, or 23 moves to solve it.

Re:18 moves is the limit

[harryjohnston]

That's what the summary says, but it's wrong - or rather, phrased improperly. The statement you've quoted translates to "for any configuration X, the number of steps necessary to solve X is 21, 22, or 23." Of course this is wrong; there are configurations that require fewer steps. (Also as far as I know we don't know yet whether there are solutions that require 21 steps.)

Rokicki, in his paper, phrased his statement properly: "every position in the cube can be solved in 25 moves or less".

The summary should have simply said that this shows the maximum number of moves that can be necessary to solve Rubik's cube is either 20, 21, 22, or 23.

Re:18 moves is the limit

[Paaskonijn]

I have tried it. The GP is right.

Re:18 moves is the limit

[Sparr0]

To actually *prove* your premise, I would probably start by considering the corners. Since each corner has 3 colors, they cannot change position relative to each other [between solved configuration"s"] except by symmetric operations. Nor can the edge cubes, by similar logic. I am not sure how to state it formally. I am also not sure how to extend the concept to prove that the central square cannot be rotated, but given that you "know" that to be true, I would hope a proof is possible (without resorting to mechanical analysis of the cube).

Re:18 moves is the limit

[WI2822]

To solve means to find a solution (keyword: find). Saying you can solve the combination within 0 steps is like knowing all along where your carkeys are, then exclaiming you have managed to find them... You'd be a damn liar!

Re:18 moves is the limit

[locofungus]

If you are saying there is no way to rotate a centre face without moving any of the other pieces then you are wrong.

Proof:

F1U1 (front 90, Upper 90) repeated 105 times returns the cube to its original state.

But 105 is 1 mod 4. Therefore the Front and Upper centres have been rotated by 90 degrees at the end of this move.

R1F1 has similar properties, as does R1U1.

Therefore F1U1^105 R1F1^105 R1U1^315 will rotate F centre through 180 and R and U centers through 360 - i.e. one centre will be rotated by 180 degrees.

Funnily enough, only last week I got a cube that had polarization of the centres. I very quickly found a move to rotate one centre 90 clockwise and an adjacent 90 anticlockwise but the move to rotate a single centre through 180 degrees took me a very long time to find. (The above 525 step move is not original to me and was only pointed out to me once I'd found a 12 step move to do the same thing)
Also the cube I had actually had one centre that could be in any orientation when viewed on its own. Only when comparing with the other centres was it possible to deduce that the centre was rotated from it's factory state.

Tim.

Re:18 moves is the limit

[TuringTest]

Actually, the meaning of the number 0 is exactly what the GP said. Are you a liar every time you say 0, just because you're "cheating" at counting?

Re:18 moves is the limit

[paniq]

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. now this is where the anonymous coward from above could have been correct:

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

Re:18 moves is the limit

[SQLGuru]

C programmers don't know how to count, anyway.

(I know, I know.....it's an offset from the pointer, so it's really offset 0, offset 1, etc.)

Layne

Re:18 moves is the limit

[Anonymous Coward]

That brings up an interesting question (especially for any of us that are Rubik's-challenged):

If the solving moves are random (not chosen to specifically prevent imminent order) is there a hard limit or mean number of moves that will inevitably or probably (>90% of the time) solve typically disordered cubes?

Re:18 moves is the limit

[IWannaBeAnAC]

If you do random moves, then the time required to `find' a solution is basically infinite. Well, not quite infinite, but he time is proportional to the total number of configurations of the cube, which is, according to Wikipedia, 43,252,003,274,489,856,000. If toy want 50% probability, then expect to do at least half that number of moves[*]. Don't hold your breath.
[*]actually it would be somewhat more than that, as random moves would correspond to a random walk in a 24-dimensional space, and the probability of re-visiting an earlier configuration increases quite substantially as time progresses.

Re:18 moves is the limit

[Anonymous Coward]

Ah, okay. Thank you for clarifying. I get it now.

Solvable?

[CastrTroy]

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?

[pwnies]

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?

[greg1104]

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?

[Anonymous Coward]

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

Re:Solvable?

[Kjella]

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?

[ampathee]

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?

[Kjella]

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?

[brady8]

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

Re:Solvable?

[Anonymous Coward]

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?

[Anonymous Coward]

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?

[Your Pal Dave]

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?

[Deanalator]

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?

[Fred Ferrigno]

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?

[compro01]

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?

[mdmkolbe]

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

Re:Solvable?

[Chris Burke]

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?

[Your Pal Dave]

That's my "i'm smart" story since I have to admit I was never very good at Rubik's Cube. :( Oh, I never actually solved the thing, unless you count prying it apart and re-assembling it in the correct order!

Re:Solvable?

[Anonymous Coward]

In the game SET, you can find a group of 20 cards that have no sets in them. (There's always a set if you have 21 cards.) So once, in a place where lots of people were familiar with the game, I laid out the appropriate 20 cards in a grid on the table as if it was a game that had been abandoned.

Soon, there were a whole lot of people crowded around, staring intensely at the cards, trying to find the set. With that many cards, there just had to be one. (The 20-card grouping doesn't even look like a stuck board -- it looks in many ways like there should be a set. Even the fact that the number of cards is supposed to be a multiple of 3 didn't really clue anyone in.)

Re:Solvable?

[Anonymous Coward]

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.

You must be popular with girls.

Re:Solvable?

[UnknownSoldier]

Someone have a link to the 3x3 parity function?

Re:Solvable?

[Anonymous Coward]

Not really. Anyone who could solve a cube would find the rotated corner in a minute or two.

I used to solve people's cubes and sometimes it was obvious they'd moved stickers to solve a side. I'd ask, "You peeled and moved stickers, didn't you?" and they'd aways say "No." Then show them how a cube was made up of parts and you can't have a corner piece with two white stickers on it. Then they'd admit they'd done it and I'd offer to fix it by moving the minimum number of stickers (less chance of them falling off later).

Re:Solvable?

[Anonymous Coward]

A solvable cube is one that can be solved. On mine, for example, green must be opposite blue, white to yellow, orange to red. One of my friends switched the side and, as a previous poster mentioned, it's easily fixed.

Also, to anyone that was wondering, the wikipedia article on Rubik's Cubes has the number of permutations of a cube. I don't recall if it has the number of physically possible ones or the number of theoretically possible.

LET THERE BE THREE moves...

[davidsyes]

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

Re:LET THERE BE THREE moves...

[GoodNicksAreTaken]

3. PROPHET

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

I can do it in 2...

[El_Oscuro]

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

Re:I can do it in 1

[Anonymous Coward]

1. Solve cube

chuck norris could...

[Anonymous Coward]

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

That's great.

[raehl]

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.

Re:That's great.

[tehcyder]

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

That's an easy one, the answer's exactly zero.

Mastermind

[LoudMusic]

I know it's not a Rubik's cube, but I can solve any Mastermind puzzle in seven moves.

http://en.wikipedia.org/wiki/Mastermind_(board_game)

Re:Mastermind

[Anonymous Coward]

The Maximum needed is actually 6

but rubik's hypercube remains unsolved

[circletimessquare]

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

[Anonymous Coward]

Would the stumping ever stop if you never solved it?

Re:but rubik's hypercube remains unsolved

[m1ss1ontomars2k4]

Actually, quite a few people have solved it.

Re:but rubik's hypercube remains unsolved

[icegreentea]

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

Re:but rubik's hypercube remains unsolved

[ConceptJunkie]

that 4th dimensional rotational axis means you have to reach forward in time

Depends on what kind of dimension you are using. This one uses 4 spacial dimensions (projected down to 3 dimensions due to stupid limitations of our universe).

Re:I can do it in 1

[Anonymous Coward]

I commend you for your CISC style of cube solving!

Definitions

[Ghoser777]

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

[hobbit]

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

[MillionthMonkey]

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:Definitions

[fmoc-86]

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

Only one move required...

[FoolsGold]

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

There, saved you from another 22 pointless moves.

Re:Only one move required...

[surfchicky23]

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

Re:I have a theory

[Anonymous Coward]

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

Slightly offtopic

[KokorHekkus]

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

[KokorHekkus]

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

Re:Slightly offtopic

[locofungus]

Yes, corners first. I don't know about the same 8 move combination but IMO there are only 8 pieces that aren't obvious how to position.

First you do four corners on a face - anybody can do this without any "method". (at least I could)

Then you position the second four corners and rotate them as necessary - this is more tricky.

Then you position the eight edges on opposite faces (leaving the middle slice unsolved). (How to do this was completely obvious to me, YMMV)

Then you need to position and rotate the remaining four edges - again more tricky.

Finally, you might need to reposition the centres (By default I ignore the four centres on the middle slice and minimize the moves for the edges, sometimes leaving me with a four spot pattern to "solve" at the end)

Tim.

Re:Slightly offtopic

[KokorHekkus]

The eight move permutation I use on a Rubiks cube with the corners done is:

Turn "right side" a quarter turn towards you
Turn "bottom layer" a quarter turn to the left
Turn "right side" a quarter turn away from you
Turn "center layer" a quarter turn to the right
Turn "right side" a quarter turn towards you
Turn "bottom layer" a quarter turn to the right
Turn "right side" a quarter turn away from you
Turn "middle layer" a quarter to the left


Those 8 moves will shift places of 3 edge pieces, the two in the middle layer closest to you and the bottom one furthest away from you. And carefully applied that's all I need, with the minor variation that the center layer turn is either left, right or a half full turn. Of course I actually use other move-patterns as well but they're basically just for speed/convenience.

Re:Slightly offtopic

[SuperMonkeyCube]

Corners first, when initially stumbled upon by accidentally solving the corners, does seem rather obvious. Many of the people that were fast in the early days of cubing were using corners first solutions. Any of us that were trying to make funny patterns on the cube were familiar with moving groups of edges around that didn't disturb the corners. Also, the easiest move to flip edges left everything else undisturbed, and flipped one edge on the top layer and three in the middle layer. (That would be RERERERE.) These things combined to make corners first commonplace.

As someone who still carries a cube around, I would have to say that you can still be well under a minute with a corners first solution, and not have to memorize as many routines (15-20 tops) as someone using the more efficient Fridrich F2L solution (76 much longer routines minimum) not to mention the additional difficulty of having to locate two cubes at a time for corner-edge pairs. This is, as a task, rather like human computing. Do you stick with a short program that's less error prone, or do you write a more complicated one that hogs more memory in the hope of getting it done a few cycles sooner? I'm surprised at how many so-called 'nerds' on this thread disregard the cube as some sort of frustrating toy that can't be done except by paint or sticker removal (especially when disassembly is more reliable :P) instead of wanting to understand the behavior of groups and physically grasping algorithm efficiency. Cudos to KokorHekks for solving it himself!

Re:Slightly offtopic

[Anonymous Coward]

No. I probably bought my cube in 1981 (I still have it), when books became available telling you how to solve it. I considered finding a way to solve the puzzle to be the real puzzle, using a book was cheating. I tried out all kinds of repeating moves that resulted in something useful, like pairs of corners being exchanged for example. The solution I found worked by getting all the edge pieces in place first, and then the corners. I never worried about permutations or obviousness. I found a solution and was happy with it.

Necessary can be zero

[againjj]

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 And of course, this is talking about face turns; the numbers for only quarter turns are higher.

Re:I can answer that!!

[Anonymous Coward]

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

[davidsyes]

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

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

[Anonymous Coward]

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.

Re:LET THERE BE THREE moves... HEHEHE

[Tango42]

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

Brute force

[Tango42]

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

[rokicki]

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

[mdmkolbe]

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

[phliar]

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

[pez]

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

[Myrddin Wyllt]

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.

Re:Hofstadter

[DMUTPeregrine]

Douglas Richard Hofstadter is his name. Not Scott. No idea where pez got that.

Re:Hofstadter

[DerekLyons]

Anyone who has only read GEB is really missing out - both Metamagical Themas and The Minds I are also real mind openers. They take the themes raised in GEB and explore them further.
 
Fluid Concepts and Le Ton Beau De Marot are highly skippable.

Re:Hofstadter

[Cajun Hell]

A real Hofstadter fan/pedant would have complained about the "Hofstadter 1996" knowing it was off by a decade.

Re:Hofstadter

[pez]

Brain fart... of course it is Richard. Must have been too late at night when I wrote that reply.

Easy

[camperdave]

Call me when it's down to 10 moves!

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

Re:Easy

[felipekk]

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

[KDEWolf]

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

Step 3: Profit!

Re:Easy

[impskizzle]

Step 2: Will it blend?

Re:Easy

[harry666t]

2. ???
3. Profit...

Re:Easy

[Jay L]

Drop cube in can of paint.

Paint is so 1987. Sears now sells powder coaters for $150.

There is nothing that can't be improved with a little powder coating. Pencils, silverware, desks...

Re:Easy

[Richy_T]

New toy alert!!!

Slashdot

[mangu]

News for Nerds -> Check

Stuff that Matters -> Whut?

Re:Slashdot

[spydabyte]

I always thought "stuff that matters" was ironic because of the term "news"... hence the "news for nerds".

Re:Slashdot

[niceone]

I always assumed that in this case "Stuff" was a verb.

Do the math, quick!

[HiggsBison]

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!

[MadnessASAP]

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

Re:Do the math, quick!

[Anonymous Coward]

Whoooosh.

You missed the reference a bit.

Heh. As befitting my anonymous coward status,
CAPTCHA: impunity

Re:Do the math, quick!

[Splab]

And you should probably hand in your geek card and go back to literature and get acquainted with The Hitchhikers Guide To The Galaxy.

Re:Do the math, quick!

[something_wicked_thi]

No.

It's 42.

Trust me.

Re:Do the math, quick!

[Anonymous Coward]

On average about 2 stickers are already correct on each side of a cube. 54 - 12 = 42!

(Yes, I know that on average about 1.5 stickers are correct, but that wouldn't fit in with the joke, and no rubik's cube is perfectly random anyway)

Re:Do the math, quick!

[microTodd]

Bravo! Good Sir! Nicely done. Subtle, and only a true fan will catch that awesome reference.

Re:Do the math, quick!

[Anonymous Coward]

Actually 6x9 is 54...

Re:Do the math, quick!

[bkr1_2k]

Seriously? You didn't get that? Credentials officially revoked.

Now back to our regularly scheduled non-RTFA programming.

Ghetttoooo

[billcopc]

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

Recapping what it means

[Anonymous Coward]

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.

Re:Recapping what it means

[Anonymous Coward]

You are correct sir. It is possible however, to memorize a few series of moves to achieve a few stages of completion. Do one side (the top) and the middle row will need the four corner squares to be aligned, as the center squares are fixed-position. To align the middle rows' corner squares you can orient the cube depending on where each piece needs to be moved to and execute a memorized pattern of moves. The bottom row can be solved in a few series of moves than can just be repeated until the desired result is achieved.
http://www.scaredcat.demon.co.uk/rubikscube/the_solution.html
It takes quite a bit more than 18 moves, but only a few minutes. A good time killer waiting for a pot to boil or the five minutes 'till Star Trek comes on.

Cube expert

[extrasolar]

You know, if you want to make faster progress I suggest you consult the experts of all things cube.

Beware

[RomulusNR]

Professor Cooperman will be avenged.

Yeah, but...

[physman_wiu]

...I would like to see someone solve it in 21 moves with only their feet.http://tw.youtube.com/watch?v=pvXXnT35-70

least number of turns != fastest solve time

[Gitcho]

What's interesting to note is that the method for solving the cube in the least number of moves is NOT the fastest - there are very few speedcubers that use this method in competition.

The majority of speedcubers (myself included) use a method developed by Jessica Fridrich over 20 years ago commonly referred to as F2L (first two layers).

It takes quite a few more turns to solve the cube, but when you are executing 4-6 quarter-turns per second it's not speed of turning that slows you down, it's how fast you can recognize your next move.

Re:least number of turns != fastest solve time

[fprintf]

I wanted to become able to solve the cube quickly. Unfortunately the memorization required has left me doing F2L intuitively rather than using preset algorithms. First solving the white cross, then F2L. With repeated practice I can do F2L pretty quickly.

What has me stumped right now is the last layer. Using some slow algorithms I found on the 'Net e.g. FRU'R'U'F or RUR'UR2U'R I can usually get the upper level the same color but without the sides or corners permutated correctly. It is those dang corners - most of the time they are incorrect. 1 in 20 times I get lucky and solve the cube though. :-)

The good thing is that there are tons of beginner algorithms for old guys like me who want to solve the cube in 60 seconds and have no desire to work any faster. It still takes lots of practice, and in my case I haven't memorized enough to do it without looking at a cheat sheet once I get to the last layer.

my best time -1 min

[ami.one]

As a kid my best time was 1 min ! Used to just take off all the stickers on all faces and put them back in correct order. Friends were confused though as to why i want to solve it alone in a room and not in front of them.

Anyone remember Radical Eye Software?

[hoover]

Ah, Tomas Rokicki... running AmigaTeX off two 3,5" floppies and 20 disks, those were good times, good times.

Good Old Days at A&M

[FurtiveGlancer]

I remember "Computer Tom" sitting near the back of the class with headphones on, programming in BASIC on a SHARP. When the prof dared ask Tom a question, Tom invariably got it right and often pointed out a mistake earlier in the problem. I wonder if he recalls the "Nun-inverting" amplifier?

If you read this Tom, hope we didn't take up too much of your valuable programming time and thanks for the VAX account elevation. :)

Not a Proof

[eulernet]

An enumeration is not a proof, since there may be some bug in the program.

Although it's an impressive achievement, this result will only be accepted when someone else will verify this result with a different method.

Maybe I'm just slow...

[Keeper Of Keys]

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

On third reading, I get it. I thought, as presumably did the AC above, that Rokicki had shown that from an arbitrary start position it can always be solved in either 21, 22 or 23 moves.

But I think you mean "it is possible to solve a cube from any arbitrary configuration in no more than N moves, where N is 21, 22 or 23". If it starts out only 1 move away from completion, I don't really just have twiddle it round an extra 20 moves, do I?

Re:Maybe I'm just slow...

[FrangoAssado]

But I think you mean "it is possible to solve a cube from any arbitrary configuration in no more than N moves, where N is 21, 22 or 23". If it starts out only 1 move away from completion, I don't really just have twiddle it round an extra 20 moves, do I?

Yes, you're right, the "no more than" makes it clearer (that's what it was intended to mean). Of course there are configurations that don't need more than N moves (for N < 21), you can make them by starting with a solved cube and make N rotations (as with your 1 move example).

The other cube...

[Anonymous Coward]

Nobody is too smart! Nobody is too slow! Everybody is equal!
http://thepeoplescube.com/red/viewtopic.php?t=64

I am the ghost of Robert Anton Wilson

[Anonymous Coward]

...and I approve of this algorithm!

"Solving the rubik's cube"

[PinkyDead]

I've never heard it called that before.

Be careful, you may go blind.

One more question

[gr8_phk]

Can a face turn be 180 degrees, or is that 2 turns? My guess from a normal person perspective is that a 180 degree turn is one move. The programmer and armchair mathematician in me says that a 180 degree turn is two moves, as it passes through one configuration on the way to another. So what is the generally agreed upon definition of a move?

On a related note, when I was a kid some people thought sliding a middle slice was a move, when it was clear to me that it was really 2 "face turns". From the terminology you use, we seem to agree on that. I just thought I'd mention it.

So Much Brainpower Wasted

[Nom du Keyboard]

So much brainpower spent on trying to figure out a toy.

How Many Moves Is My Solution?

[Nom du Keyboard]

I just take them apart and reassemble them as solved.

What are the "unsolvable" cubes?

[AP31R0N]

"solve any (solvable) Rubik's cube"

Supercomputer?

[slapout]

Supercomputer? I've got a small little book that tells you how to do it. :-)

Here's what you do with a supercomputer.

[blair1q]

The Rubik's cube has a finite number of configurations reachable from the solved configuration using the rules of transformation. Therefore, it is possible by elaborating all of the sequences of transformations until loops are found to create a set of transformation sequences that reaches all possible configurations. The question is, have you found the optimal sequence in every case. The answer is yes if you have enumerated every sequence of shorter length.

So, in order to prove that 23 is the longest distance from a solved state, you have to compute the result of all possible 22-move sequences without reaching the 23-move state.

At any position, you can make one of 9 moves (rotate by 90 degrees any of the three planes in any of the 3 dimensions). So there are 9^22 possible sequences to enumerate.

9^22 is 984,770,902,183,611,232,881.

Hmmmm...tricky...

Of course, you can probably eliminate sequences that loop in fewer than 22 moves by working up from 1, meaning you don't need to revisit with those starting sequences as you go longer. There is where things get elegant.

Anyone have the phone number for Magrathea? I'll be over here doing some designing...

baaah!

[Anonymous Coward]

Time is not a spatial dimension!

Rubik's Cube tournament

[cheroke]

I've seen a movie in the news block couple weeks ago where 9-year kid is beating his adult opponents in the Rubik's Cube tournament. He did it in about 2 min!