Date: 6 Aug 1980 1909-PDT From: CSD.VANDERSCHEL at SU-SCORE Subject: Orbit Classification To: CUBE-LOVERS at MIT-MC cc: CSD.VANDERSCHEL at SU-SCORE 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? -------