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

Three Million Randomly Selected Positions, Optimally Solved

rokicki

Member
Joined
Oct 31, 2008
Messages
270
Using the Mersenne Twister pseudorandom number generator, I picked out
three million cube positions. I then optimally solved each of these in both
the quarter turn metric and half turn metric. From this data, I was able
to calculate an approximate distance distribution, along with confidence
intervals.

All the data is at

http://cubezzz.dyndns.org/drupal/?q=node/view/232

I can make the actual positions and solutions available if anyone is
interested.

I plan to release the actual code as well, but it still needs some additional
documentation.

-tom
 

rokicki

Member
Joined
Oct 31, 2008
Messages
270
Fast machine

I got a new, faster machine.

On this machine I can optimally solve positions in the QTM at a rate of about 6 per second, and in the HTM at a rate of about 3.4 per second.

So in total it took about 16 days to run.

And yes, visualization would be nice. I should use the google graph tools for that; they are pretty cool.

I'm running 100 random cosets now in the QTM and the HTM to try to get some estimates for the upper tail of the distribution. I am nearly positive that God's number in the QTM is 26, since only one position is known to be at that distance, and the only known distance-25 positions are its neighbors, and since I've conducted (separately) an intense search for other deep positions in the QTM and found none of distance greater than 24.

It appears that distance-24 positions in the QTM do exist in some reasonable quantity but that they are significantly more rare than distance-20 positions in the HTM.

So the "tail" in the QTM is quite dramatically different from the tail in the HTM.

Part of that is due to the fact that the QTM is bipartite and the HTM is not.

I believe that the *only* distance-26 position in the QTM is the one known.
 

Erzz

Premium Member
Joined
Sep 9, 2010
Messages
676
Location
Canada
YouTube
Visit Channel
is it the superflip?
According to this, superflip is 24 QTM.
Also on that page, "No position has ever been found which requires more moves than this, so many people believe that 20 moves is in fact the maximum number of moves that any 3x3 pattern could take to solve." This should probably be changed now that it has been proven.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
According to this, superflip is 24 QTM.
Also on that page, "No position has ever been found which requires more moves than this, so many people believe that 20 moves is in fact the maximum number of moves that any 3x3 pattern could take to solve." This should probably be changed now that it has been proven.
Nope...20 moves HTM is the most ever needed.
Nope...Erzz meant that phrases such as "No position has ever been found" and "many people believe" are now outdated since we now know the exact number.
 
Top