Date: Wed, 07 Jan 81 13:52:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Pons Asinorum -- Part 1: Optimality 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: Wed, 07 Jan 81 16:15:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Pons Asinorum -- Part 2: Pons in the Supergroup 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: Fri, 09 Jan 81 05:51:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: The Supergroup -- Part 1: Physical reality 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: Fri, 09 Jan 81 06:29:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: The Supergroup -- Part 2: At least 25 qtw, and why 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: Fri, 09 Jan 81 07:56:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: The Supergroup -- Part 3: A Super-H and Spoilers 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: Thu, 22 Jan 81 00:10:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Correction to "Symmetry and Local Maxima" In our message "Symmetry and Local Maxima" (14 December 1980 1916-EST) we examined local maxima both in the Rubik group and in the Supergroup. David C. Plummer has discovered a flaw in our argument for the Supergroup, which we now correct. Plummer has previously noted (30 DEC 1980 0109-EST) that the T-symmetric position GIRDLE CUBIES EXCHANGED, depicted near the end of section 4, is an odd distance from SOLVED. This is also true of the composition of GIRDLE CUBIES EXCHANGED with GIRDLE EDGES FLIPPED, ALL EDGES FLIPPED, PONS ASINORUM, or any combination of the three, for a total of eight positions. In addition, there are four different T groups, each corresponding to a choice of opposite corners of the cube. Thus 32 of the 72 positions with Q-transitive symmetry groups are an odd distance from SOLVED. The discussion of the Supergroup in S&LM noted that the only face-center orientations which yield Q-transitive symmetry groups are the home orientation and all face centers twisted 180o (called NOON in Hoey's message of 7 January 1981 1615-EST). Any position with either of these face center orientations must be an even distance from SOLVED, so that any reachable position which is T-symmetric in the Supergroup must be an even distance from SOLVED. In our earlier note, we erroneously calculated the number of Supergroup positions with Q-transitive symmetry groups by simply doubling the number of such positions in the Rubik group to allow for the two allowable face-center orientations. What we failed to notice--until Plummer pointed it out--is that neither of the allowable face-center orientations can occur in conjunction with an odd position. The corrected count of known Supergroup local maxima is determined by counting the 40 *even* symmetric positions, multiplying by two, and subtracting 1 for the identity, yielding 79. As Plummer notes, this is surprisingly close to the number of known local maxima in the Rubik group, which stands at 71. The number of known local maxima modulo M-conjugacy is 25 for the Rubik group and 35 ( = 2*(26-8) - 1 ) for the Supergroup. --- Date: Tue, 27 Jan 81 01:02:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Pretty Patterns and Solutions We are disappointed at Chris C. Worrell's use of the term "Baseball" for the position known in the literature as the "Worm". Worrell's term propagates the apparently popular misconception that baseballs are covered with three-lobed pieces of leather. The position which *we* call "Baseball" reflects the construction much more accurately: D D D U U U F F F U U U L R B R B L B L R F F F L R B R B L B L R D D D L R B R B L B L R F F F D D D U U U Currently, our best process for this position is 34 qtw. The corners are fixed with FRLUDB, two edge four-cycles are inserted in the middle, and a Spratt wrench is conjugated inside that: FRL (RRLL UUDD F' U (F' LUD' BUD' RUD' FUD' F) UDD RRLL F) UDB. The class of patterns which Bill Vaughan calls "Swirl Patterns" (15 January 1981 19:13 cst) are also known as "6-2L" patterns in Singmaster, and the particular one he calls the "Pinwheel" (on 16 January 1981 12:09 cst) is an M-conjugate of the AC-symmetric "Twelve-L's" mentioned in our message on Symmetry and Local Maxima (14 December 1980 1916-EST, Section 6). [Incidentally, the diagram he displays in the message of 16 January is in error; the left and right face centers have been swapped. This is made less obvious by the unusual orientation of the cube in that diagram.] We have found a totally magical 12 qtw process for the Pinwheel: FB LR F'B' U'D' LR UD. Vaughan's definition of Swirl Patterns seems unduly restrictive to us on one count: he requires the two L's on each face to be of "complementary" (evidently meaning opposite) colors. This is not necessary for an L pattern. According to our analysis, however, at least two of the faces of any L pattern must have L's of opposite colors, and five is easily seen to be impossible. We know of no patterns having three or four such pairs. But there are several with two pairs. Our favorite example is a relative of the Baseball which we name for Linda Lue Leiserson, who has the appropriate initials. D D D F U D F F F U U U L B B R L L B R R D F U L R B R B L B L R D D D L L B R R L B B R F F F U D F U U U We have a 24 qtw process for Linda Lue's L: F'BB L (B U'LR' F'LR' D'LR' B'LR' B') R UD B'FF This has a Spratt wrench, conjugated by B', embedded in magic. David C. Plummer (3 SEP 1980 2123-EDT) reported that it is possible for each of the six faces of the cube to show a capital "T". Our analysis indicates that there are two sorts of T patterns: D U D D D U D U D U U U U U U D D U L L L F F F R R R L R R F F F R L L R L R B F B L R L L L L B F B R R R R L R B F B L R L L R R B F B R L L D D D D U U U D U D D D U D U D U U B B B B B B F B F F B F F B F F B F Tanya's T Plummer's T Tanya's T is named for Tanya Sienko (who inspired the problem) and for euphony. Plummer's T is named for Plummer's Cross (which has the same symmetry group) and for homophony. There are 24 M-conjugates of Tanya's T, while Plummer's T has 8 M-conjugates. By adapting a process due to David C. Plummer, we have developed a 16-qtw process for Tanya's T: (FF UU)^3 (UU LR')^2. The first part swaps two pairs of edge cubies, and the second part is magic. We have found a 28-qtw process for Plummer's T, which is entirely magical: FF UD' F'B' RR F'B U'D RL FF RL' UD' RL FF R'L U'D'. A position which is not so visually striking, but which is important in the symmetry theory we have discussed earlier, is "All Corners Twisted": B U B U U U F U F U L U L F R U R U R B L L L L F F F R R R B B B D L D L F R D R D R B L F D F D D D B D B This can be achieved in 30 qtw with FLU (LRRFFB')^4 U'L'F'. The process is a conjugated from a 24 qtw process invented by Thistlethwaite. Unfortunately, Thistlethwaite's process twists the wrong corners, and no cancellation can be performed in the conjugation. If any process can be found which twists four corners clockwise and four counterclockwise, leaving the rest of the cube fixed, then any such pattern can be made by adding at most 6 qtw. --- Date: Sun, 01 Feb 81 05:39:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Algorithm for finding cube group orders David C. Plummer (31 Dec 1980 1210-EST) gave a preliminary analysis of the 5x5x5 cube. I complete it here. Let a move consist of twisting any of the six faces, at a depth of 1 or 2. It will be necessary to consider the two depths as distinct; M1P will refer to the number of depth 1 moves (mod 2), while M2P will refer to the number of depth 2 moves (mod two). It is important to realize that the two parities vary independently. The tabs on each face are assigned types C L E R C R D A D L E A X A E L D A D R C R E L C as in Plummer's analysis. Let COP ("C" Orientation Parity) and CPP ("C" Permutation) parity be defined as before. As before, COP=0 (mod 3). We must be explicit about the CPP this time: Since either kind of move is an odd permutation of the "C" faces, CPP=M1P+M2P. As in the 4x4x4 case, "R"'s may be ignored and "L"'s have no orientation. The permutation parity (LPP) is important, however. Depth 1 moves are an even permutation of the "L"'s (two 4-cycles), so they do not affect the LPP, but Depth 2 moves are an odd permutation of the "L"'s (three 4-cycles). Therefore LPP=M2P. Note that while LPP and CPP may vary independently, they together determine both M1P(=LPP+CPP) and M2P(=LPP). The "E" faces act as in the 3x3x3 case, with orientation and permutation parity. Orientation changes on four "E"'s with every move, so EOP=0 (mod 2). Permutation parity changes with every move, so EPP=M1P+M2P. This has already been determined by CPP, so only half of the "E" permutations are possible. Every move is an odd permutation of the "D" faces, so DPP=M1P+M2P. Since M1P+M2P=CPP is determined, only half of the "D" face permutations are possible. Moves work differently on "A" faces depending on depth: Depth 1 moves are odd permutations of the "A"'s, and depth 2 moves are even. Thus APP=M1P, which is determined by CPP+LPP, so only half of the "A" permutations are possible. Finally, the "X" faces have orientation which changes on every move, so XOP=M1P+M2P, and only half of the "X" orientations are possible. Thus there are 96 orbits, corresponding to COP (mod 3) and EOP, EPP+CPP, DPP+CPP, APP+CPP+LPP, and XOP+CPP (mod 2). The basic combinatoric is as Plummer described: 8! C Permutations 3^8 C Orientations 24! L Permutations 1 R Permutation 12! E Permutations 2^12 E Orientations 24! D Permutations 24! A Permutations 4^6 X Orientations which when multiplied together and divided by 96 yields about 5.289*10^93. [This differs from Plummer's result by a factor of 4096 because (4^6/2) he didn't count X Orientations, and (2) he did not realize that LPP and CPP are independent.] My implementation of Furst's algorithm claims that all of these are reachable. To count the number of reachable color patterns, divide this note that there are by (4!)^6/2 invisible D permutations, (4!)^6/2 invisible A permutations, and 4^6/2 invisible X orientations that satisfy the invariants. While there are pairs of L/R edges that look the same, they cannot be interchanged, for that would entail putting an L tab into an R position. So there are 2.829*10^74 different color patterns achievable. ---------------------------------------------------------------- --- Date: Sun, 01 Feb 81 06:12:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Algorithm for computing cube group orders Oops... you have just received part 3. This is part 1.... This note is in somewhat delayed response to the note by David C. Plummer (31 DEC 1980 1115-EST) regarding the 5x5x5 Rubik cube, and some related ideas. In that note he tried to calculate the size of that cube's Rubik group, but left several of the values open to conjecture. I will complete the answer, and answer a few others that haven't been addressed here. Computing the size of a Rubik group is a special case of computing the size of a permutation group, given generators for that group. The technique we have already seen in these pages is in two parts. The first part seems relatively easy: certain invariants must be observed in the generators, such as "Corner Orientation Parity" and "Total Permutation Parity." [In this general setting, such invariants as "Colortabs on the same cubie move together" must also be considered.] It may take some thought to dig out the invariants, but once you have seen them demonstrated for Rubik's Cube, you have an idea of what to look for. The second part is the devil: it must be demonstrated that every permutation satisfying those invariants is actually generated. This involves developing a solution method for the puzzle. Given the days or weeks (or eternity) it takes most people to develop such a method--with cube in hand!--it is hardly surprising that few answers have been developed. Well, the second part is no longer a hard problem. The answer lies n a paper by Merrick Furst, John Hopcroft, and Eugene Luks, entitled "Polynomial-Time Algorithms for Permutation Groups," which was presented at the 21st Annual Symposium on Foundations of Computer Science, October 1980. Among the results is an algorithm which takes as input a set of permutations on n letters, and reports the size of the group G which is generated by those permutations. The algorithm operates by decomposing G into a tower of groups I=G[0], G[1], ..., G[n]=G, where G[i] contains those permutations p in G for which p(k) = k whenever i < k <= n. The index of G[i-1] in G[i] is developed explicitly by the algorithm; in fact, a representative g[i,j] of every coset of G[i-1] in G[i] is exhibited. These coset representatives generate G; in fact, every element of G is representable as a product of the form (g[1,j1])(g[2,j2])...(g[n,jn]). For this reason the coset representatives are called "strong generators" for G. There is a good deal of structure that can be learned from the strong generators, in addition to the size of G. I have coded this algorithm in Pascal, and offer the program for the use of anyone who needs to find group orders. The relevant files are on CMU-10A, from which other sites may FTP without an account. The relevant files are all:group.pas[c410dh51] The source all:rubik.gen[c410dh51] A sample input -- the supergroup all:rubik.lst[c410dh51] Sample output. Of course, CMU Pascal is probably slightly different from yours, and OS-dependent stuff like filenames is likely to be wrong. I'll be glad to help out in cases of transportability problems. The other problem you may run into is resource availability. The running time of the algorithm is proportional to (nm)^2, where m is the total number of strong generators; the supergroup (n=72, m=279) takes 639 cpu seconds on a KL-10, and bigger problems grow rapidly. The program also requires 47000+47m words. It might seem that the problem has been answered, but I find that simply knowing the size of a group is not very satisfying. There doesn't seem to be a better way of demonstrating lower bounds, but the upper bounds that come from invariants are much more elegant than a simple numerical answer. Unfortunately, I know of no mechanical way of finding the invariants. Furthermore, using group theory does not help much when we ignore the Supergroup. Consider the 4x4x4 cube. If we are only concerned with the color pattern on the cube, then a twist may or may not affect the four face centers--it depends on whether they are the same color or not. In summary, the algorithm has inverted the hard and easy parts of cube analysis. The size of the group is now easy to determine, making invariant-finding the hard part. Further, the algorithm works on the Supergroup, making counting distinct color patterns the part which requires further analysis. Two messages follow, supplying these answers for the 4x4x4 and 5x5x5 cubes. --- Date: Sun, 01 Feb 81 06:51:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Analysis of the 4x4x4 cube The first problem for the 4x4x4 cube is in eliminating positions that arise from whole-cube moves. This was done with the 3x3x3 by keeping the face-center positions fixed, but there are no face centers on the 4x4x4--or there are, but they don't maintain a fixed orientation relative to each other. I standardize the spatial orientation by keeping the DBR corner in a fixed position and orientation. A move then consists of twisting one, two, or three layers parallel to the U, F, or L face. Thus F3' is equivalent to twisting the B face. I will refer to the number of layers twisted as the "depth" of the move. Following David C. Plummer's notation (31 DEC 1980 1210-EST), organize each face of the cube as C L R C R X X L L X X R C R L C. I will assume familiarity with David Vanderschel's analysis of the 3x3x3 case, which was presented in his message of 6 August 1980. "C" faces act as they do in the 3x3x3 case, except that one of them does not move. Corner Orientation Parity (COP) is preserved and Corner Permutation Parity (CPP) changed by every quarter-twist. Depending on the depth, a quarter twist can permute the "L" faces in an odd or an even permutation. Also, "L" faces do not change orientation (or move to "R" positions). Every "R" face is determined by the "L" face (on an adjacent side of the cube) with which it shares a cubie. Thus the arguments for EOP and EPP do not apply. Every quarter-twist is an odd permutation of the "X" faces: either one, three, or five four-cycles, depending on the depth. Letting XPP be the permutation parity of the "X" faces, the Total Permutation Parity TPP=XPP+CPP (mod 2) is preserved by every quarter-twist. Thus the 4x4x4 cube group has at least six orbits, according to COP (mod 3) and TPP (mod 2). The basic upper bound of 7! Corner Permutations 3^7 Corner Orientations 24! L Permutations (which determine the R permutations), and 24! X Permutations, divided by six, yields an upper bound (of about 7.072*10^53). I have run Furst's algorithm on the problem, and my program claims that all these positions are reachable. To calculate the number of reachable color patterns, note that there are 4! permutations of each quadruple of "X" faces which are indistinguishable. However, the TPP constrains the XPP so as to reduce this by a factor of two. Dividing 7.072*10^53 by (4!)^6/2 yields 7.401*10^45. [At this point, you may find it instructive to view the message before last, which analyzes the 5x5x5 cube in the context of this message and the one immediately preceding. I regret the accidental disorder. These three are all for now, although I have results on tetrahedra, octahedra, and a dodecahedron which I am in the process of writing up.] --- Date: Mon, 16 Feb 81 23:27:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Four colors suffice Douglas Hofstadter, in the Metamagical Themas column in Scientific American this month, shows two alternate ways of coloring a cube. Both suffer from two drawbacks: They fail to distinguish all cube positions, and they use more than six colors. This seems inefficient to us, since there is a coloring of the cube which distinguishes all elements of the Supergroup and uses only four colors (and which, like Hofstadter's colorings and the standard coloring, satisfies the restriction that every whole-cube move is a color permutation, as discussed in point 2 below). Our coloring, called the Tartan, is formed by assigning the colors blue, green, red, and yellow to the four pairs of antipodal corners of the cube. Thus for each face of the cube, the four corners of the face are assigned four different colors. We use the term ``plaid'' to denote such an assignment of colors to the corners of a square. To color the cube, divide each facelet of each cubie into four squares, and color the squares so all facelets on a side of the cube display the plaid associated with that face. The result is shown below, with the initial assignment of colors to corners in lower case. (r)---------------(y) | R Y R Y R Y | | B G B G B G | | | | R Y R Y R Y | | B G B G B G | | | | R Y R Y R Y | | B G B G B G | (r)---------------(b)---------------(g)---------------(y) | R B R B R B | B G B G B G | G Y G Y G Y | | G Y G Y G Y | Y R Y R Y R | R B R B R B | | | | | | R B R B R B | B G B G B G | G Y G Y G Y | | G Y G Y G Y | Y R Y R Y R | R B R B R B | | | | | | R B R B R B | B G B G B G | G Y G Y G Y | | G Y G Y G Y | Y R Y R Y R | R B R B R B | (g)---------------(y)---------------(r)---------------(b) | Y R Y R Y R | | G B G B G B | | | | Y R Y R Y R | | G B G B G B | | | | Y R Y R Y R | | G B G B G B | (g)---------------(b) | G B G B G B | | R Y R Y R Y | | | | G B G B G B | | R Y R Y R Y | | | | G B G B G B | | R Y R Y R Y | (r)---------------(y) To understand the importance of the Tartan, there are several points to consider: 1. By reading off the four colors of a plaid in clockwise order, starting at an arbitrary point, we obtain four permutations of the four colors. Quadruples read from different faces are disjoint, so all 24 permutations of the four colors appear on the Tartan, once each. 2. Every motion in the group C of whole-cube rotations is a permutation of the pairs of antipodal corners, and so corresponds to a recoloring of the Tartan. Some restriction of this sort is necessary to prevent us from simply drawing a different black-and-white picture on each facelet and calling that a two-coloring. 3. Point 2 implies that C is isomorphic to a subgroup of S4, the group of permutations on the four colors. But both C and S4 have 24 elements, so C is isomorphic to S4 itself (a fact well-known to crystallographers). 4. Since every color permutation is realizable by a whole-cube move, there is only one Tartan (up to whole-cube moves). This is why we use colors as labels, rather than some FLUBRDoid positional scheme. [The actual choice of colors and the name ``Tartan'' arise from the DoD Ironman project.] 5. Every reflection of the Tartan is color-equivalent to a rotation. In particular, the identity is color-equivalent to a reflection through the center of the cube. If you were to lend your Tartan to someone who ran it through a looking-glass, you could not discover the fact except by removing the face-center caps and examining the screw threads! We have constructed a Tartan from a Rubik's cube and colored tape. Due to the similar appearance of the plaids, it takes us several times as long to solve the Tartan as it takes to solve Rubik's cube. Our search for pretty patterns has not been particularly rewarding. Part of the reason seems to be that the cube's appearance is strongly constrained by the Tartan's coloring. On Rubik's cube one may make a particular face pattern (e.g. orange T on white background) using any of several identically colored facelets. On the Tartan, however, the plaid on any facelet of a cubie, together with the orientation of the plaid relative to the cubie, determines the plaid and orientation of the other facelet(s) of the cubie. The one nice pattern we have is in fact the conceptual precursor to the Tartan. It is Pons Asinorum (FFBBUUDDLLRR) applied to the position shown in the diagram above. In this position, the plaids of adjacent facelets line up with each other to display the same arrangement of plaids, magnified by a factor of two. Each face looks like the following, for some assignment of colors to the numbers 1 through 4: (1)---------------(2) | 1 2 2 1 1 2 | | 4 3 3 4 4 3 | | | | 4 3 3 4 4 3 | | 1 2 2 1 1 2 | | | | 1 2 2 1 1 2 | | 4 3 3 4 4 3 | (4)---------------(3) --- Date: Sun, 22 Mar 81 08:29:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: No short relations and a new local maximum Well, the gigabyte (well, 300Mb) came in, and brute force is having its day. I have a little program that generates all positions accessible from a given position in a given number of quarter-twists. With the increased storage available here, I was able to run it to five quarter-twists. The first important fact to emerge is that there are exactly 105046 different positions at a distance of at most 5 qtw from START. This has two consequences to the argument given in my message on the Supergroup, part 2 (9 January 1981 0629-EST). Note that the results here pertain to the usual group of the cube, rather than the Supergroup, since the program does not keep track of face-center orientations. The first consequence is that there are exactly 93840 positions exactly 5 qtw from START. The message cited above proved the inequality P[5] <= 93840; this is now known to be an equality. The second consequence is that there are no relations (sequences that lead back to START) of length 10, with the exception of those that follow from the relations FFFF = FBF'B' = I (and their M-conjugates). This is because relations of length 10 would reduce P[5], which is not the case. There are, however, relations of length 12; the only known ones are FR'F'R UF'U'F RU'R'U [given in Singmaster] and its M-conjugates. These results can be extended to the Supergroup, by noting that the set of observed positions places a lower bound on the number of Supergroup positions at a distance of 5 qtw, while the upper bound given in the cited message relies on the relations FFFF = FBF'B' = I, which are relations in the Supergroup. A particular result which may be of greater interest to readers of this list concerns the relation between symmetry and local maxima. In our message on the subject (14 December 1980 1916-EST) Jim Saxe and I mentioned that the six-spot pattern is not a local maximum, as verified by computer. [The same program was used, but only four-qtw searches were needed.] With five-qtw searches, it became possible to check another conjecture, using an approach that Jim suggested. The four-spot pattern U U U U U U U U U R R R B B B L L L F F F R L R B F B L R L F B F R R R B B B L L L F F F D D D D D D D D D is solvable in twelve qtw, either by (FFBB)(UD')(LLRR)(UD') or by its inverse, (DU')(LLRR)(DU')(FFBB). It is immediate that a twelve qtw path from this pattern to START can begin with a twist of any face in either direction. The program was used to verify that there are no ten qtw paths. (It generated the set of positions attainable at most five qtw from START and the set of positions obtainable from the four-spot in at most five qtw, and verified that the intersection of the two sets is empty.) Thus the four-spot is exactly twelve qtw from START and all its neighbors are exactly eleven qtw from START, proving that the four-spot is a local maximum. (Worried that there might be an eleven qtw solution to the four-spot? Send me a note.) This is the first example of a local maximum which cannot be shown to be a local maximum on the basis of its symmetry. To be more precise, let us define a "Q-symmetric" position to be a position whose symmetry group is Q-transitive. This extends the terminology developed in "Symmetry and Local Maxima". In that message, we showed that all Q-symmetric positions, except the identity, are local maxima. Until now, these were the only local maxima known. The four-spot, however, is not Q-symmetric; the position obtained by twisting the U or D face of the four-spot is not M-conjugate to the position obtained by twisting any of the other faces. This lays to rest the old speculation that one might find all local maxima, and thereby bound the maximum distance from START, by examining Q-symmetric positions. --- Date: Mon, 18 May 81 10:46:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Drum info Most of this note is pretty straightforward application of the known cube properties, but if you want to know about the drum.... The drum shows everything you see on a regular cube except the orientation of the four truncated edges, or wedges. Because the (invisible) edge parity is preserved, each visible position of the drum corresponds to 2^4/2 cube positions. Thus there are 5.406x10^18 drum positions. To count the number of solutions, note that as in the normal cube, the face centers force each edge to its home position and orientation. In addition, each corner has a facelet that says whether it is top or bottom and fixes the corner's orientation. This means that solved positions are obtained from each other by permuting top corners, bottom corners, and wedges. But the three cubies on a diagonal face must match, and so the three permutations are the same. Only even permutations are achievable in this way (since the cube of an odd permutation is odd) and there are 4!/2=12 of these. One easy process that goes from one solved position to another is FF RR FF BB RR BB. I asked Ole Jacobsen what he meant when he said of the wedges that "as you will discover when using your edge moves: the orientation matters." It turns out this is because he solves by layers: top-middle-bottom, and doesn't know which way to orient the edges in the middle so that the edges on the bottom will have the right parity. There are several ways out of that problem; one is to turn the drum sideways and solve left-middle-right. The problem of solving without knowing the order of the wedges is trickier. Solving sideways is one method: do the left side any way; on the right side there two possibilities, one of which will work. (This is Bernie Greenberg's suggestion, modified so you don't need to memorize the whole map.) One interesting thing to do with a drum is to turn it into baseball. Using colored tape and disassembly, change the colors and positions so that the wedges appear in the UF, DF, BL, and BR positions when the colors match. On a baseball, there are only two solved positions. --- Date: Thu, 11 Jun 81 03:23:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Re: edge "flip" anyone... Does anyone know of a way to flip two edges without changing anything else, ie interchange the FR and FB edges, keeping their same orientation. The term "flip" generally means "change orientation" (of an edge). I take it you mean "exchange" (or, acceptably, "interchange"). This is provably not possible, because an exchange is an odd permutation. I will send you the two messages which deal with what can be done with a cube. (Anyone else who wants a copy, request of Hoey@CMU-10A rather than the list.) If you don't know what an even (or odd) permutation is, or how it acts, any elementary algebra text should help. If you try and fail, drop me a line and I'll try to help. If not, how about one that will interchange FR and FB edges without disturbing the top layer, but can mess up the bottom?? There is no FB edge. I'd guess you mean UR and UB, for which RU'R' UUFFBB DDFFBB RUR' suffices. --- Date: 7 July 1981 0643-EDT (Tuesday) From: Dan Hoey at CMU-10A To: SF-LOVERS Subject: The Steel of Raithskar It is my pleasure to mention a new title to the readers of this list. @i(The Steel of Raithskar) by Randall Garrett and Vicki Ann Heydron is the first of a (planned?) trilogy named the @i(Gandalara Cycle). Mr. Garrett is well known for his tight plotting, carefully constructed fantasy, and engrossing mystery to readers of the Lord D'Arcy series. At the risk of nit-picking, I fault that series only on the basis of its dry, academic tenor, and a slight tendency to concentrate on actions over people. And at the risk of excessive romanticism, I attribute the warmth, emotion, and excellent characterization of the current work to collaboration with Ms. Heydron, his wife. At no risk, I highly recommend this novel. I would draw the parallels to the best of Asimov, Brackett, Bradley, Cherryh, Crowley, Herbert, McCaffrey, and Tolkien, but when a book is this full of surprises, it's a sin to tell. I did run across one jarring note, for which I seek clarification. Midway through (and no spoiler) we find the following narrative. A huge chrome-nickel-iron meteor had come smashing in through the atmosphere in the distant past at somewhere between ten and twenty miles per second. At those velocities, plenty of hard radiation is given off during the time it takes to go through the atmosphere--between ten seconds and two minutes, depending on the speed and the angle at which it struck. That radiation would be lethal to those creatures near enough to barely survive the impact, and disabling to those who caught a smaller dose.... Meteors have been blamed for many things, including physical heating of the biosphere, the greenhouse effect, and heavy-metal poisoning. There was an overlong discussion of these effects and their relation to dinosaur extinction either here or on Human-Nets; I'd just as soon see that discussion follow the dinosaurs into extinction. But hard radiation? This sounds like the sort of arrant pseudoscientific gibberish that infests so much of modern fantasy . [It could be explained away as narration by an uninformed character, but that would be reaching.] So I ask for the experts' opinions. If anyone can support the described emission of radiation by a high-velocity meteor, please send a note to Hoey@CMU-10A, and I'll collect and report. --- Date: 11 July 1981 1800-EDT (Saturday) From: Dan Hoey at CMU-10A To: SF-LOVERS Subject: Poor taste Bambino's Restaurant Breakfess Menu Baken - Blindseys - Hominy Fritz - Ingalish Muffin Mabel syrup - Marmalada - Oatmel - Spam - Waphils Lunjohn Menu Angeladas - Beef Stu - Billogna - Burritas - Chicken Alec king Grhilda cheese - Kippered Harryng - Kitney pie - Salamy - Samburger Horace d'oeuvres Annetipasto - Gazpajoe - Jeff salad - Meg rolls Oysters on the half Shelly - Patty de foie gras Salad Barb Brocollie - Cellery - Heda lettuce - Kellyflower Pickled Beats - Waltercress Garnieshes Margeryne - Marshamellow - Maryschino cherries - Sour cream and Clives Sueps Clem chowder - Myrtle soup - Tomaeto soup - Won Tom soup Entrays Arroz con Paula - Biff Bourguignon - Bobster - Calve's Brians Chetlins - Chicken Gordon bleu - Chop Susy - Coq au Van - Filet of Sol Frank steak - Lesagna - Lynneguini - Mackaroni - Mannycotti Neil Cutlets - Peteza - Roast Burkey - Sallysbury steak Smoked Solomon - Standing Rob roast - Steak Florentina Turkey Devaughnshire - Veal Parmesean Sid Orders Artichuck hearts - Chopped Oliviar - Franch fries Owenion rings - Provolonny - Whole-wheat Brad Vegetabels Black-Ida peas - Karen on the cob - Kayle - Rudybaga Russell sprouts - Scalleons - Zackini Libashawns Bass Head Dale - Cyder - Drambowie - Lymanade - Miltshake Orange Joyce - Perryer water - Sloe Jean fizz Deeserts Apple Chrisp - Bucklava - Carriemel apples - Cherries Jubilly Chocolate covered Lance - Cupkates - Dave-nut bread - Fawndue Gerry pie - Jillo - Napauleon pastry - Parfay - Peaches and Corinne Sherbert - Spumona - Strawbarry shortcake - Watermellen - Yogert --- Date: Sun, 12 Jul 81 13:43:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Happy birthday \ /\ / / \ \ \I\ I/ ### ### ### ### ### --------------------------###------- | -- -- ### -- | ---------------------###------------- | | -- -- ### -- -- | | ------------------------------------- | | | -- -- -- -- | -- | | ------------------------------------- | -- | | | | | | | -- | | H a p p y B i r t h d a y | | | -- | | | | | | | -- | | | | | -- | | |-----------+-----------+-----------| | -- | | | C U B E | | | | -- | | | | | | | -- | | | | - | | -- | |L O V E R S| | -- | | |-----------+-----------+-----------| -- | | | | | -- | | O n e Y e a r | -- | | | | -- | 342 messages -- 73000 words | ------------------------------------- --- Date: Mon, 20 Jul 81 23:32:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Re: One stuck axle Singmaster gives the answer. Let A = RL'FFBBRL', then AUA = D. Thus it is possible to dispense with D moves entirely. Jim Saxe also has a solution, but I don't know if it's the same one. --- Date: Tue, 21 Jul 81 23:50:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: The ten stuck-axle subgroups 1. No faces stuck. The familiar cube group. 2. D face stuck. As previously noted, all positions can be reached. In addition, all Supergroup positions that fix the orientation of the D face center are achievable. 3. B and D faces stuck. All Supergroup positions that fix the BD edge and the B and D face centers are achievable. 4. U and D faces stuck. Edges cannot be flipped. If we define edge orientation by marking the F and B facelets of the F and B edges, and the U and D facelets of the others [cf Jim Saxe's message of 3 September 1980], then all Supergroup positions that fix the orientation of all edges and the U and D face centers are achievable. 5. L, B, and D faces stuck. All Supergroup positions that fix the BLD corner, the LB, BD, and DL edges, and the L, B, and D face centers are achievable. 6. U, B, and D faces stuck. Again, edges cannot be flipped. All Supergroup positions that fix the orientation of all edges, the position of the UB and BD edges, and the orientation of the U, B, and D face centers are achievable. 7. U, L, B, and D faces stuck. Singmaster has a very nice description of this group [indexed as Group, Two Generators]. The group of achievable permutations of the six movable corners is isomorphic to the group of all permutations on five letters. All Supergroup positions that permute the corners in an achievable permutation, fix edge orientation, and fix the unmovable two corners, five edges, and four face centers are achievable. 8. U, L, D, and R faces stuck. Sixteen positions 9. U, L, D, B, and R faces stuck. Four positions. 10. All faces stuck. One position. --- Date: Fri, 24 Jul 81 22:20:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: A new problem Suppose you buy a new cube and the arrangement of the colors is different from your old cube. Naturally, you want the new one to be like the old, so you decide to switch the colortabs around. A. What is the smallest number of faces you have to recolor? B. What is the smallest number of colortabs you have to move? Note the hidden variable: the permutation of the new cube with respect to the old one. This variable has thirty values, including the identity. There are two kinds of answers I am interested in. 1. A minimax value -- a recoloring algorithm and a proof of its optimality. 2. A probability distribution of optimal recolorings. Any takers? --- Date: Fri, 31 Jul 81 06:26:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Re: Supergroup Don Woods's answer is correct. When the edges and corners are in their solved positions, the total face center twist is zero modulo 180 degrees. Thus the number of face centers that are twisted 90 degrees must be even. A proof of this appeared in Cube-Lovers last year. A process to twist the U face center 180 degrees without changing anything else is (U LR UU L'R')^2. This process comes from Singmaster's book. I sent Cube-Lovers a general procedure for solving the supergroup in January. If you want a copy of either of these messages, send a note to Hoey@CMU-10A. --- Date: Fri, 14 Aug 81 01:11:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Results of an exhaustive search to six quarter-twists The first answer is that there are exactly 878,880 cube positions at a distance of 6 quarter-twists from solved, and so 983,926 positions at 6qtw or less. These figures reflect a decrease of 744 from the previously known upper bounds. It turns out that the twelve-qtw identities reported by Chris C. Worrell are complete, in a sense. The only reservation here is that a fifth rule must be added to his list of the ways in which ``a generator generates other identities.'' This rule is substitution with shorter identities, and it's not too surprising that it was left out, since the only shorter identities are the ``trivial'' ones like XXXX=XYX'Y'=I, where X and Y are opposite faces. In the case of the twelve-qtw identities, this means that identities of the form aXXb and aX'X'b generate each other. The structure of the 12-qtw identities is clearer if we write them in a transformed way: I12-1 FR' F'R UF' U'F RU' R'U I12-2 FR' F'R UF' F'L FL' U'F I12-3 FR' F'R UF' UL' U'L FU' The fifth rule is necessary so that I12-2 may generate the identities I12-2a FR' F'R UF FL FL' U'F and I12-2b F'R' F'R UF FL FL' U'F'. To see that this rule is necessary, it need only be observed that inversion, rotation, reflection, and shifting all preserve the number of clockwise/counterclockwise sign changes between cyclically adjacent elements. In what sense are the ``trivial'' identities trivial? I have come to believe that they are trivial only because they are short and simple enough that they are well-understood. The only identities for which I can find any theoretical reasons for calling trivial are the identities of the form XX'=I. In spite of the simplicity of the ``trivial'' identities, their occurrence is one of the major reasons that Alan Bawden and I were unable to show earlier that I12-1-3 generated all identities of length 12. I fear that the combination of 4-qtw and 12-qtw identities may turn out to be a major headache when dealing with identities of length 14 and 16. --- Date: Wed, 16 Sep 81 00:03:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Re: lower bounds Hi. I'm really pressed for time, but I'll drop a couple of comments. Alan pretty well said it--there are half-twisters and there are quarter-twisters and the included message is one of the former. I strongly favor the latter, since then all the moves are equivalent, (M-conjugate, to you archive-readers). But Singmaster's book, though in the other camp, is too good to ignore. To extend the argument I gave on 9 January to the case where quarter-twists and half-twists are counted equally (we call such a move a `htw' whether it is quarter or half) let PH[n] be the number of (3x3x3-cube) positions at exactly n htw from SOLVED. Then PH[0] = 1 PH[1] <= 6*3*PH[0] PH[2] <= 6*2*PH[1] + 9*3*PH[0] PH[n] <= 6*2*PH[n-1] + 9*2*PH[n-2] for n > 2. Solving yields the following upper bounds: htw new total htw new total 0 1 1 10 2.447*10^11 2.646*10^11 1 18 19 11 3.267*10^12 3.531*10^12 2 243 262 12 4.360*10^13 4.713*10^13 3 3240 3502 13 5.820*10^14 6.292*10^14 4 43254 46756 14 7.769*10^15 8.398*10^15 5 577368 624124 15 1.037*10^17 1.121*10^17 6 7706988 8331112 16 1.385*10^18 1.497*10^18 7 102876480 111207592 17 1.848*10^19 1.998*10^19 8 1373243544 1484451136 18 2.467*10^20 2.667*10^20 9 18330699168 19815150304 At least 18 htw are required to reach all the 4.325*10^19 positions of the cube. This is the same argument that was used in Singmaster's fifth edition, p. 34, and is the best I know. Lest ye be tempted to pull the trick I did in the January message, remember that half-twists are even permutations, so there is no assurance that half the positions are an odd distance from SOLVED. This is illustrated in the 2x2x2 case, where more than half of the positions are at a particular odd distance. And yes, all of Thistlethwaite's analysis seems to use the half-twist metric. I am quite surprised, however, to hear the rumor of 41 htw. As of Singmaster's fifth edition, the figure was 52 htw ``... but he hopes to get it down to 50 with a bit more computing and he believes it may be reducible to 45 with a lot of searching.'' If anyone has harder information on the situation, I would like to hear it. Well, back to real work. I saw a Rubikized tetrahedron in a shop window earlier this evening; I'm not sure whether I'm relieved or infuriated that the store was closed for the day. --- Date: Wed, 23 Sep 81 22:36:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Re: question for cube-lovers (S and T patterns) It is impossible to put Z patterns on all six faces of the cube, just as it is impossible to extend the Laughter (or Zig-Zag) pattern to six faces. The problem is with the corners. If every face is to have a pair of opposite corners that agree with the face center and a pair of opposite corners that agree with each other but not with the center, then the only constructible pattern is like (i.e. M-conjugate to) the following: F - U - U - U - F D - L F - R U - R B - L - L - - F - - R - - B - L - D R - F R - U L - B B - D - D - D - B But this pattern has incorrect corner orientation, and so is not achievable. The T patterns were introduced to this list by David C. Plummer [3 September 1980 2123-EDT], who assigns credit to Tanya Sienko for the idea. Jim Saxe and I [27 January 1981 0102-EST] gave a process for Tanya's T, the pattern that Minh Tai uses to sign with. Our process, (FF UU)^3 (UU LR')^2, is four quarter-twists shorter than Tai's ``quick routine'' because of the cancellation in the middle. The other T pattern, Plummer's T, can be achieved in 28 qtw: FF UD' F'B' RR F'B U'D RL FF RL' UD' RL FF R'L U'D'. --- Date: Mon, 07 Dec 81 19:11:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Brute Force Report: The fourteen-qtw identities Several messages in August of this year [mail to Hoey@CMU-10A for copies] concerned short identities of the cube, i.e. processes which return the cube to solved. Later in that month I assisted David Plummer in a brute force attack on the problem. We had plans to investigate all the positions up to eight qtw, but unfortunately became busy on other projects. I have finally come up with enough time to analyze and report the data from the seven-qtw search. There are 8,221,632 cube positions at a distance of seven quarter- twists from solved, and 9,205,558 positions at seven or fewer qtw. By recording cases of different seven-qtw processes yielding the same position, a complete list of fourteen-qtw identities is obtained. The task is then to reduce the list to exclude multiple instances of equivalent identities. We call two identities equivalent when one can be obtained from the other by some combination of the following operations: - uniformly relabeling the twists according to a rotation or reflection of the cube, - cyclically permuting the twists, - reversing the order of the twists and inverting each one, and - substituting a sequence x for a sequence y, where xy' is a shorter identity. The first three criteria are easily implemented on a computer. The fourth can be performed for the shortest identities, those equivalent to F^4 and FBF'B', but I know of no algorithm to detect all cases of equivalence due to substitution of the longer identities. My strategy was to reduce the (several thousand) identities by computer for the simple kinds of equivalence, and then to look by hand for substitution equivalence between the fourteen identities then remaining. I found three equivalences, listed at the end of this note, but the possibility remains that some of the following identities are equivalent. The list is, however, complete (modulo bugs and cosmic rays). Identities equivalent to the first six on this list were independently discovered by Chris C. Worrell; I follow his numbering for them. Identities I14-5 through I14-7 do not hold in the Supergroup, because they twist face centers as noted in the brackets. I14-1 BF' UB'U'F UL' BU'B'U LU' I14-2 B UBL' B'D'BD LB'U' L'B'L I14-3 BB U BB UD' RR U' RR U'D I14-4 BUB'U' L'FL UBU'B' L'F'L I14-5 (BB UD B U'D')^2 [Supergroup BB] I14-6 BF' U B'F LR' UD' F' U'D L'R [Supergroup UF'] I14-7 BF U B'F' LR' UD F' U'D' L'R [Supergroup UF'] I14-8 BF' UFRU'R'B'U'B'RBUR' I14-9 BF' UFRU'B' UD' F'U'R'FD I14-10 (BUBU'L'B') R (BLUB'U'B') R' I14-11 (BUBU'L'B') D'R'B' DLD'RD The twelve-qtw identity I12-2 = (BUBU'L'B') (B'D'B'DLB) can be substituted into identities I14-10 and I14-11 to yield: I14-10a (B'L'D'BDB) R (BLUB'U'B') R' I14-10b (BUBU'L'B') R (B'D'B'DLB) R' I14-10c (B'L'D'BDB) R (B'D'B'DLB) R' I14-11a (B'L'D'BDB) D'R'B' DLD'RD Identity I14-10c can be obtained from I14-10 [by shifting seven places and reflecting the cube through the UD plane] but I14-10, I14-10a, and I14-10b are mutually inequivalent when twelve-qtw identities are ignored. The same holds for I14-11 and I14-11a. Strangely enough, I14-11a can also be transformed to I14-11 by substituting with the identity (BDBD'R'B') (B'U'B'URB), which is equivalent to I12-2. ---