• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 35,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

23 moves suffice

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,106
Likes
134
Location
Atlanta, Georgia
WCA
2003HARD01
Thread starter #1
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.

No distance 21 positions were found in this search, despite solving a total of more than four million billion cube positions.

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

To prove 22 would require, using this technique, solving somewhere between 1 and 1.5 million cosets. We are investigating refinements to our techniques to reduce the CPU time required.

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

Amazing stuff!

Chris
 
Joined
Aug 29, 2007
Messages
837
Likes
16
YouTube
badmephisto
#3
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.
 

Mike Hughey

Super Moderator
Staff member
Joined
Jun 7, 2007
Messages
9,759
Likes
1,738
Location
Indianapolis
WCA
2007HUGH01
YouTube
MikeHughey1
#5
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).
 
Joined
Mar 23, 2007
Messages
531
Likes
2
Location
Bangalore, India
WCA
2008PUTH01
YouTube
karthikputhraya
#13
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.
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

Premium Member
Joined
Apr 5, 2006
Messages
4,106
Likes
134
Location
Atlanta, Georgia
WCA
2003HARD01
Thread starter #14
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
 
Joined
Mar 23, 2007
Messages
531
Likes
2
Location
Bangalore, India
WCA
2008PUTH01
YouTube
karthikputhraya
#16
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
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.
 

AvGalen

Premium Member
Joined
Jul 6, 2006
Messages
6,857
Likes
87
Location
Rotterdam (actually Capelle aan den IJssel), the N
WCA
2006GALE01
YouTube
arnaudvg
#18
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
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.
http://cubezzz.homelinux.org/drupal/?q=node/view/63
 
Top