Date: 3 NOV 1980 0945-EST From: DCP at MIT-MC (David C. Plummer) Subject: Christman Cross To: CUBE-HACKERS at MIT-MC Greetings, to those who are still on this list!! I have discovered a rather fast method of doing the Christman Cross. It can be done in 22 quarter twists, and I think it can be optomized down into 20. When I ask somebody what the current representation for transforms is, I will send the HOW along. ((NOTE: This means the Plummer Cross can be done in 44 QTwists)) ((((REMARK: For those who count Half Twists [[**sigh**]] as one MOVE, this algorithm is a mere 16 MOVES))))  Date: 4 NOV 1980 0023-EST From: DCP at MIT-MC (David C. Plummer) Subject: Christman Cross algorithm described To: CUBE-HACKERS at MIT-MC Let the following notation exist: the faces: T=Top B=Bottom F=Front P=Posterior (Rear, Back, but those letters are taken) R=Right L=Left The rotations: + Clockwise - Clockwise ++ 180 Rotation (Two moves) Note that the following algorithm exchanges corners diagonally on top and bottom: (Parens for major functional components) (+F+P)(++T++B)(-F-P)(-R-L)(++T++B)(+R+L)(++T++B) This is now a tool. To do the Christman Cross, we do -P [(+F+P)(++T++B)(-F-P)(-R-L)(++T++B)(+R+L)(++T++B)] +P but since transforms associate, and F and P commute, and -P+P = I, we get (+F)(++T++B)(-F-P)(-R-L)(++T++B)(+R+L)(++T++B) +P Which is 20 quarter twists. David Christman thinks he read in Singmaster, Edition 5 that this cross can be done in less than 20 quarter twists. Can somebody confirm or deny this recolection.  Date: 4 Nov 1980 09:28 PST From: McKeeman at PARC-MAXC Subject: Re: Christman Cross algorithm described In-reply-to: DCP's message of 4 NOV 1980 0023-EST To: DCP at MIT-MC (David C. Plummer) cc: CUBE-HACKERS at MIT-MC Using Rubik Song, (+F+P)(++T++B)(-F-P)(-R-L)(++T++B)(+R+L)(++T++B) becomes FB UUDD F'B' R'L' UUDD RL UUDD  Date: 12 November 1980 1849-est From: Paul Schauble Subject: Cube lubrication To: cube-lovers @ mit-mc Pardon me if you've seen this before, I'm not sure it got mailed. The best material I have found for lubricating a cube is a product called Tufoil. This is a suspension of fine Teflon particles in a synthetic base. From the appearance, it is mostly Teflon. The only drawbacks are that the quantity needed is fairly critical (too much will make the outside of the cube sticky until it all wipes off) and the stuff only comes in 8 oz bottles. This should be enough to lubricate over 1000 cubes. Available in the automotive department at Bradlees in Boston.  Date: 24 NOV 1980 0451-EST From: ALAN at MIT-MC (Alan Bawden) Subject: Old cube mail no longer on-line. To: CUBE-HACKERS at MIT-MC There is a klutz amoung us. This is twice that the file of old cube lovers mail has been deleted from my directory. I retrieved it last time and put it in ALAN;CUBE OMAIL and let the new messages continue to accumulate in ALAN;CUBE MAIL. But somebody just deleted the OMAIL again. I will retrieve it just once more, and if it goes away AGAIN I will just stop bothering.  Date: 24 NOV 1980 1743-EST From: ALAN at MIT-MC (Alan Bawden) To: CUBE-HACKERS at MIT-MC ALAN;CUBE OMAIL is back on disk as ALAN;CUBE XXMAIL .  Date: 24 NOV 1980 1926-EST From: DCP at MIT-MC (David C. Plummer) Subject: Plumme Cross To: CUBE-LOVERS at MIT-MC I have an algorithm to get to the Plummer Cross from solved in thirty quarter twists. It may get reduced if I notice I can combine different parts of the algorithm. Description to come in a few days.  Date: 25 NOV 1980 1308-EST From: DCP at MIT-MC (David C. Plummer) Subject: 30 move Plummer Cross algorithm described To: CUBE-LOVERS at MIT-MC Using the {Up Down Left Right Front Back} notation with clockwise normal and ' (single quote) indicating counter-clockwise: (B D)^7 that's right, 14 moves. this sets the back face up and does a couple things to the front. The next two are general tools to play with three corners and nothing else, and people should play with them for their utility. (L D L') U (L D' L') U' This fixes front upper left, which leaves front upper-right, lower-right, lower-left. At this point I would rotate the entire cube CCW about the front-back axis so that these become front upper-left, upper-right, and lower-right, in which case the following transform becomes (in the new coordinates) U' (R' D' R) U (R' D R) but in the old coordinates, we get R' (D' L' D) R (D' L D) (+ 14. 8. 8.) ==> 30. I don't think I made a mistake. Have fun. IF: Plummer == 2*Christman THEN Christman=14 (must be even) and also Plummer=28.  Date: Tuesday, 2 December 1980 10:37-EST From: Jonathan Alan Solomon To: CUBE-LOVERS at MIT-MC cc: Solomon at RUTGERS Subject: Source to CUBE to run it locally (!) Could someone please point to where the source to the CUBE program lives? Some users here want to use it and don't have access to the net. I have the newest MACLISP, so there is no problem there. Thanks! JSol  Date: 2 December 1980 1040-est From: Bernard S. Greenberg Subject: Re: Source to CUBE to run it locally (!) To: SOLOMON at Rutgers Cc: CUBE-LOVERS at MIT-MC, Solomon at Rutgers I repeat for all those interested, the :CUBE program, designed and implemented by yours truly, lives in the BSG directory on AI. The file .INFO.;CUBE INFO describes, at its end, the organization of the source modules. I will give anyone any reasonable amount of help bringing it up elsewhere, and would very much like to know if you succeed with it. -bsg  Date: 12/02/80 1059-EDT From: PLUMMER at LL Subject: Cube lube To: CUBE-LOVERS at MIT-MC I have found that talcum powder works. Take apart your cube and sprinkle generously. For a day or two after some powder will leak out, but this brushes off easily. --Bill -------  Date: 3 December 1980 0050-EST From: James.Saxe at CMU-10A (C410JS30) To: CUBE-LOVERS at MIT-MC Subject: 28 qtw Plummer Cross CC: James.Saxe at CMU-10A Message-Id: <03Dec80 005058 JS30@CMU-10A> First, F (LL RR) F B (LL RR) F. Now, rotate the whole cube 1/4 turn clockwise about the up-down axis (so that the top stays on top and the right side becomes the front) and finish up with F (LL RR) F B (LL RR) F (UU DD).  Date: 4 DEC 1980 2300-EST From: DR at MIT-MC (David M. Raitzin) To: CUBE-LOVERS at MIT-MC Hi! I'm new to this list, since I just found out about it, so I might repeat some stuff that has already been said. I guess I want to say two things. First of all, I saw Greenberg's message saying that some guy who has written a book on the cube or something does not believe that solutions in two minutes are possible. Well, even though I can not do it in two minutes (it takes me just under four minutes to do it), my roommate does it in a minute and a half (I timed it, so it's no lie). Second, I've never heard of anyone using the same algorithm that me and my roommate use. We get the top row first, then we get the second row, and finally get the third. The only other solution that I've seen (and/or heard of), and that is from anyone else who has solved the cube, is getting all the eight corners, and then getting the middles. (Greenberg's Lisp machine program also solves it in this manner. In fact, I was quite surprised to see it done in that manner, but as time went on, I realized that everyone I know of does it in that manner too.) Is that true? Does anyone have any other algorithm to the two I've described? Also, I've heard that the most optimum solution to a randomized cube is at most 41 moves. Is that true? And if so, what is the algorithm it uses. I immagine that algorithm was achieved on a computer is that true? As you can see, I have a lot of questions, but this is my first letter to the mailing list. Dave  Date: 4 Dec 1980 2118-PST From: Dave Dyer Subject: solution sequence To: cube-lovers at MIT-MC My original algorithm was: (1) bottom corners by random twisting about (2) bottom sides by random twisting about (3) middle sides mostly by variants of [( r u -r -u )^2 ]^3 with extra "u" operations between the inner and outer loops (4) top sides mostly by variants of ( r u -r -u )^2 ( -f -u f u)^2 with extra reps of phase 3 to swap positions around (5) top corner position by variations on ( r u -r -u )^2 ( r u -r -u )z with extra "b" operations between the major groups (6) top corners orientation mostly by repitions of (gasp!) A = ( r u -r -u )^2 A f A f A f A -f A -f A -f ... which I called the "long walk" My typical solution times with this methodology was 15-20 minutes. I suspect If I operated ar warp speeds (like BSG) it would still be 5 minutes. FORTUNATELY, I have developed better since then. -------  Date: 5 December 1980 0022-est From: Ronald B. Harvey Subject: Your mail of 4 DEC 1980 2300-EST To: DR at MIT-MC Cc: CUBE-LOVERS at MIT-MC Welcome to the Cube-hackers !! Note that this is my first contribution, although I have read all previous mail. First of all, there are other people who solve the cube (I, myself, average about a minute and three quarters). It is also part of the lore that there are people (overseas) who do it in 50 seconds or less. Second, while I personally get eight corners first, and then randomly go about fixing the edge cubies two at a time or so, David Singmaster, who publishes some notes in England (availability in previous mail), included, in his latest edition his algorithm, which proceeds as follows: Solve TOP edges Solve TOP corners Flip cube so that TOP is BOTTOM from now on Solve MIDDLE edges Solve TOP edges Solve TOP corners Finally, in regards to the 'most optimum solution' (also known as God's Algorithm), a person by the name of Morwen B Thistlethwaite (that's from memory - I left my notes at work) is mentioned all over Singmaster's notes as contributing algorithms. Yes, he does use a program, and his algorithm at the time of the 5th Edition took somewhere around 50 moves.  Date: 5 DEC 1980 0132-EST From: SHL at MIT-MC (Stephen H. Landrum) Subject: ADDITION To: CUBE-LOVERS at MIT-MC COULD I BE ADDED TO THIS LIST? THANX. STEPHEN LANDRUM (SHL@MC) P.S. I DIDN'T KNOW WHO TO CONTACT SINCE THERE IS NO 'CUBE-LOVERS-REQUEST'  Date: 5 DEC 1980 0135-EST From: SHL at MIT-MC (Stephen H. Landrum) To: CUBE-LOVERS at MIT-MC I ALSO SOLVE THE CUBE TOP ROW, MIDDLE, THEN BOTTOM. ONE TIME I MANAGED IT IN 58 SEC, BUT I THINK THAT WAS JUST A FREAK CASE. MY SECOND BEST TIME IS 1 MIN. 42 SEC, I AVERAGE ABOUT THREE MINS. STEPHEN LANDRUM  Date: 5 DEC 1980 0250-EST From: ALAN at MIT-MC (Alan Bawden) To: SLH at MIT-MC CC: CUBE-LOVERS at MIT-MC I have added you to the cube-lovers mailing list. Old mail is archived in MC:ALAN;CUBE MAIL. I'll Cc this message to CUBE-LOVERS so that anyone else looking through the (recent) old mail, will find out that I am a person to mail "add me" requests to.  Date: 5 Dec 1980 00:29 PST From: Woods.PA at PARC-MAXC Subject: Re: DR's message of 4 DEC 1980 2300-EST To: DR at MIT-MC (David M. Raitzin) cc: CUBE-LOVERS at MIT-MC I've hardly ever found two people who solve the same way. The most common method I've found around Stanford is to go for all the edges, then the corners. My own method is to get the top corners, then the top edges (via operations like -l r f^2 l -r & similar tweaks) then three of the middle edges (via things like l^2 u^2 r^x u^2 l^2, where x=1, 2, or -1), then get the other four corners in the right place (requiring at most one corner-swap, for which I have a fairly simple macro), then get those four corners oriented using the "rFUfuR" commutator macro, which also randomly alters the remaining middle edge, then get the last five edges, then flip edges as necessary. My typical time is about 5 minutes. "Best" times are meaningless, since anybody can luck out once or twice; the best measure of your solving speed (in my opinion) is your WORST solving time over your most recent ten or so attempts. Of course, for real fun, pick some pretty pattern and solve to it without going through the normal solved state! -- Don.  Date: 5 DEC 1980 1240-EST From: DCP at MIT-MC (David C. Plummer) Subject: My 6 faces worth To: CUBE-LOVERS at MIT-MC The technology exists to solve the cube in any way possible. I.E., tools exists to do the most primitive of operations to individual cubies (rotating corners, flipping edges, moving three corners around, and moveing trhee edges around). Using these, any method of solving is possible (even solving a corner, then the edges around that corner, then the corners around those edges, etc, all the way toward the other corner). Since everybody tends to develop their own technology, they develop their own favorite way of solving. Personally, at present, I solve the top edges three of the top corners three of the middle edges the last top edge Up until here the algorithms are quite simple and now I only have the bottom and one middle edge, which I solve in whatever way looks most promising. Using this sequence, I am consistently on the order of three minutes (tending toward 2.5 as I get more familiar with the method) Intuitively, I believe that God's algorithm is less than 35 or so, and I would not be surprised if it is less than 30. Under 25 would really surprise me.  Date: 5 Dec 1980 1038-PST (Friday) From: Mike at UCLA-SECURITY (Michael Urban) Subject: Cube approach survey? To: cube-lovers at mc Top edges, top corners, middle edges, bottom edges, bottom corner placing, bottom corner orientation. Takes me about 4 minutes, but I'm out of practice. None of the steps requires any real unusual tools. I suspect I got in the habit of solving the cube in that order because the initial challenge was "get one face". Then I realized that the next step must surely be "get one face so that it matches the center faces of the sides". The beauty of the cube is that, unlike Instant Insanity or its cousins, the Cube's solutaion can not be stumbled across by accident. Instead, it's a learning experience, as you learn to manipulate things, then to manipulate cubies without messing up what you already have done. This gets progressively more sophisticated as more of the cube comes into place. Definitely the most satisfying puzzle I've ever dealt with. However, I'd be interested to find out how many as-yet-unsolved Cubes are sitting even now on the shelves of disgusted customers who thought they were great puzzlists because they solved Soma, but weren't patient enough to figure out how to get those last two corner cubies oriented right. Mike -------  Date: 5 December 1980 16:28-EST From: Alan Bawden Subject: cube-lovers-request To: CUBE-LOVERS at MIT-MC OK, I have created the cube-lovers-request mailing list.  Date: 5 December 1980 1848-est From: David C. Plummer Subject: That 28 move Plummer Cross To: Cube-Lovers@MIT-MC Something I noticed about that 28 move algorithm to get to the Plummer Cross. Any twist can be the first one made to take the Cross back to home. The last instructions are (UU DD) which can obviously be (UU D'D'), (DD UU), and (DD U'U'), so possible backward applications of the algorithm can start with U,D,U',D'. Add in the three way rotation symmetry of the cross and you can get all 12 moves as viable first moves. So, any move takes you closer to home (by this algorithm), so it has the chance of being the most distant from home. This requirement (any moves takes you closer) was mentioned by ALAN some time ago. (I don't hold that the Plummer Cross is the most distant.)  Date: 5 December 1980 19:10 est From: Greenberg.Symbolics at MIT-Multics Subject: Re: That 28 move Plummer Cross To: Plummer.SIPBADMIN at MIT-Multics (David C. Plummer) cc: Cube-Lovers at MIT-MC In-Reply-To: Message of 5 December 1980 18:48 est from David C. Plummer It is a corollary of what Plummer just said, that the "maximally distant" configuration, which is God's number of moves (the maximal length of God's algorithm) would then be no more than 28 moves from home (bounding God's number thusly).  Date: 5 Dec 1980 1624-PST From: Dave Dyer Subject: Re: Re: That 28 move Plummer Cross To: Greenberg.Symbolics at MIT-MULTICS cc: cube-lovers at MIT-MC In-Reply-To: Your message of 5-Dec-80 1910-PST Not true! It may be just a local maximum. -------  Date: 5 December 1980 21:15 est From: Greenberg.Multics at MIT-Multics Subject: Re: Re: That 28 move Plummer Cross To: Dave Dyer cc: cube-lovers at MIT-MC In-Reply-To: Message of 5 December 1980 19:24 est from Dave Dyer No. It is DEFINITIONALLY a local maximum, because any move moves it "closer". DCP was asserting its candidacy for the "ultimate" maximum, if not its fact.  Date: 6 Dec 1980 13:40 PST From: McKeeman.PA at PARC-MAXC Subject: Re: That 28 move Plummer Cross In-reply-to: Plummer.SIPBADMIN's message of 5 December 1980 1848-est To: David C. Plummer cc: Cube-Lovers@MIT-MC, Greenberg.Symbolics at MIT-MULTICS, DDYER at USC-ISIB, Hofstadter at SU-AI David, Interesting observation! Your argument about the Plummer Cross being a local maximum in QTW metric holds for any completely symmetrical configuration of the cube, independent of the algorithm used to reach it. There are a lot of them (including "home"). It raises the question: Can the maximally distant point be proven to be symmetric? If so, the search for a bound is much simplified. Bill  Date: 6 Dec 1980 13:57 PST From: McKeeman.PA at PARC-MAXC Subject: A Top-Middle-Bottom solution To: CUBE-LOVERS at MIT-MC Since I had this writeup in "sendable" form, I thought I would put it out. Most of you already have this one or better, so just delete it if you are not interested. --------------------------- Date: 19 Jun. 1980 5:57 pm PST From: McKeeman To: McKeeman File: [Ivy]Rubik.txt Kertesz' Algorithm for the Rubik Cube. McKeeman -- June 19, 1980 Rubik's Cube is a 3x3x3 cube such that each of its 3x3 planes can rotate freely about its perpendicular axis. There are 54 visible squares, colored in six sets of 9. There are 26 visible cubelets, each colored uniquely. (Commercially available cubes are not colored consistently.) The edge cublets have two colors; the corner cublets have three. The inventor is a Hungarian architect; my solution comes from Adam Kertesz, a Hungarian programmer I met in Poland. It may be less precise than you like, but without pictures it is just too much to give all the details. With a little struggle this should get you to a solution. The Problem: From an arbitrary starting position, arrange the cube so that each 3x3 surface is of a uniform color. Notation: One can limit moves to 90o rotations of the six surfaces without losing anything. It is convenient to describe the moves in terms of the orientation of the cube rather than the color. The names of the faces are: U=up D=down R=right L=left F=front B=back. A move of R, for example, is a 90o clockwise rotation of the right face, RR = R^2 is 180o, and R'=RRR= R^3 is 270o, or 90o counterclockwise. For any move M, M'M is a no-op. Macros: There a lot of macro-moves that are useful and interesting. I will use six here: X = R'F'UFUF'U'FRUU Xr = LFU'F'U'FUF'L'UU Y = RFFDFD'FFR' Yr = L'FFD'F'DFFL Z = R'DRFDF' Z' = FD'F'R'D'R It is not trivial to use these things. The general idea is to decide on the orientation of the cube, and then follow the directions mechanically. Note that the color of the central square of every face is unchanged during a macro. That is the easiest way to keep from getting messed up. I mumble to myself "Red is Up, Blue is Front" or some such thing each time just before I dive into a macro. I find it is even helpful to close my eyes during a macro when doing it from memory! Kertesz' Algorithm: Generally speaking the idea is to get the cube right one layer at a time. They get increasingly hard (tedious) because you must be careful not to destroy work already done. ---------------- Layer 1: Pick Up color. Step 1. Do Up edges. The four Up edges must be moved between the two center squares that have the same colors: For each edge do (a) hold target position UF (i.e., up front, nearest you), (b) get needed cubelet into bottom layer, (c) rotate it under target position using D^n, (d) do F^2, in which case you are done or it needs flipping, (e) in which case F'UL'U' finishes it. You should now have the top "+" shape correct and matching the side center squares. Step 2. Do Up corners. The four Up corners must be moved so that all three of their colors match their neighbors. For each corner do (a) hold target position FUR (i.e., up right, nearest your right hand), (b) get needed cubelet into bottom layer, (c) rotate it under target position using D^n, (d) either DFD'F' or D'R'DR will bring it up, (e) it may need rotation, in which case use Z for 120o clockwise, Z' for counterclockwise. You should now have the top layer correct and matching the side center squares. ---------------- Layer 2: The four remaining edges on layer two are next. Y and Yr leave Up surface invariant. For each layer 2 edge target do (a) get needed cubelet into down layer (using Y or Yr if needed), (b) rotate it 90o from under target using D^n, matching color of nearest center square, (c) hold needed cubelet DF (d) if it needs F, do Y to bring it into position, (e) if it needs F', do Yr. ---------------- Layer 3: Turn puzzle over. The macros X and Xr are used over and over again. The sequence of events is to place the four up corners, place the four up edges, flip the edges if necessary, and finally rotate the corners if necessary. Step 1. Place Up corners. One can always be rotated into position with U^n. Among other things, X will exchange the RFU and RBU corners. At most four applications of X will place all four corners. It takes a little forethought. Step 2. Place Up edges. X will also exchange the LU and FU edges. Xr will exchange the RU and FU edges and the LFU and LBU corners. Used in pairs X and Xr can exchange edges without changing corners. That is, one use exchanges corners, the next carefully chosen one restores them. Step 3. Flip Up edges as necessary. X^2 will flip both LU and FU edges. Step 4. Rotate Up corners as necessary. The macro ZU^nZ'U^-n will rotate two Up corners, one 120o and one 240o. Place the one needing 120o in FUR, do Z, do U^n to bring one needing 240o into FUR, do Z'U^-n. Don't look at the mess after the first rotation; it will destroy your morale. ----------------- You should now be done. It took me a couple of days to be able to solve the thing reliably. Enjoy. P.S. Real Rubniks will want to write for: Notes on Rubik's 'Magic Cube', David Singmaster, Mathematical Sciences and Computing, Polytechnic of the South Bank, London SE1 0AA, England (send $5). ------------------------------------------------------------  Date: 6 Dec 1980 14:16 PST From: McKeeman.PA at PARC-MAXC Subject: Re: That 28 move Plummer Cross In-reply-to: Greenberg's message of 6 December 1980 1644-est To: Bernard S. Greenberg cc: McKeeman, Cube-Lovers at MIT-MC, DDYER at at MIT-Multics, Plummer.SIPBADMIN at MIT-Multics I do not follow the reasoning. It seems quite possible that there is a non-symmetric local maximum. In any case, it is not a definition, but rather a proof that needs doing. It is certainly true that a move from a non-symmetric configuration will either a. get closer to home b. stay the same distance from home c. get further from home. Furthermore, it is obvious that there are usually both (a) and (c) cases. What I don't see is the argument that there must always be a (c) case. One way of looking at it is that there is an enormous graph connecting all solutions by one QTW moves. Nearly all nodes are non-symmetric. You argue that from every non-symmetric node there is a move to a node that is further from home. I am willing to be convinced, but am not yet, and mere probability favors the following: Conjecture: There exists a non-symmetric configuration from which every move leads to a position that is closer to home. Bill  Date: 6 Dec 1980 1428-PST From: Dave Dyer Subject: Re: That 28 move Plummer Cross To: McKeeman.PA at PARC-MAXC In-Reply-To: Your message of 6-Dec-80 1340-PST Remailed-date: 6 Dec 1980 1429-PST Remailed-from: Dave Dyer Remailed-to: cube-lovers at MIT-MC While I believe it is true that all symmetric positions are local maxima, It is definitely NOT true that all local maxima are symmetric. As a counterexample, consider that a repeated permutation is at a local maximum 1/2 way through its period. So for example, the Idempotent ( r u -r -u )^6 is at a familiar but unsymmetric local maximum halfway through. -------  Date: 6 DEC 1980 1745-EST From: DCP at MIT-MC (David C. Plummer) Subject: Re: That 28 move Plummer Cross To: McKeeman.PA at PARC-MAXC CC: CUBE-LOVERS at MIT-MC Date: 6 Dec 1980 13:40 PST From: McKeeman.PA at PARC-MAXC In-reply-to: Plummer.SIPBADMIN's message of 5 December 1980 1848-est USC-ISIB, Hofstadter at SU-AI David, Interesting observation! Your argument about the Plummer Cross being a local maximum in QTW metric holds for any completely symmetrical configuration of the cube, independent of the algorithm used to reach it. There are a lot of them (including "home"). It raises the question: Can the maximally distant point be proven to be symmetric? If so, the search for a bound is much simplified. Bill I don't know exactly where to start my comments. For one thing, the Plummer cross is not totally symmetric. What I stated (actually ALAN, but I seem to be the culprit now): It is necessary for the maximal state to have the quality that any quarter twist brings you closer to home. It is also true that any symmetric state also has this quality. What I noted was that the 28 move algorithm given shows that the Plummer Cross also fulfills this. HOWEVER, there may exist a 26 or 24 move algorithm such that only 6 of the 12 possible moves may be done first in order to fix it. About your question, even if you could prove the maximal distant point is symmetric, we still cannot prove how far away a configuration is away from home. If you could prove that, you would also God's Algorithm.  Date: 6 DEC 1980 1748-EST From: DCP at MIT-MC (David C. Plummer) Subject: food for twisting To: CUBE-LOVERS at MIT-MC Here is a piece of food for thought: why can't there be two (in general more than one) maximally distant point). For example, the 24 Plummer Crosses and the "every edge flipped" configuration. And the obvious question is: how far apart are these maximally distant types. Between different types is probably more interesting than between different "reflections" of the same type.  Date: 6 DEC 1980 1846-EST From: DCP at MIT-MC (David C. Plummer) Subject: Re: That 28 move Plummer Cross To: McKeeman.PA at PARC-MAXC CC: CUBE-LOVERS at MIT-MC Date: 6 Dec 1980 14:16 PST From: McKeeman.PA at PARC-MAXC In-reply-to: Greenberg's message of 6 December 1980 1644-est Plummer.SIPBADMIN at MIT-Multics I do not follow the reasoning. It seems quite possible that there is a non-symmetric local maximum. In any case, it is not a definition, but rather a proof that needs doing. It is certainly true that a move from a non-symmetric configuration will either a. get closer to home b. stay the same distance from home c. get further from home. Furthermore, it is obvious that there are usually both (a) and (c) cases. What I don't see is the argument that there must always be a (c) case. Bill Except from solved, there always exists a move taking you closer to home. Always: There is NEVER (by the QTW metric) a move that keeps you the same distance, and from the maximally distant state it is IMPOSSIBLE to get further from home. Notice I have said nothing about symmetry.  Date: 6 DEC 1980 1841-EST From: DCP at MIT-MC (David C. Plummer) Subject: Re: That 28 move Plummer Cross To: DDYER at MIT-MC CC: CUBE-LOVERS at MIT-MC Date: 6 Dec 1980 1428-PST From: Dave Dyer In-Reply-To: Your message of 6-Dec-80 1340-PST Remailed-date: 6 Dec 1980 1429-PST Remailed-from: Dave Dyer Remailed-to: cube-lovers at MIT-MC While I believe it is true that all symmetric positions are local maxima, It is definitely NOT true that all local maxima are symmetric. As a counterexample, consider that a repeated permutation is at a local maximum 1/2 way through its period. So for example, the Idempotent ( r u -r -u )^6 is at a familiar but unsymmetric local maximum halfway through. ------- I think what most of mean by LOCAL MAXIMUM is that ANY twist will bring you closer to home. The proposed counterexample can be taken farthur away from home (eg (R U -R -U)^3 then D)  Date: 6 Dec 1980 16:30 PST From: McKeeman.PA at PARC-MAXC Subject: Re: That 28 move Plummer Cross In-reply-to: Greenberg's message of 6 December 1980 1836-est To: Bernard S. Greenberg cc: McKeeman, Cube-Lovers at MIT-MC, Plummer.SIPBADMIN at MIT-Multics OK. There may be non-symmetric local maxima. I feel better; thought maybe I was just so dense I couldn't grok the obvious. As for a definition of symmetric: For the purposes of local maximum argument, each of the 6 basic QTW must have the same effect. That is, the configuration must be isomorphic under the rotation group of the whole cube (of order 24). Bill  Date: 6 Dec 1980 16:42 PST From: McKeeman.PA at PARC-MAXC Subject: Re: That 28 move Plummer Cross In-reply-to: DCP's message of 6 DEC 1980 1745-EST To: DCP at MIT-MC (David C. Plummer) cc: McKeeman, CUBE-LOVERS at MIT-MC David, Suppose one could prove local maxima had configurations that were invariant under the rotation group of the whole cube. (I am not at all sure it is even true.) There are a small number of such symmetric configurations, and they could probably be easily tabulated. One of them would have to be maximally distant from home. Thus if we had a QTW solution for each of them, the maximum over that set would bound God's Algorithm. I see no reason to believe that a QTW cannot take you between two solutions that are at the same distance. As DPC pointed out, there are a lot of even identity paths. E.g., (RUR'U')^6. The two furthest points on the path are (by symmetry) necessarily equally distant, yet connected by a QTW. Bill  Date: 7 December 1980 00:47-EST From: Alan Bawden Subject: Maximally distant states To: McKeeman.PA at PARC-MAXC cc: CUBE-LOVERS at MIT-MC Date: 6 Dec 1980 16:42 PST From: McKeeman.PA at PARC-MAXC I see no reason to believe that a QTW cannot take you between two solutions that are at the same distance. As DPC pointed out, there are a lot of even identity paths. E.g., (RUR'U')^6. The two furthest points on the path are (by symmetry) necessarily equally distant, yet connected by a QTW. I am not sure I understand what you are trying to say here. But I do know that a single quarter twist can never leave you the same distance from anything. This is because a single quarter twist is a odd permutation of the "stickers". Thus if you are N quarter twists away from something, a single quarter twist will leave you N-1 or N+1 quarter twists away. (And hence the proof that any quarter twist will bring you closer from a maximally distant state.) I'm not sure how to apply this to your statement that perhaps a "QTW" can take you "between two solutions that are at the same distance".  Date: 7 DEC 1980 0108-EST From: MJA at MIT-MC (Michael J. Aramini) Subject: maximally distant state To: CUBE-LOVERS at MIT-MC well it is possible that to maximally distant states are half twist apart also if you count half twists as one twist (i dont, but its still worth thinking about) does that change the set of maximally distant states? also it is possible that there exists states for which all directions lead closer to home (and twist put the cube in a state closer to home) but the state is not necessarily maximally distant (to use a continous analogy, think of think of a hill in a funtion of two variables, that is not necessarily the maximum value of the function)  Date: 7 DEC 1980 0724-EST From: DCP at MIT-MC (David C. Plummer) Subject: maximally distant state, setting the record straight To: MJA at MIT-MC CC: CUBE-LOVERS at MIT-MC Date: 7 DEC 1980 0108-EST From: MJA at MIT-MC (Michael J. Aramini) well it is possible that to maximally distant states are half twist apart WRONG! (I assume you meant "two" for "to" and typo'ed). Read ALAN's previous message. In the half twist metric, there exist odd distances away, and there exist even distances away. A QTW takes the cube from odd to even or from even to odd. The maximally distant state is the state such that the fewest number of QTW required to solve it is maximized. This must be odd OR even, and thus, two states that are maximally distant must be both odd or both even, which means the distance between them is even, or an EVEN number of QTW. A single QTW is ODD, and thus cannot separate maximal states. also if you count half twists as one twist (i dont, but its still worth thinking about) does that change the set of maximally distant states? Maybe it does, maybe it doesn't. It is much harder to tell because counting half twists has no analog to the QTW odd/even property of distance, and this is one reason several of us don't count half twists. For example, (R L R) and (L [RR]) are equivalent manipulations, but in half twist counting, one is three and the other is two moves. (assume [] means grouping two moves into one.) also it is possible that there exists states for which all directions lead closer to home (and twist put the cube in a state closer to home) but the state is not necessarily maximally distant (to use a continous analogy, think of think of a hill in a funtion of two variables, that is not necessarily the maximum value of the function) We have been saying this all along! Simple example: (RRLL UUDD FFBB) is a local max (any twist takes you closer), and it is definitely not absolute max (abs max must be at least 21 from combinatoric arguments).  Date: 6 December 1980 1836-est From: Bernard S. Greenberg Subject: Re: That 28 move Plummer Cross To: McKeeman.PA at PARC-Maxc Cc: Cube-Lovers at MIT-MC, Plummer.SIPBADMIN at MIT-Multics I confess to not only having no proof to this proposition, but no longer believing it. The false equivalence of "symmetric" and "locally maximal" seemed to me visually obvious, given that all symmetric positions are in fact locally maximal. If one believes this subconsciously, it is but a short step to the conscious "proof" that all asymmetric positions are but "on the way" to a symmetric, maximal one; this of course, is bogus. Now a good definition of symmetric is also needed here; I assume that what we have been meaning is that all rotations of the cube are Isomorphic. Note that the Plummer and Christman crosses don't qualify under this definition. What is a good definition?  Date: 6 December 1980 1644-est From: Bernard S. Greenberg Subject: Re: That 28 move Plummer Cross To: McKeeman.PA at PARC-Maxc Cc: Cube-Lovers at MIT-MC, DDYER at at MIT-Multics, Plummer.SIPBADMIN at MIT-Multics The maximally distant point is definitionally symmetric. It was Bawden (ALAN) who first stated this; were it NOT symmetric, there would be some twist you could make that would make it WORSE as opposed to the ones that would make it better. Were this the case, it would then not be a maximum.  Date: 7 December 1980 1218-est From: Bernard S. Greenberg Subject: Symmetry of configurations To: McKeeman.PA at PARC-MAXC Cc: CUBE-LOVERS at MIT-MC The definition of symmetry proposed by you does not seem adequate. Plummer's Cross is NOT symmetrical by that definition. Given Plummer's Cross in any orientation, there are plenty of elements of the 24-move whole-cube rotation group which will shift it to something NOT isomorphic through a substitution of colors to the original. Yet, we know, intuitively, that the CP is "highly symmetric", and it is a local maximum. It is as though I were saying that this equivalence of all twists "out" of this position almost defined symmetry.....  Date: 7 December 1980 1401-est From: Bernard S. Greenberg Subject: Re: That 28 move Plummer Cross To: DDYER at MIT-Multics Cc: McKeeman.PA at PARC-Maxc, CUBE-LOVERS at MIT-MC I do not believe that (r u r' u')^3 is a local maximum. An move other than r, u, r', u', (e.g., l) seems to pervert it further than any of the four which bring it back.  Date: 7 December 1980 1620-est From: Bernard S. Greenberg Subject: Re: Maximally distant states To: McKeeman.PA at PARC-Maxc Cc: CUBE-LOVERS at MIT-MC, ALAN at MIT-MC King of bogosity! Fencepost errors abound. Here's an "even" identity transform for you: (R R)^2. Halfway through this transform is ONE state. There are no "two furthest points on the path", there is one. There ARE, however, two ways out of it. And similar to all even identity transforms.  Date: 7 December 1980 16:58-EST From: Alan Bawden To: CUBE-LOVERS at MIT-MC, Greenberg at MIT-MULTICS cc: ELLEN at MIT-MC To sum up everything we know: 1) A Symetric position is a local maximum. 2) A maximally distant state is a local maximum. 3) If Plummer's cross is 28 Qs away from home, then it is a local maximum. All the other implications that have been flying around are unproven as far as I know. I welcome PROOFS of anything else that I might not be aware of. The volume of air-headed speculation on this subject has reached the point where the MC mailer is so overloaded with gubbish that a "CUBE-LOVERS Digest" is being considered. Now that is just plain silly given that NORMALLY we only get one or two pieces of mail a week through this list. If you don't understand why one of the three facts above are true, DON'T send mail to the whole list! Look through the old mail (they are all explained there) or send JUST ME a question, and I will try and answer it.  Date: 8 December 1980 1309-EST (Monday) From: Guy.Steele at CMU-10A To: McKeeman.PA at PARC-MAXC Subject: Re: That 28 move Plummer Cross CC: cube-lovers at MIT-MC In-Reply-To: McKeeman.PA@PARC-MAXC's message of 6 Dec 80 19:42-EST Message-Id: <08Dec80 130910 GS70@CMU-10A> A QTW cannot take you between two positions of equal distance, I believe -- is there not some parity quantity obeyed by QTW's (net twist of the six center cubies)? If so, then there cannot be two positions of equal distance separated by a QTW, for then there would be an odd length identity transformation, which would violate parity. (In the example you gave, there are *not* two positions of equal distance, but only one -- the halfway point.)  Date: 8 December 1980 1117-EST (Monday) From: Guy.Steele at CMU-10A To: ddyer at USC-ISIB Subject: Re: That 28 move Plummer Cross CC: cube-lovers at MIT-MC In-Reply-To: Dave Dyer's message of 6 Dec 80 17:28-EST Message-Id: <08Dec80 111740 GS70@CMU-10A> The position halfway through the cycle of a permutation need not be a local maximum, since moves other than the permutation cycle might take it further away. It is more like a saddle point (most positions probably are in that class: at least two moves take it closer, and at least two take it further). There is one symmetric position which is not a local maximum: the solved state!  Date: 8 Dec 1980 17:03 PST From: McKeeman.PA at PARC-MAXC Subject: A Proposed Definition of Symmetry To: cube-lovers at MIT-MC The discussion of local maxima for the Q measure of distance led to an informal use of symmetry. It is not clear to me just what symmetry is needed to carry through the maxima argument but I suggest the following is sufficient (although perhaps too restrictive). Let C by the rotation group of the cube (closure of IJK: order 24) Let G be Rubik's group (closure of UDRLFB: order 10^19 or so) Both groups can be represented as a permutation group on [0, 1, ...53] for some arbitrary numbering of the 54 faces. We can also use the names UDRLFB for the six colors; where the association is made once and for all for any given physical puzzle. Like U=red, F=blue, etc.). The elements of g are 1-1 with the observable configurations of the standard cube; and in fact are the recipes to reach the configurations from "home". g' is the "solution" that returns g to home. The elements of G*C are also 1-1 with the observable configurations except now the correspondence must also take into account the observed orientation of the cube. Each g in G is represented by a permutation of the cubelet faces. Each face in g is a fixed color. For color X, let X[g] be the set of faces of g colored X. |X[g]| = 9. Let Coloring[g] = {U[g], D[g], R[g], L[g], F[g], B[g]}. Then g is totally symmetric if for all c in C, Coloring[gc] = Coloring[g]. ---- It is true that "home" and UUDDRRLLFFBB are totally symmetric by this definition. "home" is a minimum (special case). UUDDRRLLFFBB is a local maximum. Questions: Is there a simpler equivalent definition? How many totally symmetric configurations are there? Is there a less restrictive definition that guarantees local maxima?  Date: Mon, 8 Dec 1980 1956-CST Message-id: <345171394.17@DTI> From: aramini at DTI (Michael Aramini) To: cube-lovers@mc Subject: "notes on rubikics cube" booklet can someone please tell me the address of the seller of this booklet in England (I know a can find it in the archive file, but i prefer not to try to edit it at a mere 300 baud, without the benefit of being able to do an i-search (local host traps ^s's) also, is it better to order it from this english address, or from the one in virginia? also, what is the current price for the booklet from each of these 2 sources? -----  Date: 9 December 1980 1638-EST (Tuesday) From: Dan Hoey at CMU-10A To: McKeeman.PA at PARC-MAXC Subject: Re: A Proposed Definition of Symmetry CC: Cube-Lovers at MIT-MC In-Reply-To: McKeeman.PA@PARC-MAXC's message of 8 Dec 80 20:03-EST Message-Id: <09Dec80 163821 DH51@CMU-10A> Given a subroup G of permutations, we may define a cube position P to be G-symmetric if every permutation in G preserves P up to color relabelling. Explicitly, if x and y are two facelets which have the same color in position P, then g(x) and g(y) also have the same color in P. Consider, for instance, the group R of whole-cube moves. The Pons Asinorum is R-symmetric. Any whole-cube move moves the set of blue facelets to positions occupied (before the move) by facelets of some single other color. In fact, even if the cube were reflected, this would be true. This can be verified by looking at one blue facelet of the cube and realizing that you know from that alone where all the other blue facelets are. Letting the M denote the group composed of R augmented by the set of whole-cube mirror reflections. The Pons Asinorum is also M-symmetric. McKeeman has stated that any R-symmetric position (with the exception of the solved state) is a local maximum. I do not know if this is true, but I can show that any M-symmetric position (with the same exception) is a local maximum. Consider a robot cubenik which knows how to do whole-cube moves, but can only QTW the "up" face. Clearly, this robot has no problems, because it can move any face to the top, perform U or U', and move it back. The robot could get along without U' by doing U^3 instead, but if we're counting QTWs it's not going to win any races. Solution? Build a transdimensional robot which can perform whole-cube reflections. This robot performs U' by reflecting the cube, performing U, and reflecting it back. The point of this parable is that for any two QTWs x and y, there is an element m in M for which y = (m x m'). Note also that for any m in M, the permutation (m x m') is a QTW. Let P be an M-symmetric position, and let (x1 x2 ... xn) = P' be the shortest solution of P in QTWs. Assume that P is not the solved position, so n > 0. For any QTW y, I will demonstrate an n-step solution of P which begins with y. Write y = (m x1 m'). Since P is M-symmetric, (P m) is a relabelling of P. This implies that (P m P') and therefore (P m P' m') are relabellings of I. Therefore the sequence ((m x1 m') (m x2 m') ... (m xn m')) = (m P' m') will essentially solve P, up to a whole-cube move. The existance of an n-step solution starting with an arbitrary QTW y implies that P is a local maximum. There is a twelve-element subgroup T of M which will suffice instead of M for this argument. Representing elements as permutations of faces, T is generated by the permutations (represented as cycles): (F L U)(R D B) -- Rotating the cube about the FLU-RBD axis (F B)(U R)(L D) -- Rotation exchanging corners FLU and RBD (L U)(R B) -- Reflection in the LU-RB plane Question: Does there exist a position other than the solved position and the Pons Asinorum which is T-symmetric or R-symmetric?  Date: 9 December 1980 23:57-EST From: Alan Bawden Subject: Re: A Proposed Definition of Symmetry To: Hoey at CMU-10A cc: CUBE-LOVERS at MIT-MC Date: 9 December 1980 1638-EST (Tuesday) From: Dan Hoey at CMU-10A There is a twelve-element subgroup T of M which will suffice instead of M for this argument. Representing elements as permutations of faces, T is generated by the permutations (represented as cycles): (F L U)(R D B) -- Rotating the cube about the FLU-RBD axis (F B)(U R)(L D) -- Rotation exchanging corners FLU and RBD (L U)(R B) -- Reflection in the LU-RB plane AH! Excellent! (I believe you mean that last permutation to be (L U)(R D).) It took me a while to realize that this is the subgroup of M that leaves the FLU-RBD "diagonal" fixed. Question: Does there exist a position other than the solved position and the Pons Asinorum which is T-symmetric or R-symmetric? Hmm. I hadn't realized that we don't really know that many symmetric positions. I have another favorite pattern that happens to be fully M-symmetric. It is the pattern obtained by "flipping" all of the edge cubies: U B U L U R U F U L U L F U F R U R B U B B L F L F R F R B R B L L D L F D F R D R B D B D F D L D R D B D This pattern has another interesting property, it is the only other permutation besides the identity that commutes with every other element of the cube group! I have often thought that this position is a good candidate for maximality. Dave Plummer has shown that this position can be also be reached in 28 moves...  Date: 10 DEC 1980 0157-EST From: DCP at MIT-MC (David C. Plummer) Subject: The 28 QTW all-edge-flipper mentioned by ALAN To: CUBE-LOVERS at MIT-MC Indeed it can be done in 28. Tool: flip the top edges and the bottom edges: (R L) (U D) (F B) (R L) (U D) (F B) /\ || To do the other four, insert the following things at the indicated place (u b') (u' D b' u' d l' u' d f' u' d r') (b u') There may be another place to put this to find a shorter path. Those with time are free to try and find one.  Date: 10 DEC 1980 0834-EST From: DCP at MIT-MC (David C. Plummer) Subject: A configuration symmetric wrt the first QTW To: CUBE-LOVERS at MIT-MC I believe the following is symmetric in the sense that any QTW will bring you closer to home: All corners are rotate, and letting + indicate clockwise and - counterclockwise, each face has the following corner configuration +- -+ (and all the edges are intact) a total map of the cube corners might look like +- -+ +- -+ +- -+ -+ +- -+ +- +- -+ Each face is essentially the same: edges OK and all corners rotated so that opposite corners are rotated in the same direction. It is rather intuitive to me that rotating a face clockwise is the same as rotating the face counterclockwise. This fulfills the condition needed for maximality, but what flavor of symmetric is it (if the symmetry is easily describable). Also, does anybody have a 28 QTW algorithm (OR LESS!!) to go between solved and this position.  Date: 14 December 1980 1916-EST (Sunday) From: Dan Hoey, Jim Saxe To: Cube-lovers at MIT-MC Subject: Symmetry and Local Maxima (long message) Reply-To: Dan Hoey at CMU-10A Message-Id: <14Dec80 191649 DH51@CMU-10A> Symmetry and Local Maxima -- Dan Hoey Jim Saxe 1. Introduction =============== In this note, we attempt to give a uniform treatment of the issues raised in the recent discussions of symmetry and local maxima. We have attempted to restate and justify the correct observations on these subjects that have been made in mail to cube-lovers in recent days and also to refute a number of incorrect ones. We include a description of 71 local maxima, which we believe to be all of the local maxima that can be proven using known techniques other than exhaustive search. We let G denote the "Rubik group", consisting of all transformations of the cube which can be achieved by twisting faces. G does not include transformations which require movements of the whole cube. Also, G does not take account of the orientations of the face centers. We will defer discussion of the Supergroup, in which face center orientations are significant (but whole-cube motions still excluded), to Section 5 of this message. We will sometimes (particularly towards the end of this message) take the liberty of identifying a transformation with the position reached by applying that transformation to SOLVED. We let Q = {U, D, L, R, F, B, U', D', L', R', F', B'} be the set of all possible quarter-twists. Q is a subset, but not a subgroup, of G. The set {U, D, L, R, F, B} of all clockwise quarter-twists is called Q+, and the set {UU, DD, LL, RR, FF, BB} of all half-twists is called Q2. The "length" of an element s of G (denoted |s|) is the length of the shortest sequence of quarter- twists whose product is s. The "distance" between two elements, s and t, of G is the length of the shortest r such that t = s r. Note that the length of s is same as the distance between s and the identity permutation. Note also that we are measuring distance in the "quarter-twist metric." We defer discussion of the "half-twist metric" to Section 5. Two elements, s and t, of G are "neighbors" if there is some q in Q such that t = s q (i.e., if the distance between s and t is 1). An element, s, of G is said to be a "local maximum" if no neighbor of s is longer than s. It is a consequence of parity considerations that all neighbors of any local maximum, s, have the same length, namely |s| - 1. Conversely, any element s of G (except for the identity permutation) whose neighbors are all equally long must be a local maximum. [Anyone who *still* doesn't understand why neighbors cannot be equally long in the quarter-twist metric should either send mail to one of the authors, or learn about even and odd permutations from a book on group theory and think about how a quarter-twist permutes the positions of the corner cubies.] 2. Symmetry =========== It has been asserted that any "symmetric" element of G must have all its neighbors equally long and must therefore be a local maximum (or the identity). The first occurrence of this assertion in cube-lovers mail was by Alan Bawden in his message of 10 Sep 1980, 11:09 pm PDT. The recent spate of messages on this subject has made it clear that Bawden's notion of symmetry was not clearly defined. In what follows, we make the notion of symmetry more precise and categorize those kinds of symmetry for which the above assertion is correct. We let M denote the group generated by all rotations and reflections of the whole cube and C denote the subgroup of M which contains only the rotations. C has 24 elements (any of the six faces can be put on top, after which any of the four adjacent faces can be put in front, uniquely determining the positions of the remaining faces). M has 48 elements (six choices for U, then four for F, then two for L). [Our use of G and C agrees with that in McKeeman's note of 8 Dec 1980, 17:03 PST. Hoey's note of 9 Dec 1980, 16:38 EST used the letter R rather than C for the latter group, a practice which we hereby retract.] Let G+M be the group of all transformations achievable by any sequence of face twists and/or whole cube moves, including reflections. Note that G is a subgroup of G+M and that the elements of G are precisely those elements of G+M which leave the positions of the face centers fixed (to forestall possible confusion, we remark, at certain risk of belaboring the obvious, that the phrases "face center positions" and "face center orientations" have different meanings). We say that two elements, s and t, of G+M are "M-conjugates" of each other if there exists some m in M such that t = m' s m. We assert the following results without proof because they are obvious. Fact 1: Any M-conjugate of an element of Q is an element of Q, and any M-conjugate of an element of G is an element of G. Fact 2: If two elements of G are M-conjugates, they are equally long. [Anyone who does not consider the preceding facts obvious is urged to direct further inquiries to one of us rather than bothering everyone on the mailing list. The same goes for anyone who believes that any other assertions made in this message are in error; this procedure will help to reduce either duplication of erratum notices or proliferation of false counterexamples.] Let W be a subgroup of M. Then an element s of G is said to be W-symmetric iff s w = w s (or, equivalently, w s w' = s) for every w in W. [This definition is equivalent to Hoey's definition (9 Dec 1980, 16:38 EST) as we will now show. By a "recoloring" of the cube, we intuitively mean an operation which "consistently" changes the colorings of all facelets of the cube. Note that the permutation performed by a recoloring depends not only on the chosen mapping of colors to colors, but also on the configuration the cube is in when we start recoloring. Thus, a particular mapping of colors to colors doesn't appear to correspond to any fixed element of G+M. This is not a particularly satisfying situation. We can rectify this situation by always doing the recolorings when the cube is in the SOLVED state, that is, by thinking of recoloring a configuration as pre-multiplication of the permutation that achieves that configuration (from SOLVED) by a recoloring of SOLVED. More succinctly, two elements, s and t, of G+M are equivalent up to recoloring iff there is some m in M such that t = m s. Thus, by Hoey's definition, an element s of G is W-symmetric iff for every w in W there is some m in M such that s w = m s. But s doesn't move the face centers. So the only way m can be chosen so that m s will leave the face-centers in the same places as s w is to pick m = w.] 3. Transitivity =============== For which choices of W can we guarantee that W-symmetric patterns are local maxima? To approach this question, we introduce the notion of Q-transitivity. Recall that Q is the set (not a group) of all quarter-twists. We define a subgroup W of M to be "Q-transitive" iff for each two elements p and q of Q there is some w in W such that q = w' p w. (Q+-transitivity and Q2-transitivity are defined analogously) We now come to our principal result: Theorem 1: Let W be any Q-transitive subgroup of M and let s be any W-symmetric element of G. Then any two neighbors of s are m-conjugates of each other. Proof: Let p and q be any two elements of Q. We must show that sq is an M-conjugate of sp. Since W is Q-transitive, produce some w in W such that q = w' p w. Thus, s q = s w' p w = w' (s p) w. Since W is a subgroup of M, w must be an element of M. So the definition of M-conjugacy is satisfied. Q.E.D. Corollary: Let W be any Q-transitive subgroup of M and let s be any W-symmetric element of G other than the identity. Then s is a local maximum. If an element s of G is both V-symmetric and W-symmetric, where V and W are subgroups of M, then it follows that s is V+W-symmetric, where V+W is the closure of the union of V and W (that is, V+W is the group of all elements of M which can be expressed as the product of a sequence of elements of the union of V and W). Thus we may unambiguously define the "symmetry group" of any element s of G as the largest subgroup W of M such that s is W-symmetric. The elements of this group will be precisely those elements of M which commute with s. To see that this set of elements forms a group, simply note that for any elements v and w of M that commute with s, 1. (v w) s = v (w s) = v (s w) = (v s) w = (s v) w = s (v w), and 2. v' s = v' s v v' = v' v s v' = s v'. By the corollary to Theorem 1, any element of G (except the identity) whose symmetry group is Q-transitive is a local maximum. In order to find local maxima, we will first find the Q-transitive subgroups of M. The search for Q-transitive subgroups is simplified by realizing that the number of elements of any Q-transitive subgroup W must be a multiple of twelve. To show this, it will be useful to introduce another way of looking at the group M, namely as a group of permutations on the set Q. We associate each element m of M with a 1-1 function from Q to Q defined by the rule (q) = m' q m for all q in Q. These functions form a group under the operation of functional composition, which we will write in the left-to-right manner so that (*)(q) is definitionally equivalent to ((q)). Call this group . The function <> which maps each element m of M to the corresponding element of is an isomorphism as may be seen by noting that for any two elements m and n of M and for any element q of Q, (*)(q) = ((q)) = n' (m' q m) n = (m n)' q (m n) = (q) The isomorphism <> maps each subgroup of W of M into a subgroup of , while is in turn a subgroup of the group of all permutations of Q. If W is Q-transitive, then is transitive on Q in the usual group-theoretic sense that for any two elements p and q of Q there is some element of such that (p) = q. This may be taken as motivation/"justification" for our use of the term "transitive" in the former context. It is a well-known result of group theory that every transitive group of permutations on a set X has a number of elements that is a multiple of the number of elements of X. This proves our claim that each Q-transitive subgroup of M has a multiple of twelve elements. [For those not familiar with the group-theoretic result mentioned above, the proof for this specific case goes like this. Let be a transitive subgroup of . We must show that has a multiple of twelve elements. Let q be any element of Q and let V be the subgroup of containing all elements of such that (q) = q. For any element of , the right coset V of V is the set {* | is in V} Since (*)(q) = ((q)) is equal to (q) iff (q) = q, V consists of precisely those elements of which map q to (q). All cosets must have the same size, so the number of elements of must be a multiple of the number of cosets, which is the number of distinct values of (q). Since is transitive on Q, the set of such values is all of Q, which has twelve elements.] We generated the 98 subgroups of M by computer, and found that only 9 of them had a multiple of 12 elements. We examine these subgroups below. In the preceding proof, we found it useful to think of elements of M as permutations on the set Q. In what follows, we will sometimes find it useful to think of elements of M as permutations of the set of face center positions. An element of M will be called "even" or "odd" according as it induces an even or odd permutation on the six face centers. Also, we refer to elements of M which are not rotations of the cube as "reflections". This applies even to permutations which are not simple geometric reflections but must be expressed as the composition of a reflection and a rotation. An example is the element of M which permutes face centers in the cycle (U,B,R,D,F,L). The largest subgroup of M is, of course, M itself (48 elements). M has three subgroups of size 24: the group C of rotations of the cube, the group of all even elements of M, which we call AM (for alternating M), and the group of elements which are in either both or neither of C and AM. We will call this third group H. Thus the group H contains the even rotations and the odd reflections. M has five subgroups of size 12. One of these is the group of all even rotations, which we call AC. The other four are of the kind called "T" by Hoey in his message of 9 Dec 1980, 16:38 EST (corrected by Bawden, same date, 23:57 EST). Let Z be any of the four long diagonals of the cube (e.g., UFL-DRB). Then T(Z) is the contains all elements of M which map the corner cubies at the ends of Z either to themselves or to each other. Of these nine groups, all except C and AC are Q-transitive. 4. A Catalog of Local Maxima ============================ In this section, we examine the seven Q-transitive subgroups of M, and describe the 72 corresponding symmetric positions. In general, given a geometric interpretation of a subgroup W of M, verifying that a position is W-symmetric is immediate, and no proof will be given. To prove that our catalog contains all W-symmetric positions is more difficult, and we defer this to a later message. There are four M-symmetric positions: SOLVED, the Pons Asinorum (reached by RRLL UUDD FFBB), SOLVED with all edges flipped (Bawden, 9 Dec 1980, 23:57 EST), and the Pons Asinorum with all edges flipped. The Pons Asinorum is interesting in that it is our only example of a PROVEN local maximum which has been PROVEN NOT to be a global maximum (it is known to have a length of at most 12, while the global maximum must be longer because |G| > 12^12). This was pointed out by Plummer (7 Dec 1980, 07:24 EST). The only AM-symmetric elements of G are those which are also M-symmetric. Since the symmetry group of a position is the largest subgroup W of M such that the position is W-symmetric, there is no position which has AM as its symmetry group. Plummer (10 Dec 1980, 23:27 EST) has already presented an example of an H-symmetric position which is not M-symmetric. The position is SOLVED with adjacent corners rotated in opposite directions. Another position, whose H-symmetry leads to our choice of nomenclature, is shown below. U U U D U D U U U L L L F B F R R R B F B R L R F F F L R L B B B L L L F B F R R R B F B D D D U D U D D D There are two such "six-H" positions; composing the two yields the Pons Asinorum. This gives four possibilities for edge cubie positions. The corners of an H-symmetric position may be in any of three orientations, all home, Plummer's configuration, or Plummer's configuration with the twists reversed. In any position, the edges may all be flipped or not. Composing the choices yields twenty-four H-symmetric positions, twenty of which are not M-symmetric. There are four groups of the form T(Z). To make our presentation more specific, we will fix Z as the (UFL-DRB) diagonal. We define the "girdle" of the cube as the set containing all the corner cubies other than UFL and DRB and all edge cubies which are NOT adjacent to either UFL or DRB. Thus, Girdle = {ULB, LB, DBL, DL, DLF, DF, DFR, RF, URF, UR, UBR, UB} A position which is T-symmetric but not M-symmetric (T has no proper supergroups in M except for M itself) may be obtained by flipping all edges on the girdle, as shown. U B U U U R U U U L L L F F F R U R B U B B L L F F R F R R B B L L D L F D F R R R B B B D F D L D D D D D Also, each edge on the girdle may be swapped with the diametrically opposite edge, provided that the corners on the girdle are swapped with their opposites as well. R D D U U D U U B D L L F F D L L F L F F R L L F F B L R R B B F R R B R B B U R R B B U U U L U D D F D D These positions may be composed with each other and with the four M-symmetric positions to yield sixteen T-symmetric positions, twelve of which are not M-symmetric. Counting the positions symmetric with respect to the four different T groups yields 48 positions whose symmetry groups are T groups. This completes the catalog of positions with Q-transitive symmetry groups. Summarizing the numbers of positions of each kind, we have M-symmetric 4 AC-symmetric but not M-symmetric 4-4 = 0 H-symmetric but not M-symmetric 24-4 = 20 T-symmetric but not M-symmetric 4*(16-4) = 48 for a total of 72 positions, one of which is the identity and 71 of which are local maxima. 5. Generalizations =================== The group of whole cube rotations, C, is Q+-transitive, but not Q-transitive, because U = c U' c' has no solution for c in C. This means that McKeeman's suggestion (8 Dec 1980, 17:03 PST) that C-symmetry was a sufficient condition for being a local maximum is not an immediate corollary of Theorem 1. However, it happens that all C-symmetric positions are also M-symmetric and they are therefore local maxima with the exception of the identity. Thus McKeeman's claim turns out to be true "by accident". However, the case for the Supergroup is a different story. Analysis of the Supergroup, in which the orientations of the face centers are significant, is trivial given the analysis for G. The only operations on the face centers which yield Q-transitive symmetry groups are to leave them all alone or two rotate them all by 180 degrees. Thus there are a total of 72 * 2 = 144 elements of the Supergroup which have Q-transitive symmetry groups. One of these is the identity and the other 143 are local maxima. Considering face orientations as significant also allows us to construct a position which is C-symmetric but not M-symmetric, namely Big Ben, the position reached from SOLVED by turning all the face centers 90 degrees clockwise. Big Ben is a good candidate for a counterexample (in the Supergroup) to McKeeman's (8 Dec 1980, 17:03 PST) suggestion that C-symmetric positions are local maxima. Possibly Big Ben is a local maximum, but it sure isn't obvious to us that, say, U and U' will lead to positions equally near to SOLVED). Those who are interested in counting half-twists as single moves may be pleased to hear that all 71 (143 in the Supergroup) positions described above are also local maxima in the half-twist metric. To see this, first note that every Q-transitive subgroup of M is also Q2-transitive. This means that for any position p among those 71 (or 143), all positions reached by quarter-twists from p are M-conjugate (and thus equally far from SOLVED) and all positions reached by half-twists are also M-conjugate. The positions in one of these two sets must all be one step closer to SOLVED (in this metric) than p. The positions in the other set cannot be further from SOLVED than p since they are only one move away from positions in the first set. Note that this proof depends on BOTH Q-transitivity and Q2-transitivity. We do NOT make the claim that any position whose symmetry group is Q2-transitive must be a local maximum in the half-twist metric (in fact, we suspect that the six-spot pattern mentioned below is a counterexample). 6. On Conjectures ================== The point of this section is not to make conjectures, but to examine conjectures which have recently appeared in the light of our results. As an example, we will first discuss a conjecture that has not been made, but which would likely have been baldly stated as fact had anyone thought to do so. "Of course, the inverse of a local maximum is also a local maximum." Easily said, but is it true? All local maxima we know about have Q-transitive symmetry groups, and the symmetry groups of an element and its inverse are equal. But suppose the local maximum were not symmetric. Consider the position reached from SOLVED by performing the twists (U F F). From this position, either F or F' will move the cube closer to SOLVED. From its inverse, (F' F' U'), only U will move closer to SOLVED. Is it not conceivable that from some position, any of the twelve twists would move closer to SOLVED, yet only eleven or fewer would move its inverse closer? Such a position would be a counterexample to the first statement of this paragraph. Of course, the example we provide is not a local maximum, and indeed there may exist no local maxima except the (symmetric) ones we have found. But there is also no reason to believe they can't exist, and there is no reason to believe that their inverses are local maxima. Of course, the inverse of a global maximum is also a global maximum. The symmetry group of a Plummer cross has six elements and is the intersection of H with T(Z) for an appropriate choice of diagonal Z. This group is not Q-transitive, but is Q2-transitive. Consequently if the algorithm presented by Saxe in his message of 3 Dec 1980, 00:50 EST, is optimal, then the Plummer cross is a local maximum. The reason for this is that Saxe's algorithm ends with a half-twist. This means that, if the algorithm is optimal, then, by virtue of the Q2-transitivity of the symmetry group, performing any half-twist on a Plummer cross brings you two qtw closer to SOLVED. This implies that performing any quarter-twist on a Plummer cross would bring you one qtw closer to SOLVED, since the quarter-twist could be continued into a half-twist for a total gain of two qtw. This observation (Saxe's algorithm optimal => Plummer cross a local maximum) was first made by David Plummer (5 Dec 1980, 20:29 EST), who offered a slightly different, but correct, proof. We emphasize that this is all based on the purely speculative conjecture that Saxe's algorithm is optimal. The Plummer cross is NOT known to be a local maximum merely by virtue of its symmetry, Greenberg's (bogus) statement of 7 Dec 1980, 12:18 EST ("Yet, we know, intuitively, that CP is 'highly symmetric', and it is a local maximum.") notwithstanding. To drive this point home, consider the six-spot configuration (Pavelle, 16 Jul 1980, 20:51 EDT) produced by moving (L R' F B' U' D L R'). This position has exactly the same symmetry group as the Plummer cross, but is not a local maximum. Any of the six quarter-twists L', R, F', B, U, or D' will bring you closer to SOLVED (obvious), any of the other six quarter-twists will take you further away (based on exhaustive search by computer). An even more symmetric position is the twelve-L's [not to be confused with Singmaster's less symmetric but visually similar 6-2L, obtained from SOLVED by (F B U D R' L' F B)]: L R R L U R L L R B F F U U U F B B U U U B L F U F D F R B U B D B B F D D D F F B D D D L R R L D R L L R The symmetry group of this position is AC, the group of even rotations. AC is Q+-symmetric, so all clockwise twists have the same effect, and all counterclockwise twists have the same effect. If the two sets of neighbors should happen to have the same lengths, then this position would be a local maximum. Need we say that there is no reason to believe this to be the case? Michael Aramini (7 Dec 1980, 01:08 EST) mentions the possibility that two maxima might be one half-twist apart in the half-twist metric. This was claimed impossible by Plummer (7 Dec 1980, 07:24 EST). We do not follow the reasoning, and we conjecture that he misread "half" as quarter and then mistyped "quarter" as half. We also do not see anything to prevent two (local or global) maxima in the half-twist metric from being a quarter-twist apart or two maxima in the quarter-twist metric from being a half-twist apart. Parity considerations do not stand in the way of such occurrences and, while none of the known (symmetric) local maxima are so close to each other, we have no proof that either local or global maxima must be symmetric. We have no proof that such closely neighboring maxima (or any non-symmetric maxima at all) *do* exist, either. While we know 71 local maxima, we know only 25 distinct ones up to M-conjugacy (3 having symmetry group H, 12 having symmetry group T, and 10 [yes, 10] having symmetry group H). McKeeman (6 Dec 1980, 16:42 PST) has correctly (provided we substitute our corrected definition of symmetry) noted that, if we could show that maxima had to be symmetric, then the maximum of the best known solutions to these configurations would bound the length of the global maximum. Unfortunately, we have no proof of this conjecture, nor any strong reason to think it true. Dan Hoey (Hoey @ CMU-10A) Jim Saxe (Saxe @ CMU-10A)  Date: 15 DEC 1980 1851-EST From: DCP at MIT-MC (David C. Plummer) Subject: Administrata and an Algorithm To: CUBE-LOVERS at MIT-MC CC: ELLEN at MIT-MC, DUFFEY at MIT-MC First the Administrata. CUBE-LOVERS came close to a crisis this weekend. There were thoughts of having it digested, but DUFFEY came through and made some very valuable suggestions. What happened is that the Hoey-Saxe message was long enough to confuse the mailer, and it ended up sending it twice. It took at least an hour and a half to send, so the mailer response was terrible. Things have been reorganized to help make things more efficient, and we really thank DUFFEY for doing this. In the future, please limit your messages to one to two thousand characters. If you must send long messages, please break it up into sections and send a piece every hour or so. Please keep this mailing list winning. Thanks. Now for the algorithm. Hoey and Saxe mentioned an H pattern. By a simple method of doing it, it can be done as follows: FF (LLRR) BB (LLRR) RR (UUDD) LL (UUDD) DD (FFBB) UU (FFBB) and after removing the NOPs ==> FF (LLRR) BB (LL) (UUDD) LL (UU) (FFBB) UU (FFBB) which is another 28 mover. But I have found another way to do IT: (UD LLRR FFBB UD) (FFBB LR FFBB L'R') ==> 24 QTW Hoey and Saxe said that the Pons Asinorum is the only local maximum that is PROVEN not to be a global maximum. It still is, but if somebody can prove that Global Max must be larger than 24 (it is currently at 22), then this would be another example. The other possibility is to find a faster algorithm to this pattern. I have an intuitive sense that the global maximum is an even distance away. I cannot prove it. Can anybody?  Date: 16 December 1980 1841-EST From: James.Saxe at CMU-10A (C410JS30) To: Cube-Lovers at MIT-MC Subject: 16 qtw algs for CC and H patterns CC: James.Saxe at CMU-10A Message-Id: <16Dec80 184127 JS30@CMU-10A> In his note of 4 Nov 1980, 00:23 EST, David Plummer gives a 20 qtw algorithm for the Christman cross based on the following tool for producing a 4-cross pattern: 4+ = FB UUDD F'B' R'L' UUDD RL UUDD This can be reduced to 16 moves as follows: 4+ = FB UD LLRR UD FB UUDD Consequently, Plummer's 16 qtw Christman cross algorithm, conceptually B' 4+ B, can be reduced to B' [FB UD LLRR UD FB UUDD] B = F UD LLRR UD FB UUDD B (16 qtw). [Note: There is another 4-cross pattern besides the above, namely LLRR F LLRR FB LLRR B' LLRR F'B'.] The H pattern which Dan Hoey and I described in our earlier message (14 Dec 1980, 19:16 EST, Sec. 4) can be achieved in 16 qtw as follows: FF LL DD FF BB DD RR FF This makes it the second proven example of a local maximum which is not a global maximum. Of course this applies equally to the second H pattern which is Pons Asinorum away from the above. I count these two as only one example since they are M-conjugates. --Jim Saxe  Date: 30 DEC 1980 0109-EST From: DCP at MIT-MC (David C. Plummer) Subject: Hackery (92 line message) (first of three) To: CUBE-LOVERS at MIT-MC Greetings...I'm back from vacation. I took a copy the old mail home and read it. It was an interesting experience. Existence proofs: Saxe and Hoey described (14 December 1980, 19:16 EST) several local maximums that were previously not described. I have algorithms for a couple that are 28 moves long, showing that THESE PARTICULAR local maximums are no further than 28 away from SOLVED. ========== The edges flipped along the girdle (hereafter refered to as GIRDLE EDGES FLIPPED [until somebody else thinks of a better name]) can be done as follows: (F D'U L D'U B D'U R D'U ) (U'L'F) (L'R F' L'R U' L'R B' L'R D') (F'L U) [This is a Sprat Wrench, get-ready, another Sprat Wrench, un-get-ready.] At first glance this is 30 moves, but notice that the U and U' near the end of the first line cancel, making it 28. ========== The edges not along the girdle flipped (hereafter refered to as OFF GIRDLE EDGES FLIPPED) (NOTE: This is GIRDLE EDGES FLIPPED compounded with ALL EDGES FLIPPED), can be done as follows: (L B'F U B'F R B'F D B'F ) (F F U) (R'L U' R'L F' R'L D' R'L B') (U'F F) [Again, Sprat-mung-Sprat-unmung] And again, 30 at first glance, but this time the FFF near the end of the first line becomes F', so 30-2 is again 28. ========== ========== I noticed something peculiar about the second kind of girdle configuration the mentioned. Hoey and Saxe describe it as "each edge on the girdle may be swapped with the diametrically opposite edge, provided that the corners on the girdle are swapped with their opposites as well" and they give a picture. It is indeed reachable, but the most interesting thing (in my opinion) is that it is an odd distance away!! (Of course so are the related configurations obtained by performing on it: PONS, ALL EDGES FLIPPED, and PONS WITH ALL EDGES FLIPPED.) ODD!! Most of (if not all) the previously described "nifty patterns" were even. And on top of that, this odd permutation is a local max. Most of the tools people seem to use are even. Several of them fall along the lines of MUNG/DO SOMETHING/UNMUNG, and DO SOMETHING is often even, and two MUNGS is even. Now the question is: HOW FAR AWAY ARE THESE, AND HOW DO YOU (THE HUMAN) TRY TO FIND THE ALGORITHMS TO DO THEM? My suggestion: Do something, Mung, Do something (maybe different). I also suggest that Do somethingbe of length 12, and that mung be 3 or 5. I would really apprecitate it if it were less than 28 -- I happen to like 28 as the maximal length. ========== The local max which I described (Plummer 10 December 1980, 08:34 EST) which is all corners rotated such that adjacent corners are rotated in opposite directions (shall we call this ALL CORNERS ROTATED? I know it isn't explicit, but it is descriptive enough for our purposes) can be done in 40 by a Christman Cross (16, thanks to Saxe 10 December 1980, 18:41 EST), two half twists (4), another Christman Cross (16), and undoing the two half twists (4). I have been trying for the better part of a week to get this down to 28 (my favorite number), but have not yet succeeded. What I want is a 14 move algorithm to exchange all corners with their diametrically opposite corner in such a way that the top forms a cross of the top as the cross and the bottom at the corners. Two of these with a whole cube manipulation in between will do the trick. Alternately, if somebody could come up with a 12 mover to move FDL to FUR (and do this so that it sould look this way if viewed from F,L,R or B), you could do U U' and the opposite corners would be swapped as desired. I have an almost algorithm, but it falls short in that the four edges on the center horizontal slice are swapped with their diametric opposites. The algorithm is R'L' F'B' R'L' FB RL FB If anybody can find the desired algorithms, please publish. ========== Reading cube mail, I saw several things about "this Sprat Wrench is best executed by a right handed person." The way I do the Wrench does not descriminate, and I think it is worth it to describe it: (0 QTW) Holding the right face in the right hand, (0 QTW) holding the left face in the left hand, (2 QTW) rotate the center verticle slice toward you, (1 QTW) rotate the NEW front face clockwise (either hand will do) Do this a total of four times, giving 4*3=12 QTW. Try it, and also try turning the NEW front face counterclockwise. ========== That's all I can think of on this subject. Coming soon: Design of the higher order cubes Thoughts on manipulating the higher order cubes.  Date: 30 DEC 1980 0144-EST From: DCP at MIT-MC (David C. Plummer) Subject: The higher order cubes (just the 4x4x4 for now) [93 lines] To: CUBE-LOVERS at MIT-MC And you thought the 3x3x3 was a complicated beastie... I have plans for the 4x4x4 which I think can work. A first order approximation is to take the 3x3x3 and split the edges in two. This doesn't take care of the centers or axis, but those are perhaps the most complicated anyway, and will get considerable thought. WARNING: If you really want to see this, get out the graph paper and correct the aspect ratio that the characters here will have. The way I have labeled the cubies is as follows: Corners are labelled A (there are 8 of these) Edges are labeled both B and D (this defines the orientation) (there are 24 of these) Centers are labeled C (there are 24 of these) So a face would look like: ABDA DCCB BCCD ADBA Take a slice down the center of one of the planes and open it up. It should look something like: .....&&&&&&&&++++++++ .....&&&&&&&&++++++++ where & and @ are pieces of ..xxxxxx&&&++++++++++ the C type of cubie ..xxxxxx&&&++++++++++ + is a B/D type ....xx&&&&&++++++++++ x is the central axis ....xx&&&&&++++++++++ ....xx&&&&&++++++++++ ....xx&&&&&++++++++++ ....xx&&&&&++++++++@@ ....xx&&&&&++++++++@@ ....xx&&&&/@@@@@@@@@@ \...xx&&&/@@@@@@@@@@@ .\..xx&&/@@@@@@@@@@@@ ..\.xx&/@@@@@@@@@xx@@ ...\xx/@@@@@@@@@@xx@@ xxxxxxxxxxxxxxxxxxx@@ xxxxxxxxxxxxxxxxxxx.. .../xx\..........xx.. ../.xx.\.........xx.. ./..xx..\............ Gross, isn't it? There are a few things going on here that are hard to show. That central cross must be able to rotate, so the innermost parts of C and B/D are carved in somewhat. There is another hairy constraint: the central axis MUST BE RIGIDLY CONNECTED TO ONE AND ONLY ONE OF THE C TYPE CUBIES. The reason is hard to describe. Hint: suppose you rotate a half cube portion. It is possible that when the rotation is finished, the central axis is misaligned. Connecting it to one face cubie forces it to win. This may also make the central cross somewhat more fragile. Forgetting about the central axis and the corner cubies (they shouldn't be too able to work into the picture) we have the following diagrams for the B/D and C type cubies. The numbers indicate elevations: B/D C 44444444 4444 44444444 ACTUALLY THEY 4444 4443333333 ARE CURVED, 4443333333 4443333333 BUT CHARS 4443333333. 4433333333 HAVE POOR 4433333333.2 4433333333 RESOLUTION 4433333333.2. 4433333333 4433333333.2.1 4433333333 4433333333.2.1. I seriously think these will work. I hope to find somebody in a material science type of lab that can make plastic molds so I can actually try and build one of these. I hope to use a soft plastic that is machinable, carvable, sandpaperable, etc, and when I have a good one, make several pieces out of harder plastic and see what happens. Perhaps I'll have something by the end of January. I think that the 5x5x5 cube (though the tolerances might be tighter) may actually be easier to construct. It may also be a more interesting cube to work with. Next: Notes on transforms on the 4x4x4 and 5x5x5 cubes. PS: A mind blower: a DODECAHEDRON frob (can't call it a cube). I thought of this one coming back on the bus. I haven't put anything down on paper, but my minds eye tells me it has a chance. Comments welcome.  Date: 30 DEC 1980 0152-EST From: DCP at MIT-MC (David C. Plummer) Subject: Notes on transforms on the 4x4x4 and 5x5x5 cubes. (65 lines) To: CUBE-LOVERS at MIT-MC First we have to define what a twist is. I propose that a twist is a twisting of face or faces about an axis such that there is only one plane on which sliding friction happens. This means that slice turns are not single turns, but rather multiple turns. This is consistent with the 3x3x3 definition, and it is generalizable to nxnxn. Also, I think it is wisest to consider quarter twists as the only single twist "move" (don't count half twists as one!!) One thing to note: Even order cubes should have a STANDARD coloring. This is nice to have since there is now visible axis to align the corners on. I know it isn't necessary, but if I own a cube and you own a cube, and they are colored differently, and we swap for a day, both of us will probably have a hard time trying to get used to a different color arrangement than what each is used to. May I suggest Front Right Up Back Left Down RED WHITE BLUE ORANGE YELLOW GREEN The general PONS can be described as follows (for cubes, not necessarily dodecahedra): Pick an axis. Make 180 twists along all twistable planes. Pick another axis. Do the same. Do the same on the last axis. This will produce a checkerboard pattern on all faces using complementary (from the opposite side of the cube) colors. On the 4x4x4 (and in general on even order cubes), to corner cubies do not move (but then again it is hard to tell without a fixed reference). I have done more thinking about the 5x5x5 than the 4x4x4 since the 5x5x5 offers several immediate advantages. First of all, from solved we can do things like: do a transform as we would on a 3x3x3 and consider the 3x3 set of cubies in the center of the faces as the center of our favorite 3x3x3 Hungarian. Another way to view this is to do normal Hungarian rotations using only one level deep of cubies. Then run the algorithm backwards doing twists using two levels deep (considering theface center as a center and 2x2 at the corners as corners, and 1x2 around the edges as edges. (Bad explanation, but it is 1:30 in the morning). I believe doing the traditional SIX-DOTS pattern forward then backward using this method will produce something that looks like: +++++ +++++ +@@@+ +@@@+ +@+@+ +@x@+ +@@@+ +@@@+ +++++ +++++ The one on the right is what happens if you do it again in the same direction. I think the Plummer's Cross will look like: +@+@+ @@+@@ +++++ @@+@@ +@+@+ And if I am not mistaken, the approriate EXTENDED-SIX-DOTS mentioned above performed on this will produce a 3-cycle checkerboard. And the PONS on top of that will produce a 6-cycle checkerboard. Of course, I could be wrong, but we wont know until (a) somebody carfully works it out on paper (b) somebody writes a computer program to simulate the crazy thing, or (c) somebody actually builds one. That's it for tonight folks, aren't you glad!!  Date: 29 Dec 1980 23:54 PST From: McKeeman at PARC-MAXC Subject: Re: The higher order cubes (just the 4x4x4 for now) [93 lines] In-reply-to: DCP's message of 30 DEC 1980 0144-EST To: DCP at MIT-MC (David C. Plummer) cc: CUBE-LOVERS at MIT-MC David, Interesting thoughts. It seems to me that the icosahedron is a more attractive physical target than the dodecahedron. It has 12 shear planes. A move would be a 72o rotation of a five-triangle subsection. My intuition is that it is buildable more or less along the line of the Rubik cube, except that the fixed axes point at vertices instead of center faces. The dual of the 2x2x2 cube seems to be an octahedron with shear planes along its edges. More generally slice a sphere a buncha times. The cuts are shear planes. Don't let it fall apart (there is the trick!). Now paint the surface pieces. Now twist to mix. The actual shape does not seem to matter much. It is the interaction of the shear planes that makes the puzzle. Happy sphereing, Bill  Date: 31 DEC 1980 0330-EST From: ACW at MIT-MC (Allan C. Wechsler) Subject: Groups and Cayley Graphs To: CUBE-LOVERS at MIT-MC If there is any popular response I will write a short introduction to Group Theory for Cubists. = - = - = - = - = - = - = - = - = - = - = - = - = Problem: the cube is known to have "small mountains", states that are locally maximally distant from the home state but not globally so. The Pons Asinorum is an example: it has been proved (a refreshing relief from unmitigated conjecture) to be 12 qtw from home and all its neighbors are closer. The cube's Cayley graph in its six generators is vertex- transitive (all the states look the same) like all Cayley Graphs. In addition, because all the generators are conjugate in the big group (quarter-twists plus whole- cube motions) the Cayley graph is edge-transitive (all transitions between adjacent states look the same). Can anyone find a small example of an edge-transitive graph that has local maxima that are not global? ---Wechsler  Date: 31 DEC 1980 1115-EST From: DCP at MIT-MC (David C. Plummer) Subject: the higher order SPHERE slices To: McKeeman at PARC-MAXC CC: CUBE-LOVERS at MIT-MC Sigh, my goemetry needs to be zapped back into working order. I really did mean icosahedron instead of dodecahedron (they both have 12 faces). I was originally thinking of the fixed axes pointing at the center faces, but pointing at the vertices is an interesting idea. I shall have to think about it a little. About the general case: "slice a sphere a buncha times." Holding it together is REALLY the tricky part. Consider the 7x7x7 CUBE. Do a 45 degree clockwise rotation on the top face (half a quarter twist). The problem is that the ENTIRE FRU corner cubie COMPLETELY hangs over the front face. This means that the 3-D jigsaw-puzzle idea that keeps the 3x3x3 cube together will not work on order 7 and higher order CUBES.  Date: 31 Dec 1980 0729-EST From: ZILCH at MIT-DMS (Chris C. Worrell ) To: CUBE-LOVERS at MIT-MC Subject: relatives of the plummer cross Message-id: <[MIT-DMS].177333> Two relatives of the plummer cross which people may find interesting are given here: The first is called a baseball. lL U L L U U L L L F F F U U U B R B D B D L L F U F F R R B D B B F L F U F U B B B D D D R D R D D R R R R I do this one in 50 qtw though I know how to shorten it to 42. The second is called a cube in a cube. L L L U U L U U L F L L F F U B B B D D D F L L F F U B R R B B D F F F U U U B R R B B D R R R R D D R D D I do this one in 70 qtw, though I could reduce it to 62. These configurations both have two minor variants which leave the essential nature of the configuration the same. these other patterns are obtained by twisting the FUL AND BDR corners. Both of these patterns were devised by people at Caltech. Chris Worrell (ZILCH @MIT-AI)  Date: 31 DEC 1980 1210-EST From: DCP at MIT-MC (David C. Plummer) Subject: the 5x5x5 [133 lines] To: CUBE-LOVERS at MIT-MC OK, folks, I'm considering going further than 4x4x4 and entering the realm of the 5x5x5. Cubies: C := Corner X := aXis (center) E := Edge (outside center) L := Left (external edge) R := Right (external edge) D := Diagonal (internal [to the face] corner) A := Adjacent (to the center, thanks to WER) (internal [to the face] edge) A 3-D view would look like this z=-5 +---+---+---+---+---+ / / / / / /| / C / L / E / R / C / | +---+---+---+---+---+ | / / / / / /|C + / R / D / A / D / L / | /| +---+---+---+---+---+ |/ | z=0 / / / / / /|R + | / E / A / X / A / E / | /|L + +---+---+---+---+---+ |/ | /| / / / / / /|E + |/ | / L / D / A / D / R / | /|D + | +---+---+---+---+---+ |/ | /|E + / / / / / /|L + |/ | /| / C / R / E / D / C / | /|A + |/ | y,z=5 +---+---+---+---+---+ |/ | /|A + | | | | | | |C + |/ | /|R + | C | L | E | R | C | /|D + |/ | /| | | | | | |/ | /|X + |/ | y=3 +---+---+---+---+---+ |/ | /|D + | | | | | | |R + |/ | /|C + | R | D | A | D | L | /|A + |/ | / | | | | | |/ | /|A + |/ y=1 +---+---+---+---+---+ |/ | /|L + | | | | | |E + |/ | / y=0 | E | A | X | A | E | /|D + |/ | | | | | |/ | /|E + y=-1 +---+---+---+---+---+ |/ | / | | | | | |L + |/ | L | D | A | D | R | /|R + | | | | | |/ | / y=-3 +---+---+---+---+---+ |/ | | | | | |C + | C | R | E | L | C | / | | | | | |/ y=-5 +---+---+---+---+---+ x=-5 -3 -1 1 3 5 LOVE THAT ASPECT RATIO !!!! All in all there are 6 aXis faces 8 Corners 12 Edges 24 Left/Right type edges 24 Diagonals 24 Adjacents -- 98 = 5^3 - 3^3 = 125-27 visible cubies Computation (inaccurate, but within a couple orders of magnitude) of the number of reachable positions: Axes: lets not hack the extended problem yet -> 1 Corners:8 of them anywhere -> 8! each can take 3 orientations -> 3^8 parity of the corner -> 1/3 Edges: 12 of them anywhere -> 12! each can take 2 orientations -> 2^12 position/orientation restriction -> 1/4 L/R: 24 of them anywhere -> 24! orientation defined (they cannot flip) -> 1 parity (cannot swap only two) -> 1/2 (I think) Adjac: 24 of them anywhere: -> 24! one edge always touches a face center -> 1 parity -> 1/2 (at least) Diags: 24 of them anywhere -> 24! one corner always touches a face center -> 1 parity -> 1/2 (at least) It may not be accurate, but this computation gives 1.291318 * 10^90 A slice through the center (z=0) probably looks something like y=5\ / ..XXXXXXXXXX++++++++++EEEEEEEEEE ..XXXXXXXXXX++++++++++EEEEEEEEEE .....XXXX++++++++EEEEEEEEEEEEEEE .....XXXX++++++++EEEEEEEEEEEEEEE X is an axis cubie y=4\ .....XXXX++++++++EEEEEEEEEEEEEEE E is an edge cubie / .....XXXX++++++++EEEEEEEEEEEEEEE + is one adjacent cubie .....XXXX++++++++EEEEEEEEEEEEEEE ~ is another adjacent .....XXXX++++++++EEEEEEEEEEEEEEE .....XXXX++++++++EEEEEEEEEEEEEEE y=3\ .....XXXX++++++++EEEEEEEEEEEEEEE / .....XXXX++++++++EEEEEEEEEEEEE~~ .....XXXX++++++++EEEEEEEEEEEEE~~ .....XXXX++++++++EEEEEEEEEEEEE~~ .....XXXX++++++++EEEEEEEEEEEEE~~ y=2\ .....XXXX++++++++EEEEEEEEEEEEE~~ / .....XXXX+++++++/~~~~~~~~~~~~~~~ .....XXXX++++++/~~~~~~~~~~~~~~~~ .....XXXX+++++/~~~~~~~~~~~~~~~~~ \....XXXX++++/~~~~~~~~~~~~~~~~~~ y=1\ .\...XXXX+++/~~~~~~~~~~~~~~~~~~~ / ..\..XXXX++/~~~~~~~~~~~~~~~~~~XX ...\.XXXX+/~~~~~~~~~~~~~~~~~~~XX ....\XXXX/~~~~~~~~~~~~~~~~~~~~XX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX y=0\ XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX / XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX ..../XXXX\....................XX .../.XXXX.\...................XX y=-1\ ../..XXXX..\..................XX / /\ /\ /\ /\ /\ x=-1 0 1 3 5 This time the central axis is rigid in the sense that it does form a cross, but each of the six spokes can rotate as in the 3x3x3 cube. The curvature and tolerances of some of the pieces gets a little hairy, but I'm working with graph paper and looking at the other slices through the cube. Wish me luck -- I have thoughts of construction.  Date: 31 December 1980 1511-EST (Wednesday) From: Guy.Steele at CMU-10A To: DCP at MIT-MC (David C. Plummer) Subject: Icosahedron CC: cube-lovers at MIT-MC In-Reply-To: DCP@MIT-MC's message of 31 Dec 80 11:15-EST Message-Id: <31Dec80 151120 GS70@CMU-10A> The icosahedron has twenty faces, not twelve. It and the dodecahedron are duals: each has the same number of vertices as the other has faces. If you join the centers of the faces of one with lines, you get the other. They have the same number of edges.  Date: 31 DEC 1980 1230-PST From: WOODS at PARC-MAXC Subject: Re: relatives of the plummer cross To: ZILCH at MIT-DMS, CUBE-LOVERS at MIT-MC In response to the message sent 31 Dec 1980 0729-EST from ZILCH@MIT-DMS Your "baseball" is listed in Singmaster's booklet as "the Worm" (though I must admit I like your name for it), with a 28-qtw solution (23 if you count half-twists=1). I prefer the pattern named the "Snake": DUD DUD DUD BBB RFR FFF LBL BLL FFR FRR BBL BLB RRR FRF LLL UUU DDD UUU which is known to be soluble in 20 qtw (16 if htw=1). Meanwhile, your cube-in-a-cube has a 24-qtw (20-htw/qtw) solution in Singmaster, though I generally find it easy enough to make in 34 qtw using the commutator operation [spoiler warning!] nicknamed "rFUfuR": rFRfUfuFuRUr. -- Don. -------  Date: 31 Dec 1980 1545-PST From: Dave Dyer Subject: bigger&better cubes To: cube-lovers at MIT-MC Clearly, we must not be deterred by mere mechanical limitations! I'm sure a color bit-mapped raster could do a dandy job of displaying cube-like objects in any size and geometry you can imagine. If you must have a physical cube, how about a box with LCD's on all faces (in six colors?), pressure sensors to detect what ytou want to twist, and a uP inside to do all the work. -------  Date: 31 Dec 1980 1634-PST From: Dave Dyer Subject: Singmasters book To: cube-lovers at MIT-MC Does anyone know of a domestic source for it? -------  Date: 31 Dec 1980 1651-PST From: MERRITT at USC-ISIB Subject: Bigger & better cubes To: cube-lovers at MIT-MC In light of all the talk of cubes greater than 3 x 3 x 3, such as 4 x 4 x 4, or 5 x 5 x 5, perhaps you would like to comtemplate a cube that is 3 x 3 x 3 x 3, or 4 x 4 x 4 x 4. The idea of adding dimensions is really reasonable, since it needn't be mechanically possible. This Rubics hypercube could probably be represented by a video display in some form. This is at least a matter for further contemplation. -IHM -------  Date: 31 DEC 1980 1740-PST From: WOODS at PARC-MAXC Subject: Re: Bigger & better cubes To: MERRITT at USC-ISIB, cube-lovers at MIT-MC In response to the message sent 31 Dec 1980 1651-PST from MERRITT@USC-ISIB And then of course there's the megacube, formed by taking a standard 3x3x3 cube and replacing each cubie with a 3x3x3 Rubik's cube. The idea would be that each megaface could be twisted as usual, but the megafacies (the faces of the smaller 3x3x3 cubes) could be twisted only if they were visible. (Otherwise all you really have is a collection of independent 3x3x3 cubes.) The orientation of the colors on all the microcubes is the same -- that is, the beast starts with all 81 microfacies on a given side being the same color. -- Don. -------  Date: 31 December 1980 22:35-EST From: Ed Schwalenberg Subject: bigger&better cubes To: DDYER at USC-ISIB cc: cube-lovers at MIT-MC Obviously the age of mechanical polyhedra is long past. I propose that the center cubies (polyhedries?) of the electronic marvels be equipped with fixed arrows so that those who are hacking the higher-order problem can be happy. (I really like this idea because it closely resembles one of my favorite ideas: a keyboard which has small character displays in each keytop in lieu of engraving; when you hit SHIFT the legends change from qwertyiop to QWERTYUIOP and when you hit CONTROL+META they change to ETAIONSHRDLU, etc.) The all-electronic cube has many other potential features: instant resettability, a stack of saved states, subroutines.... Given extensible, customizible, self-documenting editors, I don't see why we should settle for polyhedra that are any less featureful. Speaking of higher-order polyhedra, I hereby nominate the tetrahedron as being appropriate to my own level of expertise.  Date: 1 JAN 1981 0221-EST From: ACW at MIT-MC (Allan C. Wechsler) Subject: How much intellect does it take to solve the cube? To: CUBE-LOVERS at MIT-MC Well, happy new year. I solved it while not exactly sober. ---Wechsler  Date: 1 JAN 1981 1315-EST From: DCP at MIT-MC (David C. Plummer) Subject: several subjects To: CUBE-LOVERS at MIT-MC One last try!! What I meant was the 12 sided frob built out of pentagons. And after refering to better and better dictionaries I discovered this thing is called a pentagonal dodecahedron, and I meant the faces to be the points of rotation. Perhaps McKeeman thought I meant the rhombic dodecahedron, and subsequent messages got me confused and I jumped the gun without thinking very heavily. Woods: Could you please send the manipulations for "baseball," "snake," and "cube-in-cube" for the benifit of those who do not have Singmaster. Please use prime notation (R' instead of (lower case) r) for counterclockwise twists since that seems to be the notation currently in use in this list. In general, my opinion is that it would be nice if people would send along the short algorithms that are known. ZILCH's 50 and 70 qtw algotithms are a little too long, but anything under 36 should probably be sent. I know it may be a spoiler, but (1) there seem to be several configurations mentioned and perhaps some people don't have time to find nice fast ways to get there, (2) it reduces needless duplication of effort, (3) parts of the algorithm (or the algorithm itself) might serve as a subroutine for other algorithms under development. On the concept of the higher order "cubes:" N dimensions has a reasonable geometric interpretation (maybe it doesn't have to have this condition?) built out of some number of "cubies" of dimension N Each "cubie" is in turn a "cube," perhaps of a different order than the larger cube (eg, a 3x3x3 cube whose cubies are 5x5x5) Each "cubie" of the "cubie" is a "cube," ad infinitum as desired In addition to all this, each faclet is a "cube" of dimension N-1, ad infinitum (at least until the dimensions run out!!) The thing I am doing is trying to PHYSICALLY construct a higher order (flavor: dimension 3, cubical, order 5, cubies are "atomic" (ie, not cubes in themselves), faclets are atomic). Personally, I think half the fun is being able to hold one of the beasties and mung it by twisting. ACW: I think it would be instructive to have an short intro to Group Theory for Cubist. This would benefit newcomers to the mailing list, and people who hack the cube and want to know some of the theory behind the cube. (5-10K characters if you can keep it down to that. If not, send it when machines are generally lightly loaded.) I vote: plase do.  Date: 3 JAN 1981 0248-EST From: ZILCH at MIT-MC (Chris C. Worrell ) Subject: How to play with the corners of your cube (long message) To: CUBE-LOVERS at MIT-MC At this point I have found sufficient Algorithms such that given a cube with everything correct except for possibly the four corner cubies on one side, I can (with a little thought and reference to my notes) solve the cube in 24qtws. [SPOILER WARNING] If all the cubes are in the right place, but possibly oriented wrong, the following transforms are used to TWIST the corners to the proper orientations: T1: F' (R' D' R D' F D F' D)^2 F 18qtws (FDL,RDF,BDR,LDB) => (DLF,FRD,RBD,DBL) T2: L D (D L' D' L)^2 D' L' R' D' (D' R D R')^2 D R 24qtws (FDL,RDF,BDR,LDB) => (LFD,DFR,RBD,DBL) T3: (D' L' D R D' L D R') (B' L D^2 L' B L B' D^2 B L') (FDL,RDF,BDR) => (DLF,DFR,DRB) 20qtws T4: (R D' L' D R' D' L D) (L B' D^2 B L' B' L D^2 L' B) (FDL,RDF,BDR) => (LFD,FRD,RBD) 20qtws Note: T3 and T4 are inverses based on the same components, which happen to commute. (see C1 and C2 below) T5: (L' U L F U F') D' (F U' F' L' U' L) D 14qtws (FDL,RDF) => (DLF,FRD) T6: L' F' D' L' D R D' L D F L F' R' F 14qtws (FDL,RDF) => (LFD,DRB) Along the same line as T5 and T6, but not usefull in the present discussion, shown to me in a private message from Dan.Hoey@CMU-10A. T7: F' R' D' R U R' D R F D F' U' F D' 14qtws (FDL,BUR) => (LFD,RBU) If all of the corner cubies are not in the proper positions it is more profitable to execute several corner moving transforms rather then one corner moving one then one corner twisting one. As presented here all transforms cycle the cubies in the same manner (clockwise) , though twisting the cubies in all possible ways. Their inverses (counter-clockwise) should also be kept in mind. C1: D' L' D R D' L D R' 8qtws (FDL,RDF,BDR) => (FRD,RBD,LFD) (twist all clockwise) C2: L B' D^2 B L' B' L D^2 L' B 12qtws (FDL,RDF,BDR) => (DFR,DRB,DLF) (twist all clockwise) Note: make reference in c1 (twist all counter-clockwise) C3: F L^2 D' R' D L' D' R D L' F' 12qtws (FDL,RDF,BDR) => (RDF,BDR,FDL) (don't twist at all) C4: F' R' B' R F R' B R 8qtws (FDL,RDF,BDR) => (FRD,BDR,DLF) C5: F L F' R F L' F' R' 8qtws (FDL,RDF,BDR) => (RDF,RBD,DLF) Note: C4 and c5 have been adopted from those presented by DCP in his message of 25 nov. 1308-EST C6: L F L' D^2 L F' L' F D^2 F' 12qtws (FDL,RDF,BDR) => (FRD,DRB,FDL) C7: R' D^2 R B' R' B D^2 B' R B 12qtws (FDL,RDF,BDR) => (DFR,RBD,FDL) C8: (C5)' (C1)'= 16qtws (R F L F' R' F L' F') (R D' L' D R' D' L D) (FDL,RDF,BDR) => (RDF,DRB,LFD) C9: (C1)' (C4)'= 16qtws (R D' L' D R' D' L D) (R' B' R F' R' B R F) (FDL,RDF,BDR) => (DFR,BDR,LFD) These nine transforms are the only possible legal ones (along with their inverses) which exchange three corners on a face (with the possibility of twists0, though I can't guarentee minimum lengths for any of them. If all of the corners are not in their proper positions then there are three possibilities: 1) One of the corners is in the right position and has the correct orientation. to fix: do the appropriate transform, or its inverse from the list given above. max length=16qtws 2) None of the corners is in the proper position to fix: using C1,C4, or C5 (the shortest ones) move one of the corners to the proper position and orientation, then continue as in case 1. max length=8+16=24qtws 3) One of the corners is in the correct position, but is in the wrong orientation. to fix: Preferably using C1,C4, or C5 move theproperly positioned corner out of its spot and at the same time move another corner into its proper position and orientation, then procede as in case 1. If none of C1, C4, or C5 will do the proper thing then a combination of C2 and C3 must be used, C2 first, to orient the corners correctly (with respect to the bottom) then use C3 to position the corners correctly. max length=8+16=12+12=24qtws These algorithms may be usefull to someone making a sides first, corners second cube solving algorithm. If anyone has any shorter algorithms for any of these transforms, please send them to the list. Unfortunatly I probably won't be able to answer any questions about this method as I am going back to school (Caltech) tommorrow (today?)(Sat. 3rd) and I don't have decent net access from there. Chris Worrell (ZILCH@MIT-MC) p.s.: sorry about the length of this message.  Date: 3 JAN 1981 0433-EST From: ZILCH at MIT-MC (Chris C. Worrell ) Subject: oops.... To: CUBE-LOVERS at MIT-MC Sorry folks, I missed one possibility. In case 2,my algorithm does not account for the configuration reached by L R D^2 R' L' F' B' D^2 F B D^2 14qtws (FDL,RDF,BDR,LDB) => (BDR,LDB,FDL,RDF) Either add this transform to the list given, or when you get to this particular configuration execute C3 twice 24qtws, but still inmy range and still along the general lines of the rest of the possibilities. Chris Worrell (ZILCH@MIT-MC)  ACW@MIT-AI 01/05/81 00:01:05 Re: Group theory and Cayley graphs. To: CUBE-LOVERS at MIT-AI I have some other short term resposibilities, but will get around to this in a couple of days. ---Wechsler  From: Don Woods Subject: excerpts from Singmaster To: CUBE-LOVERS at MIT-MC [In reply to message from Plummer sent 1 JAN 1981 1315-EST.] ** SPOILER WARNING!! SPOILER WARNING!! ** This message gives the shortest solutions known to Singmaster (as of the fifth edition of his booklet) for three pretty and moderately complex patterns, recently referred to as "baseball" (or "worm"), "snake", and "cube-in-a-cube". People wishing to investigate these patterns (as described in earlier messages) may not wish to read further. Notes: Singmaster uses the half-twist measure. His notation also includes special representation for the slice (center-twist) and antislice (such as L+R as opposed to L'+R) operations, which he counts as two twists; I have expanded this to strict "befuddler" (BFUDLR) notation in this message. BASEBALL or WORM RUFFD'RL'FB'D'F'R'FFRUUFRRF'R'U'F'UUFR SNAKE BRL'D'RRDR'LB'RR + UBBU'DBBRLUUR'L'BBD' It's not too hard to get to the snake, if you don't mind wasting few twists. Start with DLLRRD' and you're most of the way there. This assumes you know simple macros for swapping two pairs of edge cubies and for flipping two edge cubies. CUBE IN A CUBE BL'DDLDF'DDFD'B' + F'RUUR'U'BUUB'UF Again, the cube-in-a-cube is not hard to generate using two instances of the commutator macro -- R'FRF' UF'U'F U'RUR' -- plus a few simple extra twists. This is left as an exercise to the reader. -- Don.  Date: 7 January 1981 12:59 est From: Greenberg.Symbolics at MIT-Multics Subject: Lisp Machine Color cubesys To: cube-lovers at MIT-MC Lisp machine color cubesys has been fixed.  Date: 7 January 1981 1352-EST (Wednesday) From: Dan Hoey at CMU-10A To: Cube-Lovers at MIT-MC Subject: Pons Asinorum -- Part 1: Optimality Message-Id: <07Jan81 135220 DH51@CMU-10A> The Pons Asinorum (obtained by UUDDFFBBLLRR, and known as 6-X in Singmaster) is well-known to readers of this list. It is perhaps surprising that this so well-known position has anything more to teach us. The first surprise is that the 12-move sequence given above is provably optimal in the quarter-twist metric. Proofs were sent to me by David C. Plummer, who attributed it to Alan Wechsler, and by Chris C. Worrell. While it is well-known (See Alan Bawden's messages of 31 July 1980 13:06-EDT and 31 JUL 1980 2159-EDT) that some positions require at least 21 moves, the longest sequence which has previously been proven optimal is LR'FB'DU'LR' for the six-spot configuration. It is good to see a 12-move sequence proven optimal -- and in a way not dependent on the vagaries of programming errors and cosmic rays. The proof of optimality relies on the "Oriented Distance from Home" (ODH), used by Vanderschel (6 Aug 1980 1909-PDT) in his proof of edge orientation parity conservation. The ODH of an edge cubie (in some position and orientation) is defined to be the minimum number of quarter-twists required to move that cubie to its home position and orientation. A table of possible ODH values of the UF cubie is given below, indexed by the position of that cubie's F tab. + 3 + 2 U 2 + 3 + + 1 + + 0 + + 1 + + 2 + 2 L 2 1 F 1 2 R 2 3 B 3 + 3 + + 2 + + 3 + + 4 + + 3 + 2 D 2 + 3 + The Pons Asinorum moves every edge cubie to a position and orientation which has an ODH of 4. To move all twelve cubies in this way requires a total of 48 edge moves, and only four edge moves can be accomplished by each quarter-twist. Thus the Pons Asinorum requires twelve quarter-twists. Unfortunately, this seems to be the only really impressive result to be derived from counting ODH. All edges flipped (Singmaster's 12-Flip) can be shown to require at least ten quarter-twists, but this is a far cry from the 28-qtw process which is the best known (Plummer, 10 Dec 1980 0157-EST). A brute force technique for deriving such results is of course possible, but to show a twelve-move lower bound seems to require sorting and merging two lists of over one hundred thousand positions each, an act which is viewed as unsociable (or, more usually, impossible) on the systems to which I have access. Anyone who has a gigabit to spare should get in touch -- there are several good problems for which brute force seems attractive if there is enough of it. Surprise number two -- Pons Asinorum in the Supergroup -- in an hour or two. Dan  Date: 7 January 1981 1615-EST (Wednesday) From: Dan Hoey at CMU-10A To: Cube-lovers at MIT-MC Subject: Pons Asinorum -- Part 2: Pons in the Supergroup Message-Id: <07Jan81 161515 DH51@CMU-10A> The second observation I would like to make regarding the Pons Asinorum involves the Supergroup (also known as "the extended problem") in which the orientation of face centers is considered. The process UUDDFFBBLLRR turns each of the face centers 180 degrees, so Pons Asinorum is symmetric in the Supergroup as well. (Turning each face center 180 degrees is the M-symmetric position Big Ben Squared, which I will call Noon.) There is another optimal way of making a (pseudo-) Pons Asinorum, (UD'FB')^3, which differs from the true Pons only in the face center orientations. According to an exhaustive search I carried out by hand, this is the only pseudo-Pons (up to M-conjugacy) that can be obtained with six slice moves. I would be very interested in hearing about any other twelve-qtw positions which differ from the Pons Asinorum only in the Supergroup. I have found a 16-qtw process for Pons Asinorum composed with Noon, (UD FB FB UD)(FB UD UD FB), which looks like Pons Asinorum, but does not rotate the face centers. This in turn gives a 20-qtw process for Noon itself: LLRR UUDD (UD FB FB UD) (FB UD UD FB) FFBB = LLRR (U'D' FB FB UD) (FB UD UD F'B'). Of course, there's no assurance of optimality here. It occurs to me that many readers of this list may find details of the Supergroup uninteresting. I have more on this subject, so if you would or wouldn't like to know more about the Supergroup, send a vote to Hoey@CMU-10A and we'll see what to do. Dan  Date: 8 JAN 1981 1515-EST From: DR at MIT-MC (David M. Raitzin) To: CUBE-LOVERS at MIT-MC I've been reading the old mail from this mailing list, and I've noticed some discussion on the definition of what is a single twist. As far as I can see, the definition of a twist should be the change in position of all the cubies in a single plane performed by a single motion. In other words that should include a 90 degree twist, a 180 degree twist, and a twist of the middle slice (the last one can be thought of as holding the U and D parts of the cube in place with one hand, while moving the middle slice with the other).  Date: 8 JAN 1981 1523-EST From: DR at MIT-MC (David M. Raitzin) To: CUBE-LOVERS at MIT-MC The other day, having nothing to do, I started optimizing my transformations. Counting 90-degree twist, 180-degree twist and a twist of the middle slice as a single move, I reached the following numbers: for Plummer cross: 24 moves, and for what I call inverting the cube (that means flipping every non-corner cubie) 29 moves. Now realizing that neither of those comes close to the optimum # of moves, I'd like to know how far of the so far achieved optimum am I?  Date: 8 January 1981 20:06 cst From: VaughanW.REFLECS at HI-Multics (Bill Vaughan) Subject: Befuddled by BFUDLR To: CUBE-LOVERS at MIT-MC cc: VaughanW.REFLECS at HI-Multics This is a plea for another notation. BFUDLR is sufficient to describe anything. So what? It's about as readable as a LISP s-expression, as rich as the average grad student, and (my particular gripe) it's impossible to express an elegant sequence in it and keep any of the elegance. I want to keep this short, so I'll only give a few examples. The first is the Sprat Wrench. BFUDLR calls it: RL'URL'BRL'DRL'F. But the way most everyone does it, it's: (XU)*4, where X means "move the LR slice clockwise as viewed from the left." The next example (I don't know its name) flips all top and bottom edges. BFUDLR calls it: LRUDFBLRUDFB. Interesting, but this is nicer: (R-B-)*3, where "foo-" means "foo antislice" and is done by twisting foo and its adjacent slice clockwise 1qtw, then twisting foo another qtw. A move yielding (RF, BL, RB) has been published (Don Woods 6 Jan 81) in BFUDLR as: BRL'D'RRDR'LB'RR. Now where's the symmetry in that? But annotate the same move BXB'RR.BX'B'RR (X as in first example) and you can see how pretty it is. And it's a lot easier to remember. The key is that the fixed orientation of the center cubies shouldn't be a sacred cow. Often, keeping a corner cubie as a fixed point will yield a far more natural notation. The commonest compound moves: slice, antislice, and possibly Singmaster's Y and Z commutators, should have specialized notations. A move that I use commonly in solving the cube is a monotwist: Y(f,r)*2.L.Y'(f,r)*2.L'. That's a lot harder to understand as: FR'F'RFR'F'RLR'FRF'R'FRF'L'. I don't have good notations to offer for slice and antislice. What I do with paper and pencil involves overstrikes that my CRT can't handle. Something nice and linear is needed, with all the characters in ASCII. Any suggestions, anyone?  Date: 8 January 1981 2235-est From: Bernard S. Greenberg Subject: Cubesys and FLUBRD To: CUBE-LOVERS at MIT-MC A new hack for interpreting transforms expressed in FLUBRD notation has been added to ITS and LISPM cubesys. (As I am no longer with Honeywell, I can no longer modify Multics cubesys, but I will give instructions below for how to use this on Multics). Transforms are defined in Lisp, with the "defxform" macro. "defxform" is followed by a name to assign to the transform, and one to any number of "cube operations". A cube operation is either 1) a flubrd syllable 2) (apply ), meaning do that transform 3) (inverse ), meaning "undo" that transform 4) any other list, which is interpreted as a list of cube-operations A flubrd syllable is an atomic symbol whose name is a character string consisting of one to any number of flubrdniks. A flubrdnik is either 1) F L U B R D f l u b r d (case doesnt count) 2) F* L* U* .... etc, meaning counterclockwise turn 3) F2 L2 U2 .... etc, meaning 180 degree turn. Here is the provided, automatically-loaded library of transforms: (defxform monotwist-op (ld l*d*) ldl*) (defxform monotwist (apply monotwist-op) u (inverse monotwist-op) u*) (defxform quark r2 (apply monotwist) r2) (defxform pons f2 b2 r2 l2 u2 d2) (defxform christman-cross ;Saxe 16 dec 1980 f ud llrr ud fb uudd b) (defxform plummer-cross ;Saxe 3 dec 1980 f (ll rr) f b (ll rr) f l (bb ff) l r (bb ff) l (uu dd)) To load new transforms... ITS: ^X break, load a file full of defxforms, ^G back. Lispm: , load the file,^Z (oh yes, Lispm cubesys now has a ^Z handler) Multics: ESC X loadfile the file. To run a transform: ITS: Use the X command. the transform name will be prompted for. Lispm. Use the X command. A MENU OF KNOWN TRANSFORMS WILL POP UP! Mouse at it. Multics: ESC X run-xform On Multics, you will have to load the new package before doing any of this, with esc-x loadfile. Currently, it is >udd>sym>bsg>cxfrm .... it may move or go away. Multicians, contact me if you have any interest in it.  Date: 9 January 1981 0551-EST (Friday) From: Dan Hoey at CMU-10A To: Cube-lovers at MIT-MC Subject: The Supergroup -- Part 1: Physical reality Message-Id: <09Jan81 055144 DH51@CMU-10A> Well, whoever doesn't like the Supergroup didn't send me any messages, and several who do did, so here goes. This message is part one of three, separated for the benefit of MIT's notoriously fragile mailer. In case anyone has managed to miss it, the Supergroup is the group underlying the cube when face center orientation is taken into account. By the "orientation" of a face center, we refer to the number of 90o twists of that face center from the position designated "solved." To visualize this, Singmaster suggests replacing the solid colors on the sides of the cube by some nine-piece pictures, so that the centers must be restored to their initial (untwisted) state to solve the cube. He reports that this was done (on two sides only) by a company in England, which printed its logo on cubes for a promotion. The term "Supergroup" is also due to Singmaster, and I adopt it in favor of the term "the extended problem," which has appeared in Cube-lovers. To make the face center orientation visible on my cube, I first used magic marker, which rubbed off, then paint, which attacked the colortabs and looked and felt awful. [Then I went to a stationery store and got plastic tape and replaced my colortabs -- no orange, so my cube now has a tan face.] I marked the face center orientation by cutting out circles from the plastic colortabs to let the black plastic show through. I like it, though some people think it looks like the cube has been used for target practice. Each cutout circle has a diameter of about 3/8" (1/2 the side of a cubie) and is centered at the corner of a face center, overlapping two edge cubies and one corner cubie. The orientation is then visible if either the corners or the edges are in the home position. It doesn't particularly matter which corners of the face centers are used; I chose the pattern which has the same symmetry group as Plummer's cross (unique up to M-conjugacy). There will be a short intermission while we change reels.  Date: 9 January 1981 0629-EST (Friday) From: Dan Hoey at CMU-10A To: Cube-lovers at MIT-MC Subject: The Supergroup -- Part 2: At least 25 qtw, and why Message-Id: <09Jan81 062915 DH51@CMU-10A> Alan Bawden (31 JUL 1980 2159-EDT) calculated that it must take at least 21 quarter-twists to solve an ordinary cube, and 24 qtw to solve a cube in the Supergroup. This message explains how the first bound can be obtained, improves the second, and points toward a technique for possible further improvements. Express any (optimal) sequence of twists as a sequence of segments, where each segment is a sequence of twists on two opposite faces, and no two adjacent segments operate on the same pair of faces. Because the quarter-twist has period four, and opposite faces commute, a segment operating on faces X and Y has one of the forms X, X', Y, Y' (1 qtw -- 4 ways) XX, YY, XY, YX, X'Y, Y'X, XY', Y'X (2 qtw -- 6 ways) XXY, XXY', XYY, X'YY (3 qtw -- 4 ways) XXYY (4 qtw -- 1 way). There are 3 ways of choosing X and Y for the first segment, and two ways of choosing them for every succeeding segment. Let P[n] be the number of positions that are exactly n qtw from SOLVED. Then bounding P[n] by the number of n-qtw sequences, P[0] = 1 P[1] <= 4*3*P[0] P[2] <= 4*2*P[1] + 6*3*P[0] P[3] <= 4*2*P[2] + 6*2*P[1] + 4*3*P[0] P[4] <= 4*2*P[3] + 6*2*P[2] + 4*2*P[1] + 1*3*P[0] P[n] <= 4*2*P[n-1] + 6*2*P[n-2] + 4*2*P[n-3] + 1*2*P[n-4] for n > 4. Evaluating this recurrence, substituting strict (in)equality where I have personally verified it, and rounding truthfully yields: P[0] = 1 P[9] < 724,477,008 P[18] < 4.048*10^17 P[1] = 12 P[10] < 6.792*10^9 P[19] < 3.795*10^18 P[2] = 114 P[11] < 6.366*10^10 P[20] < 3.557*10^19 P[3] = 1,068 P[12] < 5.967*10^11 P[21] < 3.334*10^20 P[4] = 10,011 P[13] < 5.594*10^12 P[22] < 3.125*10^21 P[5] <= 93,840 P[14] < 5.243*10^13 P[23] < 2.930*10^22 P[6] < 879,624 P[15] < 4.915*10^14 P[24] < 2.746*10^23 P[7] < 8,245,296 P[16] < 4.607*10^15 P[25] < 2.574*10^24 P[8] < 77,288,598 P[17] < 4.319*10^16 There are 4.325*10^19 positions in the standard cube; since P[0]+P[1]+...+P[20] < 3.982*10^19, there must be a position at least 21 qtw from SOLVED (The number 22 has appeared in Cube-lovers recently, but it was an error). There are 8.858*10^22 positions in the Supergroup; since P[0]+P[1]+...+P[23] < 3.280*10^22, there must be a position at least 24 qtw from SOLVED. But this can be improved: half of the positions in the Supergroup are an odd number of qtw from SOLVED, and since P[1]+P[3]+...+P[23] < 2.963*10^22 is less than half the Supergroup, there must be some odd-length elements of the Supergroup at least 25 qtw from SOLVED. QED. (If you think there's something fishy here, mail to Hoey@CMU-10A for clarification. I am responsible for any cruft that has crept into the original, elegant, formulation due to Jim Saxe.) The recurrence on which this bound relies is due to the relations F^4 = FBF'B' = I (and their M-conjugates.) It may be possible to improve the recurrence by recognizing other short relations. Exhaustive search has shown that there are none of length less than 10. The most promising ones I know of come from Singmaster: I = FR'F'R UF'U'F RU'R'U (12 qtw), I = (FFBB RRLL)^2 (16 qtw), and a 14-qtw relation which holds only in the standard group, since it twists a face center 180o (see part 3). Unfortunately, the number of intermediate terms grows too large to be comfortably hand-computable, and there are a few conceptual problems to hacking it out. If you can improve this, or know of any other relations shorter than 24qtw, I'd like to hear about it. Coming up next: SPOILERS  Date: 9 January 1981 0756-EST (Friday) From: Dan Hoey at CMU-10A To: Cube-lovers at MIT-MC Subject: The Supergroup -- Part 3: A Super-H and Spoilers Message-Id: <09Jan81 075610 DH51@CMU-10A> IMPROVEMENT Jim Saxe (16 December 1980 1841-EST) gave a 16-qtw process for the H position: FF LL DD FF BB DD RR FF. Unfortunately, the position obtained by this process is not H-symmetric in the Supergroup: the F, L, B, and R face centers are rotated 180 degrees, but the U and D face centers are in the home orientation. I have a 16-qtw process which leaves all face centers in the home orientation: (FB UD)^2 (UD FB)^2. This may look familiar -- conjugation by FBUD yields the 16-qtw "Bridge at Midday" I sent day before yesterday. SPOILERS I developed a solution method on my own, but it was a long one. The following good methods, which affect only face centers, are from Singmaster. It seems simplest to solve the cube before applying them, since some of the most popular processes (e.g., the Spratt wrench (but not mono-ops!)) change face center orientation. The first method can be used to perform any multiple of four face-center quarter-twists on the faces in a centerslice. At most two applications are necessary to accumulate any remaining twist in one face center. The method is given in Singmaster as two examples, but he doesn't explain how they work. Hopefully the following discussion will make them easy to use. Choose a face center X that needs to be twisted, and a centerslice containing X and other face centers to be twisted (call these FCT's). Place the cube with X up and with the FCT's in the FB slice (i.e., among R, D, and L). The basic move has much of the flavor of a mono-op: 1: Move the LR centerslice toward you. (Move a face center from U to F. X and the FCT's are now in the UD centerslice. 2: Select an FCT, and move it to the F face with UD centerslice moves. 3: Move the LR centerslice away from you. (Undo step 1. The U face now contains the selected FCT and all the U edge and corner cubies. 4: Twist the U face the amount required by the selected FCT. Repeat the basic move until all FCTs have been selected. Then perform the move one last time, but select X instead of an FCT in step 2 and twist the U face to fix the cube in step 4. [After sending the previous part, I realized that in the case of one FCT, this is another 14-qtw relation in the standard cube: RL'FB'UD' R DU'BF'LR' U' But the one alluded to is in the next paragraph.] Since the total number of 90o face center twists must be even (see Vanderschel's message of 6 Aug 1980 1909-PDT), the preceding will solve the cube up to a 180o twist. The process (URLUUR'L')^2 twists the U face center 180o. This is the only short transform given in Singmaster for twisting face centers by a nonmultiple of four; I'd be interested in any others you know. That's it for now. Happy Supercubing! Dan  Date: 9 Jan 1981 14:59 PST From: McKeeman at PARC-MAXC Subject: Re: Befuddled by BFUDLR In-reply-to: VaughanW.REFLECS's message of 8 January 1981 20:06 cst To: VaughanW.REFLECS at HI-Multics (Bill Vaughan) cc: CUBE-LOVERS at MIT-MC Bill, Good points. I am not sure how to solve the problem either. But here are some comments. RubikSong is simply assembly language to drive the human computer. That has both its advantages and disadvantages. The original suggestions also included parameterless subroutines and whole cube moves. Your point it, I think, that there are some easy manipulations that are obscure, at best, in FLUBRD + IJK. One could take the position that definitions need not be mnemonic since in steady state their names will be used with a higher level of semantics. Then we get Slice = L' R J' SpratWrench = (Slice U)*4 That seems tolerable but still not well matched to the human at the lowest level. A nice property the notation could have would be to be concise where the human manipulation is concise, without introducing a large number of unmnemonic primitives. For example, we might use Xnnn for multiple parallel twists. "R antislice" = L012 = L' R' J Then we have, for example, LRUDFBLRUDFB = (L012 U012)*3, and R' = L001 R = L001' Slice = L010. Commutators are pretty common (i.e., X Y X'). Somebody suggested X[Y] for them. The idea is that X is a function to apply to Y. The main problem is that the human machine isn't very good at doing complicated inverses without some special practice. But, assuming the practice, then BRL'D'RRDR'LB'RR = B[Slice] (RRB)[Slice'] = (B[Slice])[RR] RR = (B[Slice]RR)[] Feedback appreciated... Bill  Date: 9 Jan 1981 1648-PST From: Dave Dyer Subject: nomenclature To: cube-lovers at MIT-MC The real problem with RLUDFB is that it is nearly impossible for the casual observer to determine if two "transformations" are the same or not. Transformations should be described such that there is ONE description of each transformation. We can't really get all the way to the ideal, because there are discinct sequences that lead to the same termination. But we can eliminate a lot of the confusion. I Propose that all transformations be described in terms of twists done by both hands without changing the overall cube orientation. my proposed primitives are 1 "forward" twist of left or right face 2 1/2 twist of left or right face 3 "backward" of left or right face URF orient the cube to work on named face, with your right hand. Names are lambda-bound from the start of the transformation. To instantiating a transformation one can simply substitute the color for the orientation label notation is <(optional) left hand> For example, a sprat wrench: UDLRFB calls it: RL' U RL' B RL' D RL' F. I call it: R11 U1 R11 F03 R11 U03 R11 F1 -------  Date: 9 January 1981 19:40 cst From: VaughanW.REFLECS at HI-Multics (Bill Vaughan) Subject: Re: nomenclature To: Dave Dyer cc: CUBE-LOVERS at MIT-MC In-Reply-To: Msg of 01/09/81 18:48 from Dave Dyer It would seem that there are two needs immediately visible. One need is for a notation to communicate a metamorphosis of the cube from one cube-lover to another hexahedrophile. This notation should capture the spirit of the thing being described; it should be rich and chunky (like soup?). The other need is for an archival notation, for reference and cataloguing. It must be spare and canonical. There must be one and only one way to describe a sequence of moves. (Implication: a way to get reflections, inversions etc. out of the notation? how?) No nourishment for the spirit there, but when you need to look something up... Well, clearly they can't be the same notation. (Though even the archival notation could invoke functions.) Or can they? Food for thought... Anyway, plain ole BFUDLR can't do either job decently. Not rich or expressive enough for the first need, too expressive for the second (gee, I wonder how many ways there are to annotate PONS?) Well, other people can muddle this out - I'm going home to get some dinner.