typodupeerror

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

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!"
This discussion has been archived. No new comments can be posted.

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

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

by Anonymous Coward on Thursday June 05, 2008 @07:15PM (#23676023)
"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:Solvable? (Score:3, Insightful)

on Thursday June 05, 2008 @07:38PM (#23676249) Homepage
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? (Score:5, Insightful)

on Thursday June 05, 2008 @07:40PM (#23676265)
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? (Score:3, Insightful)

on Thursday June 05, 2008 @07:41PM (#23676279) Homepage
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:I still can't do it. (Score:1, Insightful)

by Anonymous Coward on Thursday June 05, 2008 @07:46PM (#23676337)
Fuck you crafty man and making me read the whole thing before I realized you suck.
• #### Re:Or... (Score:0, Insightful)

by Anonymous Coward on Thursday June 05, 2008 @08:32PM (#23676743)
I doubt that it is 1 for any arbitrary configuration.
• #### Re:I can always do it.... (Score:4, Insightful)

on Thursday June 05, 2008 @09:02PM (#23676989)
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:18 moves is the limit (Score:0, Insightful)

by Anonymous Coward on Thursday June 05, 2008 @10:04PM (#23677511)
There exists at least one combination that takes at most 0 steps to solve
• #### Re:18 moves is the limit (Score:3, Insightful)

on Thursday June 05, 2008 @10:04PM (#23677513)
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:Or... (Score:2, Insightful)

<harry.maurice.johnston@gmail.com> on Friday June 06, 2008 @12:23AM (#23678471) Homepage
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.)

#### Related LinksTop of the: day, week, month.

Doubt isn't the opposite of faith; it is an element of faith. - Paul Tillich, German theologian and historian

Working...