# Void cube diameter at least 20 (probably 20)



## rokicki (Jan 20, 2010)

The void cube is the 3x3 without centers. For every legal 3x3 void position, there are 12 possible ways the centers can be inserted to yield a legal 3x3 cube position. (Pick any of the six colors for the top, then pick one of the adjacent four colors for the front; half of the time the result will have the wrong axis parity).

The "superflip" void position has a distance of 20. This can be shown by computing the optimal solution for all 12 axis insertions in the 3x3 cube; this yields only three unique positions (mod M), and all three have a distance of 20.

U1F1U2F1L2B1U2F1L3R3F2D1R2U2L2B1F3L1F2D1 (20f*) //superflip
D1L2F2R2B3D2L1R1U3R2U3F2D3R2U3B3F3D2R3U3 (20f*)
D1R2D2B3F1L1D3B1L2B2U1R2D1L2B2D2B3U2R2U3 (20f*)

Therefore the void cube has a Cayley graph in the half turn metric with a diameter of at least 20.

This is at present the only known distance-20 position on the void cube. I've evaluated my 84,161 unique-mod-M distance-20 positions in the 3x3 and found that there is no other distance-20 position in this set such that all of its legal axis rotations are still in this set. Since this set of 84,161 is of course far from complete, this does not mean there is not another distance-20 position in the void cube (or even possibley a distance-21 or greater position).

The real state space of the void cube is approximately 12x smaller than that of the normal 3x3; it may be substantially easier to prove a diameter of 20 for the void cube than it is for the normal 3x3.


----------



## meichenl (Jan 21, 2010)

Rokicki,

I'm not familiar with what's meant by "mod m". Are you referring to the cosets of the group generated by the M slice turn? Or the action of that M slice turn on the centers? Could you give an example of two positions that are equivalent mod M? Why do you consider these particular cosets?


----------



## jaap (Jan 21, 2010)

It simply means the positions are unique up to cube rotations (or recolouring) and reflections. It has become fairly standard in cube theory terminology to use C for the group of cube rotations and M for the group of rotations and reflections.


----------



## meichenl (Jan 21, 2010)

got it. thanks, Jaap.

So, Rokicki, how did you find these 84,161 positions?


----------



## rokicki (Jan 21, 2010)

*Seeking 20f* positions*

A substantial fraction (32,625) of the 20f* positions were found by Silviu Radu and Herbert Kociemba in their exhaustive exploration of all symmetrical positions; see

http://kociemba.org/symmetric2.htm

http://cubezzz.homelinux.org/drupal/?q=node/view/63

For almost all the remainder, I took the following steps.

First, I defined the notion of a "canonical sequence" of generators, which is a sequence for which adjacent commuting generators always occur in a specific order. For instance, U before D; in a canonical sequence a twist of U must never directly follow any twist of D.

Next, I wrote a small program that computed how many canonical sequences there were, that led to any position in the Kociemba subgroup (that is, the subgroup generated by {U,F2,R2,D,B2,L2}). This was a pretty simple dynamic programming problem, but took a fair amount of memory since there are about 138M positions (when you combine the ones that are symmetry-equivalent).

I then sorted the list of positions according to the count of distance-19 canonical sequences that led to that position, fewest sequences first. The cosets of these positions were the cosets likely to include the highest number of distance-20 positions.

I have been running the cosets of these positions, exhaustively, for a few weeks now, and have run about 130 of them. This is the primary source for the remaining distance-20 positions. On an i7-920, I can run about three of these cosets a day; on a Q6600 I can run about one. My i7-920 is busy right now on another project, so only the Q6600 is still doing this.

Each coset I run gives me somewhere between 100 and 400 new symmetry-unique distance-20 positions, typically.


----------

