Home »

2x2x2 Cube

Submitted by B MacKenzie on Sat, 05/17/2014 - 15:19.

I recently added the 2x2x2 cube to my Virtual Rubik app. Playing around with the code I threw together a breadth first god's algorithm calculation using anti-symmetry reduction. This is old stuff but I thought I would post the results just the same.

2x2x2 States At Depth
Depth   Reduced(Oh+)       States
 0             1             1
 1             1             6
 2             3            27
 3             4           120
 4            13           534
 5            35         2,256
 6           126         8,969
 7           398        33,058
 8         1,301       114,149
 9         3,952       360,508
10        10,086       930,588
11        14,658     1,350,852
12         8,619       782,536
13         1,091        90,280
14             8           276
15             0             0

Group Order: 3,674,160

Antipodes:
  1 R R U R F R' U R R U' F U' F' U'

  2 R R U R R F' U R F' R F' U R' F'

  3 R R U R' U F U' R F R' U' R U R

  4 R R U F F R' U' R F' R F' U U F

  5 R R U R' F R R U' R F R' U R R

  6 R R U R R U F U' R F' U R U' R

  7 R R U R R U' R F' U R' U R U U

  8 R U R R F' R F R U' F' U R U' F

» 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.

96 antisymmetries of the void corner cube

Submitted by brac37 on Sat, 09/13/2014 - 14:48.
6 positions on distance 1, that must be QTM. Another argument for this conclusion is that the highest level is 14, not 12.

The 2x2x2 that I know has 12 antisymmetries, of which 6 symmetries. You seem to use 96 antisymmetries. So I think your table is of what I call the void corner cube. Both cubes are in some sense the same, but I prefer some distinction.

But as far as I know, the void corner cube has no antisymmetries. But wait. Two corner cubes with centers are void equivalent, if they are the same up to center permutation. And if you do not use slice moves in their generators, the center permutation by means of slice moves will commute with the generators.

That makes it possible to take inverse, indeed. So the void cube has 96 antisymmetries, of which 48 symmetries, without being a group. That is remarkable.
» login or register to post comments

Antisymmetry and the 2x2x2 cube

Submitted by B MacKenzie on Tue, 09/16/2014 - 16:15.

I got to thinking on this and I decided a more rigorous justification for antisymmetry reduction with the 2x2x2 cube was called for. I worked it through in terms of a coset space of the <R U F L D B> group.

If you model the 2x2x2 cube using the <R U F L D B> group, then the distinct states of the cube map to the right cosets of the 24 element rotation subgroup of the <R U F L D B> group, C. C is the subgroup comprised of the actions of the 24 cubic group rotation symmetries on the identity group element. The 24 elements of a coset, C * g, all represent the same cube state. A cube state is the same regardless of its orientation.

An optimal solution for a group element is a turn sequence which will take it to an element of C. 

 Sg * g1 = c1   c1 ∈ C

The coset element, g1, may be obtained from any member of the coset by applying the appropriate element of C.

 g1 = c2 * g2

 plugging this into the first equation:
 
 Sg * c2 * g2 = c1

 (c2' * Sg * c2) * g2 =  c2' * c1 = c3   c3 ∈ C

Thus one may derive optimal solutions of equal length for all elements of the coset by conjugating the first solution with the elements of C. It follows that all elements of a coset are at the same depth (as they should be since they all represent the same cube state.)

The rotation subgroup, C, is invariant under conjugation by the full cubic symmetry group:

 m' * C * m = C

As I have argued previously this means the coset space may be reduced by the full cubic symmetry group. The coset containing (m' * g * m) is at the same depth as the coset containing g. Now the subgroup C is not a normal subgroup of <R U F L D B>: g' * C * g ≠ C. By the arguments of my previous post this means that the coset space ought not to be reducible by antisymmetry. However, any group element will be at the same depth as its inverse. Since all members of a coset are at the same depth (which is not the case for coset spaces in general) one can say that all element of the coset containing g' will be at the same depth as g. Thus antisymmetry reduction is valid for this coset space although we are not dealing with a normal subgroup.

» login or register to post comments

Your 2x2x2 is not a group

Submitted by brac37 on Fri, 09/19/2014 - 15:26.
Your 2x2x2 is not a group. The void group is not a group either, but the term void indicates specific cosets of the 3x3x3 group. Your group is one generated by six elements (possibly with some commutativity relations, as well as G^4 = 1 for every generator G). But that group in hard to visualize. Whenever possible, I prefer a group like the 3x3x3.

For your 2x2x2, that group is the 3x3x3 with the edge stickers removed, and to get the cosets, you just remove the center stickers as well. But there is more. The invertibility of cosets applies equally well on the void cube /with/ edges. But in order to talk about *the* inverse, you have to apply symmetry reduction with either the whole symmetry set with 48 symmetries of the cube, or the special orthogonal subgroup with 24 symmetries of it.

Indeed, let us have two 3x3x3 positions with generators g1 and g2 respectively. Let C be the subgroup of the 3x3x3 generated by dot effects. I do not say dot permutations, because the frame of my 3x3x3 cannot move, otherwise it would not be a group. Note that for the corners and the edges, dot effects are just orthogonal symmetries applied on all of them.

Then positions g1 and g2 are void-equivalent if g2.c = g1 for some element c of C. Here and below, the group operator is applying a generator of the right factor after one of the left factor, to obtain a generator of the product. Let s be the symmetry that is applied on the corners and edges by c. Now for the inverses g1', g2', c' and s' of g1, g2, c and s respectively, we have

g2' = c'.g1' = (c'.s).(s'.g1'.s).s'

and with applying the symmetry s as a move, we enter the bigger group of oriented 3x3x3 cubes with genuine slice moves. By applying s by way of conjugation, we will not leave the 3x3x3 cube.

But we only use that group in our reasoning. Namely, since c'.s is a genuine center permutation, and s'.g1'.s is static on the centers, both commute. Therefore,

g2' = (s'.g1'.s).(c'.s).s' = (s'.g1'.s).c' = (g1')^s.c'
'
where ^ is conjugation. So g2' lies in the same coset as a certain special orthogonal conjugate of g1'. With sufficient symmetry reduction, you consider both cosets the same, so that there is a unique inverse.

To be complete, let us consider the symmetry reduction as well, say that g2 = g1^s for some symmetry s. Then

g2.c = s'.g1.s.c = s'.g1.(s.c.s').s = (g1.c^(s'))^s

for every element c of C. So symmetry reduction is indeed possible.
» login or register to post comments

Quotient Group

Submitted by B MacKenzie on Sat, 09/20/2014 - 08:26.

Your idea of taking the stickers off of the 3x3x3 edge cubies to get to the 2x2x2 cube got me to thinking about the relationship of the 3x3x3 cube and the 2x2x2 cube. The 3x3x3 cube with indistiguishable edge cubies may be viewed as a coset space of the <R U F L D B> 3x3x3 group. The base subgroup of this coset space is the fixed corners group, which is composed of all elements of the <R U F L D B> group having the corner cubies in the solved state. The states of the 2x2x2 may then be mapped to the left cosets of this subgroup:

g * Se    Where g is an element of the 3x3x3 group and Se 
          is the subgroup of the 3x3x3 group with solved corner cubies.

Now Se is a normal subgroup of the 3x3x3 <R U F L D B> group. This means that its cosets form a mathematical group themselves. Thus the 2x2x2 <R U F L D B> group may be seen as the quotient group of the 3x3x3 <R U F L D B> group and its Se subgroup.

» login or register to post comments

To Group or Not to Group

Submitted by B MacKenzie on Fri, 09/19/2014 - 19:58.

Since the 2x2x2 cube has neither center cubies nor edge cubies I see no reason to include them in a mathematical representation of the 2x2x2 cube. For purposes of discussion consider a facelet representation. There are 24 facelets and 24 facelet slots. A cube state may then be represented as a permutation of these facelets. The R, U, F, L, D, B q-turns may be represented as facelet permutations. The composition of two states is modeled by permutation multiplication. All the states the 2x2x2 cube may be placed in by turning the cube faces may then be modeled as products of the face turn permutations. This set of product permutations forms a mathematical group under permutation multiplication: the <R U F L D B> group.

Likewise, all the products which may be formed from the R, U, F permutations form a mathematical group: the <R U F> group. This group maps to all the states the 2x2x2 cube may be placed in by turning only the R, U, F faces.

Starting with a solved cube the turn sequence (R L') results in a solved cube but rotated 90° about the R/L axis. Similarly, the turn sequence (U D') gives the solved cube rotated 90° about the U/D axis. Recursively forming products from these two generators gives the C subgroup of the <R U F L D B> group composed of the solved cube in all 24 possible orientations. The distinct states of the cube may then be represented as cosets of the C subgroup. As such the distinct states of the 2x2x2 do not constitute a mathematical group but rather a coset space of the <R U F L D B> group.

On the 2x2x2 cube an R turn gives the same cube state as an L turn, the two turns differ only in the orientation of the cube after the turn. Really, R and L are the same turn in terms of the rearrangement of the cubies relative to one another. Likewise, D/D' turns are equivalent to U/U' turns and F/F' turns are equivalent to B/B' turns. Any turn sequence containing L, D, B turns may be transposed to an exactly equivalent turn sequence using only R,U,F turns. It is not a simple 1:1 substitution however. Every time a RUF turn is substituted for a LDB turn the cube is rotated and the subsequent turns must be remapped to the new orientation: Here's my routine for the conversion:

// Normalize the argument
// to a path using only RUF turns

-(NSData *)normalizePath: (NSData *)input
{
    NSMutableData   *output;
    const RM_Turn   *source;
    RM_Turn         turn,
                    *dest;
    CM_SYMTAG       rot,
                    dRot;
    unsigned        n,
                    max;
    
    output = [NSMutableData dataWithLength: [input length] ];
    
    source = [input bytes];
    dest = [output mutableBytes];
    
    max = [input length] / sizeof(RM_Turn);
    
    rot = [cubicGroup identityTag];     // rot keeps track of the reference frame rotation
                                        // produced by transposing LDB turns to RUF turns
                                        // It is assumed the initial reference frame
                                        // is the RUF reference frame
    
    for( n = 0 ; n < max ; n++ )
    {
        // Map each turn to the current reference frame
        turn = [self conjugateOfTurn: source[n] bySymTag: rot ];
        
        // transpose LDB turns to RUF turns. Each transposition rotates the reference frame
        // 90° for subsequent turns.
        // (RM_Turn is an enumeration type and maps to the standard notation as:
        //  Rr = R , Rs = R', Ur = U , Us = U', Fr = F , Fs = F', 
        //  Lr = L', Ls = L , Dr = D', Ds = D , Br = B', Bs = B )
        switch (turn)
        {
            case Lr:
                dest[n] = Rs;
                dRot = [cubicGroup tagForElementNamed: @" x, z,-y"]; // C4x3 (90° cw about the X axis)
                break;
                
            case Ls:
                dest[n] = Rr;
                dRot = [cubicGroup tagForElementNamed: @" x,-z, y"]; // C4x
                break;
                
            case Dr:
                dest[n] = Us;
                dRot = [cubicGroup tagForElementNamed: @"-z, y, x"]; // C4y3 (90° cw about the Y axis)
                break;
                
            case Ds:
                dest[n] = Ur;
                dRot = [cubicGroup tagForElementNamed: @" z, y,-x"]; // C4y
                break;
                
            case Br:
                dest[n] = Fs;
                dRot = [cubicGroup tagForElementNamed: @" y,-x, z"]; // C4z3 (90° cw about the Z axis)
                break;
                
            case Bs:
                dest[n] = Fr;
                dRot = [cubicGroup tagForElementNamed: @"-y, x, z"]; // C4z
                break;
                
            default:
                dest[n] = turn;
                dRot = [cubicGroup identityTag];
                break;
        }
        
        // update the reference frame rotation
        // As we proceed down the sequence we perform a series of nested
        // conjugations by the frame rotations of the previous turns:
        // i.e.  r2' * ( r1' * ( r0' * turn[3] * r0 ) * r1 ) * r2
        // where rn is the frame rotation produced by turn[n]
        // so, one must right multiply to get the correct conjugator
        
        rot = [cubicGroup productOfOperatorTag: rot stateTag: dRot];
    }
    
    return output;
}

Here's the result of this conversion for a couple of turn sequences:

B' R B D D R' B D' B' R B' =
F' U F U U R' U R' U' R F'

L' B' D D L D' L L D' B =
R' U' F F R F' U U F' U

Turn by turn the two equivalent sequences give the same cube state but not necessarily in the same orientation. Since any cube state accessible with a turn sequence using all 12 q-turns may be arrived at with an exactly equivalent sequence of the six <R, U, F> q-turns all cube states represented as cosets in the <R U F L D B> group are represented in the <R U F> group as group elements. Thus the <R U F> group is a complete and robust group representation of the 2x2x2 cube.

Looking at it another way, a C coset contains a cube state in all 24 orientation. One of these will have the DLB cubie in the solved position and orientation. The set of these elements, one from each coset, comprises the elements of the <R U F> group

» login or register to post comments

We say the same things

Submitted by brac37 on Sat, 09/20/2014 - 10:20.
Where you say 2x2x2 facelet slot cube, I say 3x3x3 corner cube. Where I say void reduction, you say making a normal 2x2x2 without static slots for facelets or cubies.

Interestingly, as you point out, the 2x2x2 group cube with one fixed corner may play a crucial role in the implementation. For, you choose the coset representants (elements of 2x2x2 slot = 3x3x3 corner) with a specific corner in solved position. So your routine does the void reduction for generators. An extension of your algorithm with slice turns, to reduce 6 face turns and possibly 3 slice turns to 3 face turns and 3 slice turns, does the job for the full 3x3x3 void cube.

Symmetry reduction is not perfect, i.e. the reduction factor is a little smaller than the number of symmetries. Void reduction is perfect, i.e. the the reduction factor exactly the number of symmetries. You can apply one turn on a coset to get another, although in the coset space, the actual face that connects the cosets by way of a turn is undefined.
But to apply more turns after each other on a coset to get another, e.g. to get an actual generator of the coset, you need to take into account the symmetry effect of previous turns. This is for both symmetry reduction (symmetry conjugation) and void reduction (symmetry multiplication).

So to me, both reductions are cousins of each other. This seems harder if you already specify how the coset representants are chosen, i.e. by fixing the LBD cubie.
» login or register to post comments

Connecting Cosets

Submitted by B MacKenzie on Thu, 09/25/2014 - 13:19.
You can apply one turn on a coset to get another, although in the coset space, the actual face that connects the cosets by way of a turn is undefined.

In the present case when we are dealing with right cosets, one coset connects to another by right multiplying by a turn:

  For two elements of a coset g1 = c1 * g2
  
  C * g1 * t = 
  C * c1 * g1 * t =   Since C = C * c1  by closure of groups
  C * g2 * t

The right products of the elements of a coset with any group element all belong to the same coset. For left cosets the left products all belong to the same coset.

Now if you left multiply a coset element with a turn: 

  C * t1 * g1 =
  C * t1 * c1 * g2 = 
  C * c1' * t1 * c1 * g2 =
  C * t2 * g2         Since a rotational conjugate of a face turn is a face turn.

So if you apply a turn to a coset member there will be a turn which will take a second coset member to the same coset, but not necessarily the same turn. It follows that if you apply all turns to a coset member you get the same daughter cosets regardless of the coset member you choose.

» login or register to post comments

Void Cube

Submitted by B MacKenzie on Sat, 09/20/2014 - 11:10.

Yes, a similar approach does very well for the 3x3x3 void cube. See The Void Cube in GAP.

» login or register to post comments

2 x 2 x 2 Group Model

Submitted by B MacKenzie on Sat, 09/13/2014 - 21:38.

I model the 2x2x2 cube using the <R U F> group. This group maps 1:1 to the distinct states of the cube. If the cube is modeled using the <R U F L D B> group, the group is 24 times larger since each distinct state of the cube occurs in 24 orientations. Note that the <R U F> turn set does not move the DLB cubie. All elements of the <R U F> group have the DLB cubie in its starting position and orientation. Thus the model defines a preferred orientation for each cube state.

A cubic group conjugate of a <R U F> group element is not necessarily a <R U F> group element since the conjugate like as not will not be properly oriented:

m' * <R U F> * m ≠ <R U F>
However, the conjugates may be brought into the <R U F> group by applying a whole cube rotation: 
c * m' * <R U F> * m = <R U F>

Where c is the whole cube rotation which will put the conjugate in the proper orientation. So, using this trick the group may be reduced using the full 48 element cubic symmetry group. And of course there are no issues with using antisymmetry reduction with the <R U F> group.

» login or register to post comments