~~~ From:

~~~ ~~~ Subject:

Having read the CUBE-LOVERS mail, I note a recurring theme of dismay

that there is no clearly stated procedure for deciding whether a given

configuration is reachable (or solvable) or not. Furthermore, I share

Dyer's view that there has been no persuasive presentation of the fact

that there are precisely 12 equivalence classes of permutations under

the transformations permitted by the cube. In this note, I intend to

clear up this situation for the benefit of the less sophisticated

readers of this material.

I should apologize at the outset for my ignorance. I have not read

Singmaster's pamphlet, nor have I communicated with any of the

knowledgeable people around here at Stanford on the subject of cubes.

My knowledge stems entirely from my own personal efforts at solving

cubes and what I have gleaned from CUBE-LOVERS mail. So I hope

readers will be tolerant of any lengthy explanations of well-known

cube-lore.

COMMENTS ON NOTATION

I will start by offering my two-bits-worth on notation. It is

relevant because I will use some of it later.

I prefer to call the cubies in the centers of the faces "face cubies",

because "center" and "corner" both start with a "C". (Also, I have

worked with other 3X3X3 cubes and tended to use "center" for the one

in the middle that you cannot see.)

I do not agree that there is any need for notation to describe

orientation of the whole cube or reorientation of it. For discussion

purposes, you should pick one orientation of the cube (based on the

direction in which its face cubies are oriented) and leave it that

way. All transformations can be described relative to that

orientation.

Rotating a center-slice should not be considered to be a move, since

it changes the orientation of the cube.

Since it is not the case that all cubes have the same color pattern,

no direct reference should be made to color. Instead the exposed

faces of any cubie should be identified in terms of the direction

(LRFBUD) they will face when the cubie is in its home (or at START)

position relative to the chosen orientation of the cube.

When I was learning to work cubes, the concept of complementarity

played a critical role. (I do not claim my methods are good. It takes

me about 20 min.) It is certainly handy to have a way of talking

about pairs of opposing faces. I think most would agree that the top

and bottom can be referred to as "horizontal" faces, and left and

right can be called "lateral" faces. For front and back, I really do

not know a good word; I suggest calling them "extremal", since their

face cubies are the closest and most distant from the observer's point

of view.

ORBIT CLASSIFICATION (for the uninitiated)

Introduction -

It is possible to define some "parity" concepts that simplify stating

the characterization of the equivalence classes of cube

configurations. The precise definitions will follow; but to start

with, we will name them:

Edge Permutation Parity (EPP = 0 or 1)

Edge Orientation Parity (EOP = 0 or 1)

Corner Permutation Parity (CPP = 0 or 1)

Corner Orientation Parity (COP = 0, 1, or 2)

A configuration is reachable if COP and EOP are zero and CPP=EPP.

More generally, setting TPP=CPP+EPP mod 2, we can define

Total Permutation Parity (TPP = 0 or 1).

Then the Parity Vector, defined by (TPP, EOP, COP), can be used to

represent the equivalence class of a configuration.

Permutation Parities Defined -

Background: A permutation of [1,n] is considered to be even (0) or odd

(1) depending on whether an even or odd number of pair swaps is

required to restore the set to original order. You can compute it by

counting the number of reversals in the sequence - ie., the number of

pairs, (p,q) such that p>q and p precedes q.

For the cube, you can assign a position number (1-8) for each of the

corners and also a number (1-12) for each of the edge positions. For

each cubie, you can the speak of its home position number and its

current position. Writing down home position numbers in order of

current position gives a permutation of natural numbers in which you

can count reversals to see if it is odd or even. This is done without

regard to orientation.

Properties: A quarter turn is an odd permutation of the four edges

involved and also of the four corners. Thus a quarter turn changes

both EPP and CPP but leaves TPP unchanged. TPP is preserved by all

twists.

Edge Orientation Parity Defined -

For each edge cubie consider its Oriented Distance from Home, defined

to be the smallest number of quarter turn twists required to put it in

its home position with correct orientation. It is no bigger than 4.

As an example, an edge cubie at home with the wrong orientation is at

an oriented distance of 3. EOP is the sum modulo 2 of the Oriented

Distances from Home for all edge cubies.

Properties: For each edge cubie affected, a quarter turn either

increases or decreases its Oriented Distance from Home by 1. Since 4

edge cubies are affected, the net effect must be even. Thus all

twists preserve EOP.

Corner Orientation Parity Defined -

Looking head-on at the apex of any corner you can consider twisting it

to any one of three positions. For any given corner cubie we define

its individual orientation parity to be the number of 120 degree

counter-clockwise twists required to bring the horizontal face of the

cubie into horizontal position relative to the whole cube. COP is the

sum modulo 3 of the individual parities. (Since it is three-valued,

it could be argued that COP ought not to be called a "parity", but

that fouls up the parallelism in the discussion.)

Properties: Twisting a horizontal face does not change the orientation

of any corner. Twisting an extremal or lateral face does alter

orientations. Consider a counter-clockwise quarter turn of either

kind of vertical face. For each of the two corner cubies that remain

in the same horizontal face, the orientation parity decreases by 1

modulo 3. For the other two, it increases by 1. Again, the net

effect is zero. COP is preserved by all twists.

Equivalence Classes -

There must be at least 12 orbits, since all transformations preserve

the Parity Vector, (TPP,EOP,COP), and it has 12 possible values. To

show there cannot be more, you must show, given two configurations

with the same Parity Vector, that one can be transformed into the

other. The first paragraph of the note from Davis to DDYER, dated

Aug. 4, indicates how the corners can be permuted and reoriented. We

need to be a little more careful about the interaction between the

processes that rearrange corners and edges. Suppose we are

considering going from a configuration A to a configuration B, and

consider the intermediate stage C at which we have permuted and

reoriented the corners to agree with the target configuration B.

First we observe that the EPP of C must agree with that of B, whether

or not A and B have the same CPP. Thus there is an even permutation

of the edges of C that will put them in the desired target positions

of B. This permutation can be generated by swapping appropriate pairs

of edge cubie pairs. Consider the intermediate stage D achieved after

all edge cubies are in their desired positions. Now the EOPs of D and

B agree, so the number of edge cubies with wrong orientation must be

even. This can be corrected by flipping an appropriate set of edge

pairs in place.

The Extended Problem -

If the orientations of face cubies are to be considered then we

introduce

Face Orientation Parity (FOP = 0 or 1).

It is the number of quarter turns modulo 2 required to get all the

face cubies back to starting position. Adding this fourth component

to the Parity Vector yields 24 equivalence classes. Existence of

appropriate transformations for moving about within equivalence

classes was indicated by ALAN and CMB in their notes of Jul. 15.

Complementary Configurations -

A configuration may be said to be complementary if every color exposed

on a face of the cube either agrees with that of the face cubie on

that cube face or comes from the parallel opposing face. There seems

to be a fair amount of interest in such positions. It is easy to see

for such configurations that COP and EOP are 0. Thus the

configruation is reachable if and only if its TPP is 0. This can be

determined easily by counting "wrong" cubie faces - ie., edge or

corner cubie faces with the color complementary to that of the face

cubie on the same cube face. TPP is 0 if and only if this number is a

multiple of four. (It is always even.)

If you restrict yourself to 180 degree twists, you can generate only

complementary configurations. Thus the more interesting complementary

configurations tend to be those that require quarter turns to achieve.

A REDUCED PROBLEM ?

Suppose you lock up four of the axles and consider turning just two

adjacent faces. This Two-Faced puzzle deals with only 15 of the

cubies. I got the bright idea of playing with a logically jammed cube

after I had already developed a crude methodology for working cubes.

I figured that with a simpler problem I might gain some new insights.

Actually, I got confused. In retrospect, this is not so surprising.

I think that most of us would grant that if you can work Two-Faced

cubes, you can certainly work the whole thing. The point is that you

tend to encounter many of the same sorts of problems, but you have

fewer degrees of freedom for dealing with them.

The argument already given shows that the Two-Faced cube must have at

least 12 equivalence classes. It is not clear to me that there are

not more in this case. I have not discovered all the tools to show

that two members of the same equivalence class (in the regular sense)

can be transformed into one another. Can anyone out there resolve

this issue?

-------