Home »

Void cube diameter at least 20 (face turn metric)

Submitted by rokicki on Tue, 01/19/2010 - 20:15.
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.
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

An Observation

Submitted by B MacKenzie on Tue, 01/19/2010 - 22:34.

An observation.

The void positions for the identity cube are the dots pattern cubes, the three "four spot" patterns and the eight "six spot" pattern cubes. These twelve cube states form a mathematical group isomorphic with the tetrahedral pure rotation symmetry group. So, one way to view the void positions derived from a cube state is as the coset of this tetrahedral Rubik's cube subgroup which contains that cube state.

So, really what you're looking at is this coset space, which should be exactly one twelfth of the Rubik's cube space.

» login or register to post comments

Yes, but by "real size" I mea

Submitted by rokicki on Thu, 01/21/2010 - 00:51.
Yes, but by "real size" I mean the number of M-conjugate classes (or M+inv conjugate classes), which is somewhat different.

It's also interesting that all twelve cube states of interest, for superflip, are each exactly eight moves from each other---an equilateral C_12 if you will, and all distance 20 from solved.

In the quarter turn metric, the same symmetry applies but the metric is different. In this metric, optimal solutions are:

U+U+F+U-D+R+U+L+D-R+F-L+D+D+B-U-D+L-D-R-U+L-B+R- (24q*)
U+U+F+U+U+R-L+F+F+U+F-B-R+L+U+U+R+U+D-R+L-D+R-L-D+D+ (26q*)
U+U+F+U-D-F+U-R+D-F+L-U+B+U+R+D-R+L+D+F+R-D-R-D+ (24q*)

which shows the diameter in the quarter turn metric must be at least 24 (and I strongly believe it is exactly 24; there is only one known distance-26 and three known distance-25 positions in the normal 3x3 QTM).
» login or register to post comments

void cube symmetry reduction

Submitted by B MacKenzie on Thu, 01/21/2010 - 10:24.

Let me run this past you.

There is a one to one mapping of the states of the void cube and the cosets of the dots subgroup within the Rubik's cube group. The symmetry reduced size of the void cube space thus equates to the symmetry reduced size of the dots group coset space. A coset may be represented as:

    <D>q   where <D> is the dots group and q is an element of the Rubik group

One may form a symmetry conjugate coset by

    m' ( <D>q ) m          where m is an element of the cubic symmetry group
    = m' <D> m m' q m
    = <D> m' q m           since the dots group is symmetry invariant:  m' <D> m = <D>

Two cosets are symmetry equivalent if a symmetry conjugate of one coset gives the other coset

    <D> m' q m = <D> p

which is to say that if two cube states are symmetry equivalent their dots group cosets are symmetry equivalent. So it seems to me that the void cube space should reduce in concert with Rubik's cube group. Thus the reduced size of the void cube space should be exactly one twelfth the reduced size of the Rubik's cube group. Does this make sense or is there a flaw in my logic somewhere?

The twelve members of dots group are all eight f-turns from one another. This relationship then holds for any coset of the dots group. In the q-turn metric there are two distances, eight or twelve. Two members of a coset will then be either eight or twelve q-turns from one another.

» login or register to post comments

Real space

Submitted by rokicki on Thu, 01/21/2010 - 13:08.
I think you're close, but there's still one issue. A dots group coset can include positions from different symmetry classes.

I mean, let's look at the dots group itself. You have a single identity position, which maps to a single symmetry equivalence set. You have three four-spot positions, all of which map to a single symmetry equivalence set. And you have eight six-spot positions, all of which map to a single symmetry equivalence set. So for this subgroup, you have three symmetry equivalence sets in the normal 3x3, but exactly one void symmetry equivalence set.

But I see no reason your argument should fail to apply to this restricted subgroup of the cube space.
» login or register to post comments

The Void Cube Group

Submitted by B MacKenzie on Fri, 01/22/2010 - 10:18.

The situation you describe points to the flaw in the proposition that the reduced void cube space is one twelfth the reduced Rubik's cube space but for the opposite reason. In order for the proposition to be true each void cube class should expand out to cover twelve Rubik's cube classes. This is the case normally for non-symmetric states. For symmetric states this breaks down since members of the coset may belong to the same equivalence class. As you point out, for the identity cube or the superflip cube the coset contains representatives of only three classes. When this case is expanded it will account for only three Rubik's cube classes rather than twelve. Thus the ratio of Rubik's cube classes to coset classes must be something less than twelve.

Changing the subject a bit, I've been mulling over the problem of how one would model the void cube group. Our dots group cosets in the Rubik's cube group do not form a mathematical group. There is the problem of how one would define the multiplication of two states. The product depends on the relative orientation of the states, which is undefined.

This is similar to the relationship between the corners only group and the 2x2x2 cube. A single state of the 2x2x2 cube is represented by multiple states in the corners only cube. This may be resolved by fixing one cubie in place. The subgroup of the corners only cube group with say the DBL cubie fixed in place perfectly models the 2x2x2 cube.

If one applies this approach to the void cube a problem arises. There are states of the void cube which are not represented in the subgroup of the Rubiks cube group with the DBL cubie fixed in place. This may be illustrated by a L q-turn. The dots group coset of this state does not have a member with the DBL cubie in its pristine state. This is because it requires a 90° rotation to put the DBL back in place and the dots group (which may be viewed as the tetrahedral symmetry operations) does not include 90° rotations. In order to resolve this problem one must expand the parent group to include states with odd position parity. Removing the position parity restriction expands the dots group to the full 24 element cubic group rotation symmetries and now the dots group coset of an L turn has a member with the DBL cubie in its proper state. So, in order to model the void cube we expand the Rubik's cube group to include odd parity states. The void cube group then becomes the subgroup of this expanded Rubik's cube group with the DBL cubie fixed in place.

» login or register to post comments

Void Cube Study

Submitted by B MacKenzie on Tue, 01/26/2010 - 00:16.

Intrigued by the void cube, I've knocked out some code and investigated the void cube group a bit.

I will describe the void cube in different terms than Tom. Start with the 3 x 3 x 3 cube and remove the center cubie stickers. Drill a hole in the bottom of the DLB cubie, insert a 3 or 4 cm rod and glue it in place. Glue the other end of the rod into a base stand. This is the void cube.

With the DLB cubie rigidly held in place one can no longer turn the L, D or B face. What one can do is turn the opposite face together with the adjacent middle slice in the opposite direction. I will use the usual Singmaster description for the cube turns ( R , R' , U , U' , F , F' , L , L' , D , D' , B , B' ) with the understanding that the L, D, B turns mean to turn the other twelve cubies not on that face in the opposite direction. The faces are no longer defined relative to the center cubies as they are unmarked. The U face is now defined as the face facing up on the pedestal mounted cube and so forth. For this reason turn sequences performed on the void cube do not relate in a simple way to turn sequences performed on the standard cube since the relation of the two reference frames to one another changes as the faces are turned. It requires an algorithm which keeps track of this to convert one to the other.

Using a cube model based on the above description I've done a states at depth enumeration out to depth nine: 

    Depth Classes+   Void Cube   Standard Cube(Rokicki)
0           1           1          1
1           1          12         12
2           5         114        114
3          17        1068       1068
4         130        9951      10011
5        1018       92592      93840
6        9204      860852     878880
7       83789     7991856    8221632
8      774323    74114319   76843595
9     7159250   686774712  717789576

The second column lists the equivalence class counts for the void cube under cubic symmetry plus anti-symmetry. Out to depth 3 the element counts are identical to the normal cube. Subsequently, states are encountered which either are duplicates in the void cube and not so in the standard cube, or have shorter depths in the void cube than in the standard cube and the numbers diverge. Still at depth nine the void cube count is a large fraction of the standard count: 96%. Eventually the ratio must diverge more radically since the size of the standard cube group is twelve times that of the void cube group. On reflection, it is to be expected that the bulk of the divergence would be in the fat part of the distribution where the probability of encountering duplicates of previously found states is much greater.

I adapted a cube solver of mine to work with the void cube model. Below are the solutions found by this solver for the dots group coset of a random cube state. Two solutions are given. The first in the reference frame of the void cube model and the second is that same sequence of turns transposed to the reference frame of the standard cube. Note that all the void cube solutions are identical. Since in the void cube model all the cubie states are measured relative to the DLB cubie, all the coset members look the same to the void cube solver. The standard solution sequences are different from one another, but are in fact all symmetry conjugates of one another. They are interconverted by rotating the reference frame. When applied to thier parent cube state, the solutions will take that state to a member of the dots group. 

Cube State 1:  FR FD DL RB FU UR LU LB LF RD BD UB BLU RBU DLB FRU DBR LFU LDF DRF
L' U' F' D' R' U L' U' F D R D' F' D' B' U' D' B R' (void cube)
B' L' D' R' D' L U' F' L B R B' L' B' D' L' R' B L' (standard cube)

Cube State 2:  LU UR FU LB DL FD FR RB BD UB LF RD DRF DBR LFU LDF RBU DLB FRU BLU
L' U' F' D' R' U L' U' F D R D' F' D' B' U' D' B R' (void cube)
F' L' U' R' U' L D' B' L F R F' L' F' U' L' R' F L' (standard cube)

Cube State 3:  DL RB FR FD LU LB FU UR UB BD RD LF DLB FRU BLU RBU LDF DRF DBR LFU
L' U' F' D' R' U L' U' F D R D' F' D' B' U' D' B R' (void cube)
F' R' D' L' D' R U' B' R F L F' R' F' D' R' L' F R' (standard cube)

Cube State 4:  FU LB LU UR FR RB DL FD RD LF UB BD LFU LDF DRF DBR FRU BLU RBU DLB
L' U' F' D' R' U L' U' F D R D' F' D' B' U' D' B R' (void cube)
B' R' U' L' U' R D' F' R B L B' R' B' U' R' L' B R' (standard cube)

Cube State 5:  LF RF RD UF BD LD UB UL DF RU BR BL LUB UFR FUL RDB URB RFD FLD LBD
L' U' F' D' R' U L' U' F D R D' F' D' B' U' D' B R' (void cube)
D' B' L' F' L' B R' U' B D F D' B' D' L' B' F' D B' (standard cube)

Cube State 6:  UB LD BD UL RD RF LF UF BR BL DF RU LBD URB RFD FLD UFR FUL RDB LUB
L' U' F' D' R' U L' U' F D R D' F' D' B' U' D' B R' (void cube)
U' F' L' B' L' F R' D' F U B U' F' U' L' F' B' U F' (standard cube)

Cube State 7:  DF FL RU DB BR DR BL BU FR DL FU LU UBL BRD FDR BUR RUF BDL DFL ULF
L' U' F' D' R' U L' U' F D R D' F' D' B' U' D' B R' (void cube)
L' D' B' U' B' D F' R' D L U L' D' L' B' D' U' L D' (standard cube)

Cube State 8:  BL DR BR BU RU FL DF DB FU LU FR DL ULF RUF BDL DFL BRD FDR BUR UBL
L' U' F' D' R' U L' U' F D R D' F' D' B' U' D' B R' (void cube)
L' U' F' D' F' U B' R' U L D L' U' L' F' U' D' L U' (standard cube)

Cube State 9:  RD UF LF RF UB UL BD LD BL BR RU DF FUL RDB LUB UFR FLD LBD URB RFD
L' U' F' D' R' U L' U' F D R D' F' D' B' U' D' B R' (void cube)
D' F' R' B' R' F L' U' F D B D' F' D' R' F' B' D F' (standard cube)

Cube State 10:  BD UL UB LD LF UF RD RF RU DF BL BR RFD FLD LBD URB RDB LUB UFR FUL
L' U' F' D' R' U L' U' F D R D' F' D' B' U' D' B R' (void cube)
U' B' R' F' R' B L' D' B U F U' B' U' R' B' F' U B' (standard cube)

Cube State 11:  RU DB DF FL BL BU BR DR LU FU DL FR FDR BUR UBL BRD DFL ULF RUF BDL
L' U' F' D' R' U L' U' F D R D' F' D' B' U' D' B R' (void cube)
R' D' F' U' F' D B' L' D R U R' D' R' F' D' U' R D' (standard cube)

Cube State 12:  BR BU BL DR DF DB RU FL DL FR LU FU BDL DFL ULF RUF BUR UBL BRD FDR
L' U' F' D' R' U L' U' F D R D' F' D' B' U' D' B R' (void cube)
R' U' B' D' B' U F' L' U R D R' U' R' B' U' D' R U' (standard cube)

And below are the solutions found by the Kociemba solver for the same dots group coset. Note that the solutions for cube state 4 are the same in both lists. This is the coset member for which the void cube solution is also the solution for the standard cube. 

cube state 1: FR FD DL RB FU UR LU LB LF RD BD UB BLU RBU DLB FRU DBR LFU LDF DRF
U' D R L' D' L' B U L' F' U B R' U' F' U D' R' D F D  (21q*)

cube state 2: LU UR FU LB DL FD FR RB BD UB LF RD DRF DBR LFU LDF RBU DLB FRU BLU
U R F' L F F U' R' U' B' R' U' R' U D F' U B L' D' R  (21q*)

cube state 3: DL RB FR FD LU LB FU UR UB BD RD LF DLB FRU BLU RBU LDF DRF DBR LFU
R' B R L' F D L' D' R U' F D B L' F' U F R F'  (19q*)

cube state 4: FU LB LU UR FR RB DL FD RD LF UB BD LFU LDF DRF DBR FRU BLU RBU DLB
B' R' U' L' U' R D' F' R B L B' R' B' U' R' L' B R'  (19q*)

cube state 5: LF RF RD UF BD LD UB UL DF RU BR BL LUB UFR FUL RDB URB RFD FLD LBD
U R' B' R D B R' F L D' L F' L' D D F L' B' L' U L  (21q*)

cube state 6: UB LD BD UL RD RF LF UF BR BL DF RU LBD URB RFD FLD UFR FUL RDB LUB
U B' D' R' U' R' D L F L' D L' F' L' U U D D L F' L'  (21q*)

cube state 7: DF FL RU DB BR DR BL BU FR DL FU LU UBL BRD FDR BUR RUF BDL DFL ULF
U R' U B' R R B D R' L L U R' U' F R L' U F' R F  (21q*)

cube state 8: BL DR BR BU RU FL DF DB FU LU FR DL ULF RUF BDL DFL BRD FDR BUR UBL
L' U' L U' R F' B' R' D F U' L F' L D' F' R B R  (19q*)

cube state 9: RD UF LF RF UB UL BD LD BL BR RU DF FUL RDB LUB UFR FLD LBD URB RFD
U D B' U' L' F' B R L' B' L U U F D R' L' F L' B R'  (21q*)

cube state 10: BD UL UB LD LF UF RD RF RU DF BL BR RFD FLD LBD URB RDB LUB UFR FUL
U L B R' B' L' U B' R B' L' U' L U F' U' F' D F'  (19q*)

cube state 11: RU DB DF FL BL BU BR DR LU FU DL FR FDR BUR UBL BRD DFL ULF RUF BDL
U R' D' R F' B' R F' L U D' B' R B U F U' R U D' R'  (21q*)

cube state 12: BR BU BL DR DF DB RU FL DL FR LU FU BDL DFL ULF RUF BUR UBL BRD FDR
U' R R F' L B R' L' U' F' B' L' B D B' U D' L' D B U  (21q*)

Reassured by the above and similar results that the model works as expected I solved a set of 115 random cubes: 

    Depth Count Normalized
 18     8      7.4%
 19    39     32.0%
 20    46     42.6%
 21    22     18.0%
The second column gives the raw counts of the cubes with solutions of that length. The set of data is skewed toward odd length solutions and the normalized column gives the distribution normalized to a 50:50 ratio of odd to even turn parity cubes. Although 115 data points are a bit scanty, it appears that the average solution length for the void cube is only about one q-turn less than that of the standard cube.

» login or register to post comments