Odd Permutations of the Cube Shape of Square-1

Results are presented from an exhaustive search on the odd permutations of Square-1 in its solved shape. A maximum of 31 turns (U, D and /) are needed to solve these positions, which may be a new lower bound on the length of God's Algorithm for Square-1, in this metric.

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