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

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

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

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

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.