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

Posted
by
timothy

from the at-this-rate-one-will-soon-be-enough dept.

from the at-this-rate-one-will-soon-be-enough dept.

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!"*
## I still can't do it. (Score:5, Funny)

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

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

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

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

## Re: (Score:2)

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

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. (Score:5, Funny)

Please, disregard the previous sentence.

Please, disregard the previous sentence.

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

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

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. (Score:4, Funny)

## Re: (Score:2)

## Re: (Score:2)

Rich

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

## Re: (Score:2)

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

## Easy (Score:5, Funny)

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

## Re: (Score:2, Funny)

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

## Re: (Score:3, Funny)

Drop cube in can of paint.Paint is so 1987. Sears now sells

powder coatersfor $150.There is

nothingthat can't be improved with a little powder coating. Pencils, silverware, desks...## Re: (Score:2)

## my best time -1 min (Score:5, Funny)

## "Solving the rubik's cube" (Score:2)

Be careful, you may go blind.

## That's quick (Score:5, Funny)

## Re: (Score:3, Funny)

Try spray paint.

## Re:That's quick (Score:5, Funny)

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: (Score:2)

## Re:That's quick (Score:5, Funny)

## Do the math, quick! (Score:5, Funny)

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: (Score:2)

## Re: (Score:2)

## Re: (Score:3, Funny)

It's 42.

Trust me.

## Re: (Score:2)

Now back to our regularly scheduled non-RTFA programming.

## Re: (Score:2)

## I can always do it.... (Score:5, Funny)

## Re:I can always do it.... (Score:4, Insightful)

## Re: (Score:2)

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: (Score:2)

## Re: (Score:2)

## Or... (Score:5, Insightful)

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... (Score:5, Funny)

## Re: (Score:2)

## Re: (Score:2)

## Re: (Score:2, Informative)

## Re: (Score:3, Informative)

Well, he

didsayanyarbitrary 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

anyarbitrary configuration in N moves, where N is 21, 22 or 23 (it's not yet known which).## Re: (Score:2, Insightful)

## Maybe I'm just slow... (Score:2)

The point being: it is possible to solve a cube from

anyarbitrary 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 thanN 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: (Score:2)

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

## Re: (Score:2)

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

## 18 moves is the limit (Score:4, Informative)

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

## Re: (Score:2, Informative)

It should be 2(3^3)/3

## Re:18 moves is the limit (Score:5, Informative)

## Re: (Score:2)

## Re: (Score:3, Insightful)

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: (Score:2)

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

Layne

## Re: (Score:3, Interesting)

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

## Re: (Score:2)

## Re: (Score:2)

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

## Solvable? (Score:5, Interesting)

## Re:Solvable? (Score:5, Funny)

## Re:Solvable? (Score:5, Insightful)

## Re:Solvable? (Score:4, Funny)

reallyannoy me. They were quite disappointed when I solved the cube, as the second flip perfectly counteracted the effect of the first.## Re: (Score:3, Insightful)

## Re: (Score:2)

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: (Score:2)

## Re: (Score:2)

wasvery 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: (Score:2)

## Re: (Score:3, Funny)

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

## Re: (Score:2)

## Re: (Score:2, Informative)

## Re: (Score:2)

## Re: (Score:3, Insightful)

## Definitions (Score:2)

## Re: (Score:2)

Rubik'scubes. 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 ma## Re: (Score:2)

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... (Score:3, Funny)

2. Let Dry

3. PROPHET

## I can do it in 2... (Score:4, Funny)

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

## Re: (Score:2)

## That's great. (Score:2)

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

## Mastermind (Score:2)

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

## but rubik's hypercube remains unsolved (Score:2)

rubik's hypercube has me stumped

## Re: (Score:2)

## Only one move required... (Score:5, Funny)

There, saved you from another 22 pointless moves.

## Slightly offtopic (Score:3, Interesting)

So I'm curious if anyone else has experienced this as being the

obviousbut not perfect solution?## Re: (Score:2)

## Re: (Score:2)

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 remai

## Re: (Score:2)

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 th

## Re: (Score:2, Interesting)

## Brute force (Score:2)

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

## Re: (Score:2, Informative)

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: (Score:2)

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: (Score:2)

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

usinga brute-force solver, but writing one would be interesting. Give it a try.## Hofstadter (Score:3, Informative)

## Re: (Score:2)

GEBis really missing out - bothMetamagical ThemasandThe Minds Iare also real mind openers. They take the themes raised inGEBand explore them further.Fluid Concepts

Le Ton Beau De Marotare highly skippable.## Re: (Score:2)

realHofstadter fan/pedant would have complained about the "Hofstadter 1996" knowing it was off by a decade.## Re: (Score:2)

## Recapping what it means (Score:5, Informative)

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.

## One more question (Score:2)

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 terminolo

## Cube expert (Score:2)

## Good Old Days at A&M (Score:2)

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.

## So Much Brainpower Wasted (Score:2)

## How Many Moves Is My Solution? (Score:2)