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

God's number proven at 20

Rinfiyks

Member
Joined
Mar 31, 2010
Messages
182
Location
York, United Kingdom
YouTube
Visit Channel
On to 4x4! ;)

Edit: This isn't serious. Not at this point in time, at least.

What about 2x2?

I'm wondering if it's a coincidence how there is exactly 20 pieces (12 edges and 8 corners.) This is excluding the core but that doesn't change position.

I wonder if God's Number for 2x2 would be 8 moves.

Anyway, this is amazing. :)

Because the 2x2x2 has so little permutations, it can easily be brute forced. Here's a table. God's number is 11 for a 2x2x2.
 

mrCage

Member
Joined
Jun 17, 2006
Messages
655
Exactly how many positions are of maximum distance from solved? And are all these symmetrical positions??

Per
"Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are."

If there was an exhaustive search that number should be known. Or could have easily been known if implemented;) Oh well, my main concern was the second question...
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
But there wasn't really an exhaustive search. They didn't bother to optimize solutions because they just needed to show every position could be done in 20 or fewer moves. (As they said they could analyze 2 million positions optimally per second, but prove 1 billion positions to have a solution of 20 or fewer moves, it would probably have taken some decades at Google's server farm to compute optimal solutions for everything. That is, 17500 computer-years.)
 

Zarxrax

Member
Joined
Jan 7, 2009
Messages
1,282
Location
North Carolina
Now that they know which solutions need 20 moves, they could take a look specifically at those, and try to reduce the numbers... right?
 

Kabuthunk

Member
Joined
Feb 25, 2010
Messages
47
Location
Winnipeg, MB
YouTube
Visit Channel
This is awesome. Although on the cube20 site, we can't use the numbers at the bottom to find the 'average' number of moves needed to solve, since they stated on the page that they didn't "optimally" solve each position, just found a solution of 20 or less.

But yeah... I'm surprised there's still well over a hundred million (at least 300 mil on the site, but not 'optimally' solved) that need a full 20 rotations.

Although I'm curious how they came to their conclusion that "FU-F2D-BUR-F-LD-R-U-LUB-D2R-FU2D2" was the hardest solve for the computers.
 

hawkmp4

Member
Joined
May 17, 2008
Messages
1,395
Now that they know which solutions need 20 moves, they could take a look specifically at those, and try to reduce the numbers... right?

No need to, really- there are some positions that can't be solved in any less than 20 moves. 20 is the lowest upper bound we'll ever have.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Exactly how many positions are of maximum distance from solved? And are all these symmetrical positions??

Per
"Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are."

If there was an exhaustive search that number should be known. Or could have easily been known if implemented;) Oh well, my main concern was the second question...

The number of symmetric positions that require 20 moves to solve is exactly 1,091,994 (source: http://kociemba.org/math/c1.htm). All the rest of the known 20f* positions are unsymmetric. (Some undoubtedly have symmetry in edges only or corners only.)

A list of some of the known 20f* positions can be found here. This list only includes 1 position for each set of positions that are equivalent with respect to symmetry & antisymmetry.

I understand the group is thinking about the creation of a BOINC project to get the exact number of positions at each distance from solved. That may not happen for awhile, though.

My raw video of the announcement at US Nationals is embedded here.
 
Last edited by a moderator:
Joined
Nov 29, 2008
Messages
214
.

Although I'm curious how they came to their conclusion that "FU-F2D-BUR-F-LD-R-U-LUB-D2R-FU2D2" was the hardest solve for the computers.

For a coset of the subgroup H=<U,D,R2,L2,F2,B2> which has about 20 billion elements we generated in principle (because we need only one bit per element) the optimal solutions for all elements of this coset which have <=15 moves and eventually a fraction of all elements which have 16 moves. Appending now 5 moves (15) or 4 moves (16) only from subgroup H nonoptimal-solutions for almost all other elements of the coset are generated. This reminds in some way on the two-phase algorithm and there is indeed a close connection to the method.

Those elements which cannot be solved in this way are in a certain sense hard and are solved via the two-phase algorithm one by one. The longer phase 1 has to be, the harder the positions are. The position above needs 18 moves in phase 1 and has only 2 moves in phase 2 (U2D2). Try for example Cube Explorer (though a faster version of the two-phase alg developped by Tom Rokicki was used for the computations) and it will take some time to find the solution.

This explanations is a bit simplified but gives almost the right picture.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
For a coset of the subgroup H=<U,D,R2,L2,F2,B2> which has about 20 billion elements we generated in principle (because we need only one bit per element) the optimal solutions for all elements of this coset which have <=15 moves and eventually a fraction of all elements which have 16 moves. Appending now 5 moves (15) or 4 moves (16) only from subgroup H nonoptimal-solutions for almost all other elements of the coset are generated. This reminds in some way on the two-phase algorithm and there is indeed a close connection to the method.

Aha! I had been wondering exactly how you quickly computed solutions over an entire coset. This is a clever way to do it.
 

badmephisto

Member
Joined
Aug 29, 2007
Messages
836
YouTube
Visit Channel
This is great news! Huge thanks to Google for sponsoring this, wow.

I always thought it should be 20 only because of symmetry arguments: the superflip is 20... In my mind the entire state space is like a diamond with one vertex the solved position, and the opposite vertex the superflip. Of course, there are MANY other positions with 20 moves, maybe these are some other verteces of this high dimensional diamond :)
or something.

awesome news!
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Last edited:

Rinfiyks

Member
Joined
Mar 31, 2010
Messages
182
Location
York, United Kingdom
YouTube
Visit Channel
Before you guys start on the 4x4x4 and 5x5x5 I'll guess... 30 and 42.

That sounds way low, as the 4x4x4 has more than twice the number of pieces than the 3x3x3. If I would guess the 4x4x4 would be closer to 40 moves. Does anybody know upper and lower bounds of the 4x4x4?

If you do 10 inner+outer face scramble moves, that messes up the 2x2 centres and the edges, then you have another 20 outer face only moves for the edges and corners, I don't think it should be much higher than 30.
 
Top