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

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?

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

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

[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:Mastermind

[Anonymous Coward]

The Maximum needed is actually 6

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