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

I still can't do it.

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

Re:I still can't do it.

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.

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.

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.

Yes, but does the window run Linux?

Please, disregard the previous sentence.

Please, disregard the previous sentence.

Re:I still can't do it.

This post intentionally left blank

Re:I still can't do it.

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.

Easy

Call me when it's down to 10 moves!

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

my best time -1 min

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.

That's quick

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

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

I just buy a new one.

Do the math, quick!

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.

I can always do it....

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

Or...

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

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

18 moves is the limit

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

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.

Solvable?

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?

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?

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.

Only one move required...

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

There, saved you from another 22 pointless moves.

Recapping what it means

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.

I can do it in 2...

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

Re:LET THERE BE THREE moves...

3. PROPHET

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