God's number proven at 20

[irontwig]

On to 4x4!

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

What about 2x2?

http://www.jaapsch.net/puzzles/cube2.htm

[aronpm]

On to 4x4!

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

What about 2x2?

I thought that was already done, and it was 11.

EDIT: Ninja'd.

[Rinfiyks]

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]

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]

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]

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]

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.

[Bryan]

Now that they know which solutions need 20 moves, they could take a look specifically at those, and try to reduce the numbers... right?

All you need is one solution that can't be reduced, and they say they have those.

[hawkmp4]

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]

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.