# 23 moves suffice



## cmhardw (May 1, 2008)

> After solving more than 200,000 cosets, we have been able to show that every position of Rubik's cube can be solved in 23 or fewer face turns.
> 
> The key contribution for this new result was 7.8 core-years of CPU time contributed by John Welborn and Sony Pictures Imageworks, using idle time on the render farm that was used for pictures such as Spider-Man 3 and Surf's Up.
> 
> ...




Quoting from this site: http://cubezzz.homelinux.org/drupal/?q=node/view/117

Amazing stuff!

Chris


----------



## Dene (May 1, 2008)

Slowly getting down to 20...


----------



## badmephisto (May 1, 2008)

If someone could turn this into a distributive computing project, I know many people would help out.
This is like a perfect problem for distributive computing, where each subproblem is completely distinct from others.


----------



## ShadenSmith (May 1, 2008)

I'd definitely help if we turned it into a distributive computing project.


----------



## Mike Hughey (May 1, 2008)

I thought this already was a distributed computing project. After all, it does say:



> The same techniques for the proof of twenty-five moves were used, just on many more computers.



I also thought I remembered reading before (when they did the twenty-five moves) that it was distributed. On the other hand, I don't know how to get your computer hooked up to help with the load. And I'm guessing it would take a LOT of computers to equal the processing power of the Sony render farm (many more times the number of computers of all the people on this forum, anyway).


----------



## brunson (May 1, 2008)

I have several computers I could throw at it, but the software has to run under Linux.


----------



## cuBerBruce (May 3, 2008)

brunson said:


> I have several computers I could throw at it, but the software has to run under Linux.



Tom's paper said the program needs more than 4.7GB of memory. It probably needs to run on a server-class machine.


----------



## badmephisto (May 3, 2008)

by the way I'm convinced the answer is 20. The superflip is waaaay too symmetrical and pretty for this not to be true.


----------



## fanwuq (May 4, 2008)

what is the highest optimal move count for any known position?


----------



## Johannes91 (May 4, 2008)

fanwuq said:


> what is the highest optimal move count for any known position?


20


----------



## brunson (May 4, 2008)

fanwuq said:


> what is the highest optimal move count for any known position?



According to Chris' original post in this thread, it's 23. That's what we're discussing.


----------



## Johannes91 (May 4, 2008)

brunson said:


> fanwuq said:
> 
> 
> > what is the highest optimal move count for any known position?
> ...


There are no known positions that require more than 20 moves.


----------



## Karthik (May 4, 2008)

brunson said:


> fanwuq said:
> 
> 
> > what is the highest optimal move count for any known position?
> ...


No 23 is not optimal.Those which have been solved in 23 moves may have lesser optimal solutions.
The superflip is known to have an optimal move count of 20.No state has been discovered to have a higher optimal move count.


----------



## cmhardw (May 4, 2008)

They proved that every state is reachable in 23 or fewer moves. No state is known that requires more than 20, but *if* one exists it's solvable in 23 or fewer moves.

Chris


----------



## AvGalen (May 4, 2008)

Some more optimality facts:

The superflip is not the only position that requires 20 moves.

Some positions that require 20 moves are not symmetrical.

All positions that are symmetrical have been already proven to require 20 moves or less


----------



## Karthik (May 5, 2008)

AvGalen said:


> Some more optimality facts:
> 
> The superflip is not the only position that requires 20 moves.
> 
> ...


Can you give some examples?I am interested to know.Not generalising though but I thought a maxima/minima would occur when there is a symmetry.


----------



## brunson (May 5, 2008)

Johannes91 said:


> brunson said:
> 
> 
> > fanwuq said:
> ...



Ah, I misunderstood the question.


----------



## AvGalen (May 5, 2008)

Karthik said:


> AvGalen said:
> 
> 
> > Some more optimality facts:
> ...


http://cubezzz.homelinux.org/drupal/?q=node/view/63


----------

