# Odd Permutations of the Cube Shape of Square-1

The method I used was suggested by Tom and Silviu's coset searches for
the Rubik's Cube: Starting from a cube-shaped, *odd*-parity
position of Square-1, an iterated depth-first search was made for
all *even*-parity cube-shaped positions, with the search being
pruned on [shape]x[parity].

The calculation was cut short after about 3 weeks, part-way through the depth-29 search, and the 3067 positions left at that stage were finished off in 3 days using my optimal solver:

depth unreduced reduced:s reduced:a 17 16 4 3 18 432 108 59 19 4780 1215 645 20 37260 9529 4851 21 212692 53905 27278 22 1213286 304010 152652 23 5934686 1484376 744119 24 22194238 5550768 2780705 25 70670864 17676599 8851358 26 205434270 51371259 25713697 27 349774818 87457479 43776760 28 149587160 37408752 18740768 29 7770388 1945834 980340 30 16298 4252 2375 31 12 6 6 -------------------------------- 812851200 203268096 101775616

From the table it can be seen that there are disproportionately large numbers of symmetric and antisymmetric positions at large depths. All six positions at depth 31 have one symmetry (besides the identity) and two antisymmetries. Four of the depth-31 positions are self-inverse, so that the antisymmetry is trivial.

Just as for the coset searches on the Cube, God's Algorithm for Square-1 can, in principle, be found by repeating the calculation for different starting positions: all the symmetrically distinct shape-parity combinations, in this case. In practice, however, this approach would take far too long. I've done some trial runs starting from the even-parity cube-shaped position and estimate that the search would take many months to reach depth 24 on my home PC, which (given the distribution estimated by solving random positions of this type) is probably the earliest that the calculation could be turned over to the optimal solver. The difficulty with that particular case is that it is already one of the target states, so that one gets relatively little benefit from the shape-parity pruning.

Nevertheless, it might be worth starting from some other shape, if we
just want to try to improve on the 31-turn lower bound. The results
from Mike Masonjones' complete twist-metric calculation of God's
Algorithm show that there are several shapes with a relatively high
proportion of positions that need 13 twists. These shapes may be a
promising starting point for the search, as the 13-twist positions
will need *a minimum* of 25 turns, and so might be
expected to lie relatively deep.

***************

Mike Godfrey