Some observations on the Rubik's Cube Group, its sub-groups and solution algorithms.

Some observations on the Rubik's Cube Group, its sub-groups and solution algorithms.

When approaching the problem of auto-solving Rubik's cube in my Virtual Rubik program I chose to proceed in a three step process by first solving a 2 x 2 x 2 block using turns of all six faces. Then using turns of the three faces not intersecting the solved block, the block is extended to a 3 x 2 x 2 block, leaving two faces unsolved. And finally the last two faces are solved using just turns of those two faces.

As such one is concerned with three groups:

Rubik's Cube Group: 43,252,003,274,489,856,000 elements
Three Face Group:          170,659,735,142,400 elements
Two Face Group:                     73,483,200 elements

and the coset spaces for moving from the parent group to its sub-group:

Rubik/Three Face:      253,440 cosets
Three Face/Two Face: 2,322,432 cosets

In this way the daunting task of searching for a solution in the huge Rubik's Cube Group is reduced to successively searching the much smaller coset spaces. Without going into details about pattern databases, pruning tables and such, solving a problem state involves exploring the binary tree starting from the identity state until the problem state (or for coset searches a member of its coset) is found. First apply each of the allowed turns, then all combinations of two turns, then three turns, etc. The performance of such a search is related to the number of new states found at each level of the search:

The data for the Rubik/Three Face, the Three Face/Two Face and the Two Face Group distributions are based on so called God's algorithm calculations in which the groups have been completely enumerated. The distributions for the Rubik's Cube group and the Three Face Group are based on optimum solutions found for randomly generated cubes. The Three Face Group data comes from my own cobbled together three face solver and are unconfirmed.

Looking at the data, it takes on average seven turns to get from the Rubik's Cube Group into the Three Face Group, eleven turns to get from the Three Face Group into the Two Face Group and then twenty turns to get to identity within the Two Face group. All told this gives an average solution of 38 turns (actually 37.8 found experimentally solving randomly generated cubes). It is in a way ironic that the efforts used to funnel the cube into more computationally tractable groups gets one no closer to the solution in terms of the number of turns. An arbitrary member of the Rubik's Cube Group is about 21 q turns from solved, a member of the Three Face Group is about 22 q turns(using the reduced turn set) from solved and a member of the Two Face Group is about 20 q turns from solved.

One final observation in passing. I am struck by the similarity of the above distributions to population dynamics. In many situations populations initially grow exponentially until the available resources begin to be depleted. The population then levels off and finally crashes precipituously as the resources are exhausted. One sees the same lop-sided curves. The resource being exhausted here is the parameter space I would say.