God's number proven at 20

[Kryptonite]

What about 2x2?

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

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.

Anyone know what available programs can do it?

[Herbert Kociemba]

.

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]

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]

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!

[Whyusosrs?]

http://cube20.org/

Would like alg for super flip in 20 moves. Anyone else have more info on this?

[Ranzha V. Emodrach]

R' U2 B L' F U' B D F U D' L D2 F' R B' D F' U' B' U D'.
It's on the page.

[cuBerBruce]

http://cube20.org/

Would like alg for super flip in 20 moves. Anyone else have more info on this?

R' U2 B L' F U' B D F U D' L D2 F' R B' D F' U' B' U D'.
It's on the page.

No, that's a suboptimal 22-move alg that they showed. Optimal algs can be found here.

Well, actually that alg is optimal in the QTM metric, but not FTM.

[Rinfiyks]

Before you guys start on the 4x4x4 and 5x5x5 I'll guess... 30 and 42.

[irontwig]

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?

[Rinfiyks]

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.