Two Face Group

Had a look at cube-mail-13. Interesting to see symmetry discussed in a different context. As a chemist all my formal exposure to group theory was in connection with point group symmetry. W group? Heck, that's C_2v. Same symmetry as a water molecule.

In the context of my program, a group state is encoded using one byte per cubelet with I don’t know how much overhead as each state is wrapped as an objective C class. Not the most memory efficient way of doing it certainly.

How would one encode a group element as a single integer? Something like N modulo 120 for the corner position permutation, ( N / 120 ) modulo 3 for corner #1 twist , etc?

0: (0 1 2)
1: (0 2 1)
2: (1 0 2)
3: (1 2 0)
4: (2 0 1)
5: (2 1 0)

I think most people use the Sims algorithm instead, which creates a similar (but not identical) bijection. However, the bijection induced by the Sims algorithm does not place the permuations in lexicographic order, and I prefer lexicographic order.

The bijection for S₃ (or for any S_n) is "extremely symmetrical", or one might even say "completely symmetrical". Cube groups are not quite as symmetrical as S_n. As examples of this "lack of complete symmetry", bijections for cube groups must explicitly (or implicitly via the Sims algorithm) take into account such things as preservation of total twist, preservation of total flip, and preservation of parity between corners and edges.

But the bottom line with this idea is that you don't really store a bunch of positions in memory. In fact, your program typically never has more than one position stored in memory at a time. Instead, it stores the distance from Start associated with each position - often at one byte per position. And the table of lengths is indexed via the bijection between positions and the numbers from 1 to n (or from 0 to n-1).

Things get a little more complicated when symmetry and antisymmetry are added to the mix. I tend to operate with representative elements of M-conjugacy classes (which are equivalence classes). Doing it this way can make indexing rather awkward to deal with because representative elements are badly behaved. I think most people use symmetry coordinates rather than representative elements. Symmetry coordinates make indexing much easier to deal with than do representative elements.

Yes, a "bijection between the group elements and the numbers from 1 to n " is what I was talking about in my untutored way. One must have a scheme whereby one numbers the group elements leaving no gaps. Furthermore, one must have a scheme for converting that number back to a fuller representation of the group element. The particulars of that scheme are dependent on the group and how that group is represented.

I gather that the usual way group elements are represented is as a permutation of the facelets. When you start talking about these permutations in terms of abstract groups you've gone beyond my depth. I know little of these groups beyond symmetry point groups and that in terms of Schoenflies notation.

I represent the group differently. I represent each individual cubelet with a 3 x 3 transformation matrix describing how it has been moved from its home position. This has the advantage of tying in directly with the Open GL engine which makes extensive use of transformation matrixes for rendering 3D objects to the display. One further advantage is that the transformation matrixes may be further abstracted as elements of the cubic pure rotational group ( Schoenflies group O ; the C abstract group? -- the group generated by 90⁰ rotations about the coordinate axes). So my representation of a Rubik group element essentially consists of a list of 20 integers between 0 and 23 representing the O group element for each cubelets rotational state. Multiplication of two group elements then consists of looking up 20 products in the O group multiplication table, one for each cubelet position.

So how would one derive an index from my representation? Extracting the corner and edge position permutations from my representation is straightforward. I presume there are schemes for indexing these groups. Corner and edge orientation are given by the rotational state. It could be done. It could be coded as a multidimensional array: distance[ edgePermIndex ][ cornerPermIndex ][ flip1][flip2]. . . [twist1][twist2] . . . Let the compiler take care of the arithmetic.

Not that I'm particularly interested in doing so. I wanted to know the diameter of UF group because I have a Rubik cube solution algorithm which ends with a brute force solution of that group. Twenty five q turns is no problem. Here's another question for you. What is the maximum depth one would need to search from an arbitrary member of the UFR group before finding a member of the UF group? So far I've found 14 q turns to be sufficient. 16 q turns is accessible, 17 might be a problem.

I just thought I would discuss my general approach to representing the 3x3x3 cube, and sub-problems of it.

There was some mention of numbering the facelets, and represent the cube as a permutation of the facelets. With GAP, that is how you generally define the cube. Basically, in GAP, you define a set of basic moves, such as U, F, etc., in terms of how those moves permute the facelets. Then, the function Group(U,F) will automatically generate the group with U and F as generators. The expression Size(Group(U,F)) will return the size of the group.

But when I use C++, I usually use a cubie-level model, where I use an array for each type of piece (corners and edges for 3x3x3), with each array element having a number that represents the cubie occupying a given cubicle, or (especially when I care about the location of a subset of the cubies) a number representing the cubicle and orientation of a given cubie. I generally use this cubie-level model to build a "coordinate model" where I have a few integers representing the information instead of arrays.

For example, for the full cube group, I would have an integer for corner permutation from 0 to 8!-1, another integer for edge permutation (0 to (12!/2)-1), another integer for corner orientation (0 to 2187-1), and another integer for edge orientation (0 to 2048-1). Theoretically, you could combine these numbers into single number in the range 0 to 43252003274489855999, mapping each value in the range to a unique element of the cube group. Note that the range of the edge permutation number is only half the size needed to represent every edge permutation. The parity of the corner permutation must be determined before you can map the edge permutation number to the correct permutation of the edge cubies.

For permutation, I use a routine essentially the same as the perm_n_pack routine in Mike Reid's optimal solver. This represents the permutation in a sort of mixed radix fashion, with the least significant "digit" having 2 possible values, the next "digit" having 3 possible values, and so on. This routine maps the numbers in ascending order to the lexicographic order Jerry Bryan described. Another routine, perm_n_unpack, does the reverse mapping. Note these routines are designed for arrays holding permutation information only, whereas I store both permutation and orientation information. So I may need to make use of temporary arrays where the orientation information is left out.

Note that the least signifcant "digit" in this mixed radix number is either 0 or 1, and if you change the value of just that digit you swap two cubies (more precisely, the cubies in the last two cubicles, if using the cubicle-based representation). This means that the permutation parity changes between odd and even. Since (for the 3x3x3) the corner permutation parity and the edge permutation parity must be the same, the parity information for one of them is redundant. Thus, you can remove the least significant bit of one of the permutation values (such as I did for the edge permutation above). Reconstructing that bit is not so trivial. I generally create a lookup table (a large bit-vector) to generate it. Basically if you set the bit to 0, and the resulting permutation has the parity that matches the other parity, then you know that you have the correct permutation value. Otherwise, you need to set that bit to 1.

For cases when I care about the positions of a subset of the cubies, I created an extension of the perm_n_pack routine that works for m out of n cubies/items. When using a subset, the array elements (in the cubie level representation) represent cubies, and their values represent cube positions ("cubicles") where the cubies are located. Of course, I also created a routine for the reverse mapping.

Edge orientation and corner orientation can be thought of as represented by base 2 numbers for edges, and base 3 numbers for corners. For the full 3x3x3, you would only need 11 base 2 digits for edges, and 7 base 3 digits for corners. The digit values for the remaining edge and corner cubies can be reconstructed based on conserveration of flips/twists.

I usually use a sym-coordinate that takes the place of one or two of the coordinate values of the simple coordinate model discussed above. I generally now use antisymmetry, if applicable, in addition to the applicable cube symmetries for the problem being analyzed. The other coordinates are not affected. This means that there are some redundancies in this "coordinate space" in terms of the equivalence classes. When I determine a new position for the current distance (depth), I must either make sure I mark any other symmetrically equivalent positions, too; or I must make sure I always determine the representative, and only store distance values in the positions for the representative elements. Either way, the table is a little larger than it needs to be, but the amount of wasted space is generally fairly small.

For the <U, F> group, the edge orientation is irrelevant. All corner orientation configurations satisfying conservation of twists are possible, so that is straightforward. There are 7! permutations of the 7 movable edges, but only 6!/6 permutations of the 6 movable corners (and another factor of 2 reduction for matching parity with the edge parity). This makes creating a bijection a little more tricky. One possibility would be to just generate the set of all legal permutations of the corners, and build lookup tables that map between the 720 different values perm_n_pack can return (for n=6) to a number in the range of 0..119, and vice versa. Note that the even-parity and odd-parity cases should be mapped to the numbers in the 0..119 range in some reasonable way so that you can determine parity easily (such as by taking the value modulo 2, or by dividing by 60). The reverse mapping takes the parity and a number 0..59 and maps that back to a number in the range of 0..719 that perm_n_unpack can then use to generate the cubie-level permutation array.

There is a speedsolving method called the Petrus method that is similar to the method B MacKenzie describes.

In that method, the solver builds a 2x2x2 block with 1 corner and 3 edges (in relation to the appropriate centers). I believe that puts the cube into the <U, F, R> subgroup (or an isomorphism of it). Then that 2x2x2 is extended to a 3x2x2 block, followed by orienting the remaining edges. I was thinking that would put the cube into the <U, R> or equivalent subgroup, but I think it is a group that is a factor of six larger. Then, it completes a 3x3x2 block (two layers), keeping the remaining edges oriented, of course. Then, the final layer is completed in two or three steps. In extending the 2x2x2 block to 3x2x2, only U-, F-, and R-layer moves are made, and extending the 3x2x2 (after orienting edges) to a 3x3x2 is done using only U- and R-layer moves. But the method may temporarily break up completed blocks at other times.

See http://lar5.com/cube/index.html for details of the method.

I haven't done a God's Algorithm calculation of the coset space for moving from <U, F, R> into <U, R> (or <U, F>). The cube subgroups page of Jaap's Puzzle Page web site ( http://www.geocities.com/jaapsch/puzzles/subgroup.htm) lists the sizes of these and related subgroups. <U, F, R> has 170,659,735,142,400 elements, or 2,322,432 times the size of <U, R>. It seems to me that finding am efficient representation for a coset space of two nested groups like these is not a trivial task. By that I mean being able to come up with a mapping (bijection) between the coset elements and a range of integers. I've had to do that kind of thing in my five-stage 4x4x4 analyses.

What you describe is essentially the search strategy I've implemented. I progress through subgroups: Rubik group --> UFR group --> UF group --> solved. The first step, solving a 2x2x2 corner, requires at most 9 q turns. The last step, solving the UF group, takes at most 25 q turns. The maximum for the UFR to UF step is at least 14 q turns and is probably 15 or 16 q turns. Gives a quick solution averaging a shade under 38 q turns. By applying the algorithm to each of the 24 different orientations of the cube, both for the recto and for the inverse, the average comes down to 32 q turns.

I took a crack at characterizing the cosets. I figured, perhaps incorrectly, that one could really trim the search tree because I reasoned that expanding from one member of a coset yields the same cosets as expanding from another. I dropped it when I realized that in order to be useful in a forward/backward search scheme you'd need to be dealing with a normal subgroup which the UF group is not. (Looking at what I just wrote, it could probably be made to work by matching right cosets from the goal state to left cosets from the random state. No matter, I don't think I had a workable characterization of the cosets anyway).

I've been composing my messages in a word processor and then saving in HTML. The editor I used generates a lot of header info to format tables which this editor chokes on. Here's what I get with a different word processor. This OK?