From:

Subject:

I have made my program a bit faster. While previously the best I found for

superflip was a 21 move solution (even after 10 hours computation time,

actually the solution was found after about 30 minutes), I have now a 20

move solution, found after only 15 minutes:

Superflip: (13+7=20): F B U^2 R F^2 R^2 B^2 U' D F U^2 R' L' U B^2 D R^2 U B^2 U

Some more information. First a short recap. Phase1 brings the cube in

the group generated by [F^2,R^2,B^2,L^2,U,D], phase2 brings him back

to start. Phase 1 searches in the space generated by the three (orthogonal)

coordinates:

Twist (2187 entries), flip (2048 entries) and slice-edge-cube placing (495

entries).

Phase 2 searches in the space generated by the three (non-orthogonal)

coordinates:

Permutations of corner cubes (40320 entries), permutations of edge cubes

not in the middle slice (40320 entries) and permutations of the middle

slice edge cubes (24 entries).

While Kociemba originally did tree pruning based on the minimal number of

moves needed along single coordinates, I now use pairs of coordinates

(except that in phase 2 the 40320*40320 pair is not used of course).

This is part of the speed-up. (Another part is that I do now disallow

successive moves of a single face, three or more consecutive moves of

opposite faces, and a move of an opposite face if the current face moved

is B, L or D.)

Program details: the program starts with phase1 allowing for succesively

1, 2 etc. until a maximal number of moves. As soon as phase1 hits a

solution phase2 is called, again with a maximum number of moves starting

at 1. This means that if the program runs long enough it will ultimately

find the shortest solutions (phase 1 might just solve it!). But that wil

take a long time (of course). For the superflip, the program has now

checked all phase1 solutions of upto 12 moves and is busy with 13. It

found 792256 solutions of 12 moves (and that in less than 10 minutes)!

Some additional data about minimal paths along coordinates:

Phase 1:

twist: 6

flip: 7

choice: 5

twist+flip: 9

twist+choice: 9

flip+choice: 9

Phase 2: corners: 13 edges: 8 slice edges: 4 corners+slice: 14 edges+slice: 12

Based on this I expect a maximal distance in phase 1 of about 10/11, and

in phase 2 of about 16/17.

dik

--

dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland

dik@cwi.nl