# Gear cube extreme can be solved in 25 moves

Write the puzzle as the group <R,F,U,D> where R and F are 180 degree moves. We use a two-phase algorithm to first reduce the state of the puzzle to the subgroup <R3,F3,U,D>, and then finish the solve in the second phase. The subgroup <R3,F3,U,D> is the group of all positions where all of the gears are oriented, because R3 is the same as R' except the gear orientation remains unchanged.

The first phase is easy to compute. There are only 3^8 = 6561 positions because each gear has only 3 different orientations, despite having 6 teeth.

Phase 1 distribution:
```Depth	New	Total
0	1	1
1	4	5
2	8	13
3	78	91
4	102	193
5	1064	1257
6	920	2177
7	3576	5753
8	592	6345
9	216	6561
10	0	6561```
The second phase is harder. The number of positions is 24*8!^2/2 = 19,508,428,800, since it turns out that the permutation of the 3 unfixed edges on the E slice is completely determined by the permutation of the centres. This phase was solved with a BFS and took around 7 and a half hours to complete.

Phase 2 distribution:
```Depth	New		Total
0	1		1
1	12		13
2	98		111
3	774		885
4	5909		6794
5	42535		49329
6	287933		337262
7	1814194		2151456
8	10497612	12649068
9	52654764	65303832
10	231184420	296488252
11	856533794	1153022046
12	2617727430	3770749476
13	5732703244	9503452720
14	7032541792	16535994512
15	2833285424	19369279936
16	139100392	19508380328
17	48472		19508428800
18	0		19508428800```
This gives an upper bound of 9+17 = 26. To reduce this to 25, notice that U and D moves do not affect the orientation of the gears, so that every optimal phase 1 solution will end with some rotation of the R or F face. Now we can check that every one of the 48472 depth 17 positions in <R3,F3,U,D> has a 17 move solution beginning with a rotation of the R or F face. It turns out that all of these positions have a large number of solutions, and in particular, they all have at least one solution beginning with R3. Each of these positions and solutions can be reflected in the plane through LB and RF to get another position which is also at depth 17, and a 17 move solution beginning with F3'. Hence all of these positions have a solution beginning with a rotation of the R or F face, and so we can always force a cancellation between the two phases whenever phase 2 requires 17 moves, giving an upper bound of 25 moves.

The cancellation between phases was Michael Gottlieb's idea, and all the computations were done by me.