From:

~~~ Subject:

On 12/13/93 at 22:31:31 hoey@aic.nrl.navy.mil said:

In the absence of face centers, there is another kind of reduction

that takes account of the 24 possible positions of the resulting

collection of edges in space. So two positions X and Y are considered

equivalent if

X = m' Y m c

where m is a rotation or reflection in M, and c is a rotation.

>My understanding of Jerry Bryan's method is that he combines "m c"

>into a single rotation or reflection, and factors out the reflection

>on both sides. It seems to me that what he calls a "color rotation"

>is premultiplication, while a "cube rotation" is postmultiplication.

>[I am somewhat uncertain of this, because it doesn't explain how there

>can be a 1252-element symmetry group when face centers are present, so

^^^^

should be 1152

perhaps I'm missing something crucial.]

I just reread "Symmetry and Local Maxima". Let's see if I can make

some sense of this. I believe "pre-multiplication" and

"post-multiplication" are correct. In my computer model, the

corner facelets are simply numbered from 1 to 24, and any configuration

of the corners is an order-24 row vector. The rotation and reflection

operators are also order-24 row vectors, again with each cell simply

containing a number from 1 to 24.

In almost anybody's programming language you would copy an order-24

row vector with something like

For i = 1 to 24 B(i) = A(i)

Well, if P is a rotation operator, you could perform a rotation

two ways. I guess one is pre-multiplication and one is

post-multiplication.

1) For i = 1 to 24 B(i) = A(P(i)) 2) For i = 1 to 24 B(i) = P(A(i))

(As an aside, this illustrates the question I raised in my previous

post about "which is the operator and which is the thing being

operated on?" Is P operating on A, or is A operating on P?)

In fact, if what I am doing is properly called pre- and post-

multiplication, then I am doing both as a part of a single,

composite operator. I.e.,

For i = 1 to 24 B(i) = P(A(P(i)))

More completely, there are 24 rotations, P1 through P24, so the

actual loop looks something like

For j = 1 to 24 for k = 1 to 24 for i = 1 to 24 Bj,k(i) = Pj(A(Pk(i)))

Finally, if Q is a reflection (actually, if Q1 is the identity and

Q2 is the reflection), then we have

For j = 1 to 24 for k = 1 to 24 for m = 1 to 2 for i = 1 to 24 Bj,k,m(i) = Qm(Pj(A(Qm(Pk(i)))))

I believe this loop calculates Dan Hoey's M. In my data base, I

store the minimum of Bj,k,m over j = 1 to 24, k = 1 to 24, and

m = 1 to 2. I tend to call the minimum of Bj,k,m a canonical

form. I am not sure if that is the best terminology. The

minimal element is not any simpler than any other. It is just

that I need a function to choose an element from a set, and

picking the minimal element seems very natural. Any other

element would do as well, provided I could always be sure of

picking the same element.

Also, my criterion for equivalence is slightly

different (but isomorphic, I think) than the one described by

Dan Hoey. Suppose A and B are two cubes.

Rather than mapping A to B or B to A in M, I map both A and B

to their respective canonical forms. A and B are equivalent if

their respective canonical forms are equal.

I hasten to add that the actual loop in the program is a bit

more complex than the one shown above. The one above would

be far too slow. The actual loop is several hundred times

faster.

Now, as to the centers. I still sometimes have a certain doubt

about the centers. They are fixed, so how can you reduce the

problem (i.e., increase the size of the equivalence classes)

by both rotating the cube and rotating the colors (by both pre-

and post-multiplication)?

In my computer model for the centers, I simply number center facelets

from 1 to 6, and the centers are stored as an order-6 row vector.

The centers are disjoint from the corners (as well as from the edges),

so there is no problem in numbering one set of objects from 1 to 24 and

another from 1 to 6.

I define a set of 24 rotation operators P* on the centers, corresponding

to the 24 rotation operators P on the corners, and a set of 2 reflection

operators Q* on the centers, corresponding to the 2 reflection operators

Q on the corners. Then, if C is an order-6 row vector representing

the centers, I calculate Dj,k,m = Q*m(P*j(C(Q*m(P*k)))) anytime

I calculate Bj,k,m = Qm(Pj(A(Qm(Pk)))).

(Read the asterisks above as superscripts. I am not intending

the multiplication operation which the asterisk denotes in

many programming languages.)

Hence, I rotate and reflect the centers right along with the corners.

But there are only 24 distinct states for the centers, and each can

occur with any canonical form for the corners. Hence, the "corners

plus centers" data base is exactly 24 times larger than

the "2x2x2" data base.

My model for the cube seems to start out 24 times larger than

everybody else's. However, by storing only the canonical form

for each equivalence class, and since most of the equivalence

classes have 1152 elements, my data base seems to end up about

48 times smaller than everybody else's. This fact seems to

remain true, even when the "fixed centers" are added in.

I am not sure if this answers Dan's question about my model

with centers added. Effectively, I am using a "fixed corners"

representation of the cube, and rotating the centers. Each

equivalence class for the corners under M has (up to) 1152

elements, and each equivalence class for the centers under

M has only 24 elements. But it doesn't seem to matter.

(Up to) 48 different configurations of the corners within

M share each configuration of the centers.

Since I am in this deep, let me finish explaining certain details

of my model. I don't really store all 24 elements of each

row vector. I really just store 8. That is, I store the

facelets for the front and back face. The other 16 facelets

can be reconstructed from the first 8. In effect, storing

a number from 1 to 24 stores both the location of each cubie

and its twist. Finally, I really, really only store 7 elements.

In the canonical form, the first element is always 1, so there

is no reason to store it. Thus, a data base record for the

2x2x2 looks like

CCCCCCC,L

where the CCCCCCC are the seven elements representing the canonical

form, and L is the corresponding level.

When you add the centers, I started out with notion that the

order-6 row vector for center only has 24 possible states. Thus,

it can be encoded as a number from 1 to 24. This lead to the

following

CCCCCCC,L,R

where CCCCCCC and L are as before, and R is an index encoding

the orientation of the centers. But this can be improved upon

even further. With my model for the corners plus centers, each

distinct value of CCCCCCC will occur exactly 24 times, and each

distinct value of CCCCCCC is already represented in my data

base for the 2x2x2. Hence, I can have the exact same number of

(longer) records, and encode the corners of the 3x3x3 as

CCCCCCC,L,L1 L2 L3 .... L23 L24

where CCCCCCC is as before, L is the level of CCCCCCC in the

2x2x2, and L1 through L24 are the levels of CCCCCCC in the corners

of the 3x3x3 when the index of the position of the centers with

respect to the corners is 1 through 24, respectively. Hence, my

data base for the corners of the 3x3x3 has the same number of

records as the data base for the 2x2x2, and is physically only

four times larger.

With regard to the edge cube, I should mention that no one has

mentioned a 9 QT process for the all-flip nor a 15 QT process for the

pons-asinorum-all-flip. Of course, the latter would be somewhat more

interesting, being the longest optimal sequence.

I will work on these two cases, but it will take some time. My model

is very good at storing a great many states of the cube very

compactly, but it does not encode processes at all. I will have

to extract the processes by hand. This is quite easy in my

data bases for the 2x2x2 and corners of 3x3x3. But it is quite

hard for the edges because the data base is 4.2 gigabytes.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU

If you don't have time to do it right today, what makes you think you are

going to have time to do it over again tomorrow?