Antisymmetry and the 2x2x2 Cube

Someone on the Yahoo forum asked about how to do a 2x2x2 God's algorithm calculation and mentioned the "1152-fold" symmetry for the 2x2x2. I got to looking at some of the messages in the Cube-Lovers archives that Jerry Bryan had made about B-conjugation and the 1152-fold symmetry of the 2x2x2. He found that there were 77802 equivalence classes for the 2x2x2.

I have used antisymmetry to further reduce the number of equivalence classes for the 2x2x2 to 40296. The following table shows the class sizes of these equivalence classes.

class size  class size/24  count
----------  -------------  -----
     24           1            1
     48           2            1
     72           3            3
     96           4            1
    144           6           14
    192           8           11
    288          12           49
    384          16           22
    576          24          337
    768          32            6
   1152          48         3353
   2304          96        36498
                           -----
                  total    40296

I then performed God's algorithm calculations (HTM and QTM) to find the number of equivalence classes at each distance from the solved 2x2x2 cube. The results are given below. Because the 2x2x2 has no centers that provide a reference for the positions of the other cubies, the number of positions of the corners for the 2x2x2 (the only cubies it has) can be considered to be 1/24 the number of positions of the corners of the 3x3x3 (3674160 instead of 88179840). So in the tables below, I use the factor-of-24 reduced numbers for simplicity. The tables further break down the positions with respect to different class sizes.

Half-turn metric
================
             1/24
distance  class size    classes        positions
--------  ----------  -----------   ---------------
    0         1           1               1
    0            all            1                 1

    1         3           1               3
    1         6           1               6
    1            all            2                 9

    2         6           1               6
    2        12           2              24
    2        24           1              24
    2            all            4                54

    3         3           1               3
    3         6           1               6
    3        12           4              48
    3        24           5             120
    3        48           3             144
    3            all           14               321
 
    4         2           1               2
    4         3           1               3
    4         6           3              18
    4        12           2              24
    4        24           5             120
    4        48          23            1104
    4        96           6             576
    4            all           41              1847

    5         6           4              24
    5         8           1               8
    5        12           4              48
    5        24          15             360
    5        48          67            3216
    5        96          66            6336
    5            all          157              9992

    6         6           2              12
    6        12           5              60
    6        24          22             528
    6        48         134            6432
    6        96         449           43104
    6            all          612             50136

    7         4           1               4
    7         6           2              12
    7        12          12             144
    7        24          58            1392
    7        48         298           14304
    7        96        2205          211680
    7            all         2576            227536

    8         8           1               8
    8        12           6              72
    8        16           2              32
    8        24          59            1416
    8        32           1              32
    8        48         588           28224
    8        96        8753          840288
    8            all         9410            870072

    9         8           3              24
    9        12           7              84
    9        16           6              96
    9        24          91            2184
    9        32           2              64
    9        48        1325           63600
    9        96       18976         1821696
    9            all        20410           1887748

   10         8           5              40
   10        12           4              48
   10        16          12             192
   10        24          74            1776
   10        32           3              96
   10        48         879           42192
   10        96        6036          579456
   10            all         7013            623800

   11         8           1               8
   11        12           3              36
   11        16           2              32
   11        24           7             168
   11        48          36            1728
   11        96           7             672
   11            all           56              2644
                            -----           -------
                            40296           3674160

Quarter-turn metric
===================
             1/24
distance  class size    classes        positions
--------  ----------  -----------   ---------------
    0         1           1               1
    0            all            1                 1

    1         6           1               6
    1            all            1                 6

    2         3           1               3
    2        12           2              24
    2            all            3                27

    3        24           3              72
    3        48           1              48
    3            all            4               120

    4         6           1               6
    4        12           4              48
    4        48           6             288
    4        96           2             192
    4            all           13               534

    5        24           4              96
    5        48          17             816
    5        96          14            1344
    5            all           35              2256

    6         3           1               3
    6         6           3              18
    6         8           1               8
    6        12           3              36
    6        24           9             216
    6        48          37            1776
    6        96          72            6912
    6            all          126              8969

    7         4           1               4
    7         6           1               6
    7        12           2              24
    7        24          16             384
    7        48          76            3648
    7        96         302           28992
    7            all          398             33058

    8         2           1               2
    8         3           1               3
    8         6           4              24
    8        12           4              48
    8        24          25             600
    8        48         168            8064
    8        96        1098          105408
    8            all         1301            114149

    9        12           3              36
    9        16           1              16
    9        24          35             840
    9        48         334           16032
    9        96        3579          343584
    9            all         3952            360508

   10         6           2              12
   10         8           3              24
   10        12          10             120
   10        24          68            1632
   10        48         656           31488
   10        96        9347          897312
   10            all        10086            930588

   11         8           1               8
   11        12           5              60
   11        16           2              32
   11        24          76            1824
   11        32           4             128
   11        48        1040           49920
   11        96       13530         1298880
   11            all        14658           1350852

   12         6           2              12
   12         8           2              16
   12        12          11             132
   12        16          15             240
   12        24          73            1752
   12        48         774           37152
   12        96        7742          743232
   12            all         8619            782536

   13         8           3              24
   13        12           4              48
   13        16           3              48
   13        24          26             624
   13        32           2              64
   13        48         242           11616
   13        96         811           77856
   13            all         1091             90280

   14         8           1               8
   14        12           1              12
   14        16           1              16
   14        24           2              48
   14        48           2              96
   14        96           1              96
   14            all            8               276
                            -----           -------
                            40296           3674160

Comment viewing options

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

Memories

First of all, congratulations on applying antisymmetry to the 2x2x2 problem.

Your message really brought back some memories. At the time I did the original work on applying symmetry to the 2x2x2 problem, I knew very little about group theory. It was just that I was a pretty good programmer, and I had a pretty good intuitive feel for symmetry. Plus, I had to do something to reduce the size of the search space because I was working on a 286 PC running DOS with 512K memory and a 5MB hard disk. Of course, at that time the 286 PC's were brand new and were huge as compared to their predecessors.

My use of the term B-conjugation was a misnomer, kindly corrected by Dan Hoey. What I was doing was starting with the corners of the 3x3x3 and reducing the search space as follows. For each position x, I was calculating a representative as the minimum of mxn, for all m and n in M (the set of 48 rotations and reflections), and where m and n both had to be rotations or both had to be reflections. Since this process is not conjugation, it can't be called B-conjugation.

Dan showed that this process was equivalent to calculating the minimum of (m-1xm)c for all m in M and for all c in C (the set of 24 rotations). It's the inclusion of the c rotation that reduces the search space by 24 times, and the inclusion of M-conjugation that reduces the search space by about 48 times, for a total reduction of about 1152.

In as sense, I had started with a problem that was 24 times bigger than it needed to be and reduced it by 1152 times. I think now that I would have been better off starting with a problem that was just as big as it needed to be and reducing it only by 48 times. The size of the resulting search space would be the same.

As has been pointed out numerous times and places, the way to start out with a model for the 2x2x2 that starts out the right size is to generate the 2x2x2 by something like <U,L,F> rather than generating it as <U,L,F,D,R,B>. However, this model creates a new question that I've never quite been able to figure out. I'm probably just not thinking about the problem correctly, and perhaps one of you all can help me figure it out.

I can't figure out how M-conjugation can reduce the search space by 48 times for the <U,L,F> model. For example, let x be an element of <U,L,F>. Then xm may not even be in <U,L,F>. But if x is an element of <U,L,F,D,R,B>, then xm is guaranteed to be in <U,L,F,D,R,B>.

Re: memories

Basically, I had used the <U,L,F,D,R,B> model of 40320*2187 = 88179840 positions to do my calculations. I wrote my program to generate lookup tables to convert from those 88179840 positions to 77802*1152 sym-coordinates or 40296*2304 "antisym-coordinates," while also building a reverse-mapping lookup table to map the 77802*1152 sym-coordinates or 40296*2304 antisym-coordinates back to the 88179840 positions. These tables required a whopping 724,087,296 bytes.

The antisymmetry version of the code would take each position x in <U,L,F,D,R,B> and calculate (m-1xm)c and (m-1x-1m)c for all cube rotations c and all cube symmetries m. An alternate version calculated (m-1xm)c and ((m-1xm)c)-1, which also also seemed to work.

After Jerry's response, I went back to look at using <U,R,F> (essentially equivalent to using <U,L,F> as suggested by Jerry). Instead of generating mapping tables in both directions, I simply created a mapping table from the 3674160 positions to the 40296 classes. So for a position x in <U,R,F>, the program would compute (in <U,L,F,D,R,B>-space) all positions of the form (m-1(xc)m)q and (m-1(xc)-1m)q for all cube rotations c and all cube symmetries m, and where q represents the cube rotation required to put the resulting cube back into a <U,R,F> position. All the resulting <U,R,F> positions were mapped to the same class index as x. This process continued with all <U,R,F> positions not yet assigned to a class. So the mapping table in this case was only 14,696,640 bytes. This reduces the storage required, but in applying every cube rotation to the positions in <U,R,F>, it is still essentially reducing from <U,L,F,D,R,B>-space.

Later, I reran the program, except without applying the "q" cube rotation, essentially ignoring all resulting positions not in the <U,R,F>-space. This still produced the same 40296 classes. This reduces execution time, but is still essentially based on reducing from the <U,L,F,D,R,B>-space. It may be possible to simplify this further, but I haven't investigated any further.

2x2x2 Symmetries

Some thoughts occur to me concerning symmetry and the 2x2x2 cube. I would look upon one of the eight cubelets as fixed and the puzzle thus being the permutations of the other seven cubelets relative the eighth as a fixed reference. This would correspond to what you term the (U,L,F) model. The symmetry of the puzzle then becomes not cubic but trigonal pyramidal. One then only need consider six elements of symmetry, identity, two by rotation about the three fold axis, and three by reflection through the three vertical planes of symmetry. Would this not simplify the problem of finding equivalence classes or am I missing something?

Horses and Cubes

What you are writing about is what I'm trying to understand, and don't.

It seems to me that if two different models for the same problem are correct representations of the problem, then the two different models should yield the same answer. But in this case, it seems to me that we have two different models that ought to be equivalent but aren't. I'm obviously missing something.

Ignore symmetry for a second. The two models for the 2x2x2 seem to be:

1. Consider one corner fixed.
2. Do not consider any corners fixed, but consider any positions equivalent if they differ only by a whole cube rotation. This truly means differing by a single rotation, not differing by conjugation of rotations.

Model #2 starts out being exactly 24 times larger than model #1. But when you consider positions equivalent if they differ only by whole cube rotations for model #2, then the size of model #2 is reduced by exactly 24 times. That means that model #1 and model #2 are exactly the same size, which is the expected outcome. Model #1 is simpler in several respects than model #2, but the two models yield identical results.

So far, so good. Now let's add symmetry. Conjugating by symmetry, model #2 can be further reduced by about 48 times. Conjugating by symmetry, model #1 can be further reduced by about 6 times (exactly as you point out). So model #2 is about 8 times smaller than model #1.

I see where the factor of 8 is coming from. It's because model #2 is dealing with symmetries with respect to all 8 corners and model #1 is dealing with symmetries with respect to only one corner. But I'm still making a dumb mistake.

I'm sure the mistake is something like the following "proof" that a horse has 8 legs: a horse has 2 front legs, 2 back legs, 2 left legs, and 2 right legs. 2+2+2+2 is 8, so a horse has 8 legs. The mistake in the horse proof is trivial to see, but I just can't quite see what's wrong with the way the size of the 2x2x2 problem is being calculated when it is reduced by symmetry.

Reducing the 2x2x2 group by symmetry

The problem is that when one conjugates model 2 with the full 48 element cubic symmetry set one generates a whole lot of positions which differ from one another only by whole cube rotations and thus are the same position. These duplicates do nothing to reduce the search space.

Consider model 1 with the left,down,back cubelet fixed in position. The six allowed symmetries all leave this cublet in place. The disallowed symmetries move this cublet to a different position. Thus [s' m s] will in general not put the fixed cubelet back where it belongs. Thus the similarity transform produces an element not in the original group and is not valid. The same thing is occurring in model 2 but since no reference orientation is defined it is more difficult to see.

77802

I'm very much inclined to agree with your analysis. The your analysis suggests that symmetry should reduce the search space for the 2x2x2 only by six times. Yet, we have the following.
Order of the corners of the 3x3x3   88179840
Order of the 2x2x2                   3674160  (24 times reduction)
2x2x2 reduced by symmetry              77802  (47.22 times reduction, about 48 times)
So the search space for the 2x2x2 really can be reduced about 48 times by symmetry rather than about 6 times, and I can't explain why to my satisfaction.

Reducing the 2x2x2 group by symmetry

I've been thinking about this a lot and I think I was wrong in my previous post when I implied using cubic symmetry to reduce the 2x2x2 group was invalid. I believe I see how to use full cubic symmetry to reduce the 2x2x2 group in the context of the fixed cubelet model.

One must have a representation which represents all eight cubelets, one of which is designated as the reference cubelet. Let G be the group of all corner permutations using the full set of face turns and H be the subgroup of G generated using only the R,U,F face turns. H then contains all elements of G in which the reference cubelet, the ( l , d , b ) cubelet, is in the unrotated or E state.

An equivalence class may be generated for each element h in H by applying similarity transforms using the elements of the cubic symmetry group:

ei = ci-1 h ci for all elements, ci, of the cubic symmetry group.

Now as I pointed out in the previous post the set of elements generated above is not a valid equivalence class because in general the elements generated are not members of H. This is because the similarity transform may move and/or rotate the reference cubelet from the E state. However, since G has cubic symmetry and h is a member of G, the transformed elements will be members of G. Any element of G may be converted to an element of H by applying a whole cube rotation, i.e. the whole cube rotation which will place the reference cubelet in the E state. So, for each element ei a whole cube rotation must be applied to generate its corresponding element in H. The set of elements thus generated would then constitute the equivalence class--I think.

In order for the above to be valid, the procedure must uniquely define each class. For this to be true it must not matter which element of the class one uses as the basis of the class--submit any member of the class to the above procedure and one will generate the same list of elements. Now I have been confusing myself with left cosets, right cosets, normal subgroups, etc. trying to convince myself this is the case, but I haven't yet. Perhaps someone with more facility with the abstract concepts of group theory than I could look at the above with a critical eye and help me out?

2x2x2 fixed cubelet model implemented

Just for kicks I implemented the 2x2x2 cube with a fixed cubelet model . I expanded the group using the (R,U,F) q turns using symmetry compression based on the above. It works. Here are the results:

Shell Classes Elements
0 1 1
1 1 6
2 3 27
3 6 120
4 17 534
5 59 2256
6 217 8969
7 738 33058
8 2465 114149
9 7646 360508
10 19641 930588
11 28475 1350852
12 16547 782536
13 1976 90280
14 10 276
15 0 0
TOTALS 77802 3674160

My attempt to formalise this.

Let C be the group of rotations of the cube. When reducing the whole group G by cube rotations, we split G into sets C g C, g in G.

The first cube rotation can be seen as a recolouring, the last cube rotation determines the orientation of the puzzle as a whole. All elements in C g C are deemed equivalent to g itself.

These are easily shown to be equivalence classes.

C c1 g c2 C = C g C for any c1, c2 in C, and so it doesn't matter which element in the class is used to represent it.

You said:

Let H be the subgroup of G generated using only the R,U,F face turns. An equivalence class may be generated for each element h in H by applying similarity transforms using the elements of the cubic symmetry group:

ei = ci-1 h ci for all elements, ci, of the cubic symmetry group.

[...], for each element ei a whole cube rotation must be applied to generate its corresponding element in H. The set of elements thus generated would then constitute the equivalence class--I think.
I think so too. You just constructed the set:

{ cj ci-1 h ci | h fixed in H; ci in C; cj in C chosen such that cj ci-1 h ci lies in H }

Lets combine cj ci-1 to give:

{ ck h ci | h fixed in H; ci in C; ck in C chosen such that ck h ci lies in H }

This can however also be thought of as C h C intersected with H.

You said:

In order for the above to be valid, the procedure must uniquely define each class. For this to be true it must not matter which element of the class one uses as the basis of the class--submit any member of the class to the above procedure and one will generate the same list of elements.
With the formulation above it is easy to show, in just the same manner as before for the whole group.

The only remaining question now is, will the number of equivalence classes be the same in these two different formulations.

Given an equivalence class of the second type, C h C intersected with H, it is easy to uniquely construct an eq. class of the first type, namely C h C.

The other direction is only slightly trickier. Given an eq. class of the first type, C g C for some g in G. The reference piece is moved somewhere, but since C is transitive, we can follow it by a cube rotation c such that c g lies in H. From this we can of course construct C (cg) C intersect H, an eq. class of the second type.

So these two formulations of sets of equivalent permutations are themselves equivalent. It is just that in the second formulation you use a smaller group of permutations, resulting in just as many smaller equivalence classes.

Things are not so different if we use use M instead of C, i.e. include the reflections as well. The only difference is that an equivalence class of the first type now becomes M g M intersect G. This is because reflection is not an operation that lies in G itself, just like the cube rotations in C were not in the group H. For M g M intersect G to make sense, we must of course work in a supergroup containing both G and M, for example the group S24.

Jaap
Jaap's Puzzle Page: http://www.geocities.com/jaapsch/puzzles/

Reducing the 2x2x2 group by symmetry

Your analysis is very interesting. I'm trying to get my mind around what you're saying. I think visually. Symbols on paper lose their meaning unless I can visualize it, so bear with me.

You said:
"Let C be the group of rotations of the cube. When reducing the whole group G by cube rotations, we split G into sets C g C, g in G."

Ok, CgC are sets generated by: ci g cj for all elements ci, cj in C. This is equivalent to ci (cj-1 g cj). The similarity transform, (cj-1 g cj), generates all the unique ways pattern g may be applied to the cube and ci are all the whole cube rotations which may be applied to each pattern ( or the different angles from which that pattern may be viewed ).

Now we've been talking about reducing G using the full 48 element cubic symmetry group, what you refer to as M. So we want to look at equivalence classes as MgM intersect G. Restating MgM as I did above for CgC, the constructions of the sets follows:

mi(mj-1 g mj) for all elements mi, mj of M.

The similarity transform: (mj-1 g mj) always generates an element of G--parity rules require that the product of a rotation and a reflection is always a reflection and the product of two reflections is always a rotation. Thus you don't have to worry about the transform producing inside-out cubelets. Reflection preserves twist parity so everything is OK. In order for the whole product to be a member of G, mi can't be a reflection. That is mi must be a rotation, an element of C. Thus the sets may be constructed as:

ci(mj-1 g mj) for all elements ci of C and mj of M

So MgM intersect G generates sets containing all the ways a pattern ( and its mirror image ) may be applied to the cube and all the different angles from which each may be viewed. So one may organize the elements of each equivalence set in G into subsets, each subset containing all the ways of viewing a particular result of (mj-1 g mj). Now the procedure I propose for generating equivalence sets in H starts by generating a set by:

(mj-1 h mj) for all elements mj of M

This is precisely the same as the first part of the procedure for generating the equivalence sets in G. Thus the initially generated set contains one element from each subset of the set in G defined above. By applying a whole cube rotation the element in each subset which is a member of H is determined ( and there must be one since all orientations are included ) and thus becomes an element of the equivalence set in H. OK, good. I've convinced myself that what you say is true. The equivalence sets generated are indeed (MgM intersect G) intersect H.

All your other arguments for completeness etc. seem good. So I think the proposed procedure is sound and will give well formed equivalence sets in the fixed cubelet model.

Thank you. After working through what you said, I think I understand things much better.

Symmetry of the 2x2x2 vs. Symmetry of the Corners of the 3x3x3

The following largely restates what others have already said, but I believe I finally understand the issues associated with the search space for the 2x2x2 being reduced about 6 times by symmetry vs. the search space for the 2x2x2 being reduced about 48 times by symmetry.

1. <F,L,U> or any of its conjugate groups can be thought of as a subset of the corners of the 3x3x3 with an index of 24.

2. <F,L,U> or any of its conjugate groups can be thought of as a way to model the 2x2x2. The 2x2x2 is 24 times smaller than the corners of the 3x3x3.

3. The order of <F,L,U> or any of its conjugate groups as a subset of the corners of the 3x3x3 is the same as the order of the 2x2x2. <F,L,U> or any of its conjugate groups is a perfectly acceptable model for the 2x2x2.

4. The search space for <F,L,U> or any of its conjugate groups can be reduced by about 6 times when <F,L,U> or any of its conjugate groups is thought of as a subgroup of the 3x3x3.

5. The search space for <F,L,U> or any of its conjugate groups can be reduced by about 48 times when <F,L,U> or any of its conjugate groups is thought of as a model for the 2x2x2.

6. In the case of both #4 and #5, if x is an element of <F,L,U>, then xm may not be in <F,L,U>. In the case of #4, the only way to resolve the closure problem is to restrict m to one of the 6 symmetries that preserves the corner that is fixed by <F,L,U>. In the case of #5, the closure problem may be solved by applying an appropriate rotation c to xm and therefore all 48 symmetries in M may be used.

7. Another way to say the same thing is that m-1xm may not provide closure for <F,L,U>. There always exists a rotation c in C such that (m-1xm)c provides closure in the 2x2x2. However, a rotation c in C cannot be used to provide closure to m-1xm in the corners of the 3x3x3.