Date: Thu, 22 Apr 82 17:03:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Cubebot Caption from a photograph said to be from the Washington Post, April 13, 1982: University of Illinois engineering student Daniel Talken adjusts the mechanical hands of a robot built by students at the school in Urbana to solve the Rubik's Cube puzzle. The robot's computer brain can work out the solution in two-tenths of a second, but it takes the hands about 12 minutes to make average 110 moves to solve the puzzle. The photo shows a guy diddling a complicated machine in which an unsolved cube is visible. Eyes are painted on the front of the machine's support above a bulge that may be functional as well as vaguely resembling a nose. No camera equipment is apparent; presumably they tell the machine how the cube is scrambled, or cheat and have the machine itself scramble the cube. --- Date: Tue, 01 Jun 82 22:20:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Lower bounds for the 4x4x4 Well, since you insist, here are my lower bounds for the 4^3. For the "colored" 4^3, where only the color pattern matters, some positions require at least 41 qtw to solve. For the "marked" 4^3, where center facets of the same color are distinguished so as to force a unique home position for each, some positions require at least 48 qtw. The proof is in MC:ALAN;CUBE4 LB and is about 5K characters long. A qtw of the 4^3 is either a quarter-twist of a face relative to the rest, or a quarter-twist of half of the puzzle relative to the other half. Note that this makes a slice twist into two moves. I like this metric because it is consistent with our conventions for the 3^3. One of these days I'll explain why I like those conventions. --- Date: Tue, 01 Jun 82 22:22:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Lower bounds for the 4x4x4 (Long) Lower bounds for solving the 4^3 puzzle In order to prevent counting positions which arise from whole-cube moves, I do not move the DLB corner. So the generators I use are U1 U1' R1 R1' F1 F1' U2 U2' R2 R2' F2 F2' U3 U3' R3 R3' F3 F3' where the digit indicates how many layers are being moved and the prime indicates a counterclockwise quarter-twist. Let us break up any process into "syllables", where a syllable is a maximal nonempty string of generators with the same letter. Note that the order of the generators within a syllable is irrelevant. We may make a syllable canonical by simplifying so that 1. A generator and its inverse do not both appear, 2. Clockwise generators appear at most twice, 3. Counterclockwise generators appear at most once, and 4. Generators appear in numerical order. For each letter there are 63 canonical syllables. Omitting the letter, they are: 1,1',2,2',3,3' Six of length one 11,12,12',13,13',1'2,1'2',1'3,1'3',22, 23,23',2'3,2'3',33 Fifteen of length two 112,112',113,113',122,123,123',12'3, 12'3',133,1'22,1'23,1'23',1'2'3,1'2'3', 1'33,223,223',233,2'33 Twenty of length three 1122,1123,1123',112'3,112'3',1133,1223, 1223',1233,12'33,1'223,1'223',1'233, 1'2'33,2233 Fifteen of length four 11223,11223',11233,112'33,12233,1'2233 Six of length five 112233 One of length six (Exercise for the reader: There is a reason these are binomial coefficients. Why did we skip a row?) The number of canonical syllable strings containing N generators is P(-N) = 0 if -N < 0, P(0) = 1, P(N) = 6 C(N-1) P(N-1) + 15 C(N-2) P(N-2) + 20 C(N-3) P(N-3) + 15 C(N-4) P(N-4) + 6 C(N-5) P(N-5) + C(N-6) P(N-6) if N > 0, where C(N) is the number of ways of choosing a new letter after N generators: C(-N) = 0 if -N < 0, C(0) = 3, C(N) = 2 if N > 0. Evaluating this recurrence yields P( 0)= 1 P(13)<1.338E15 P(26)<1.404E30 P(39)<1.472E45 P( 1)= 18 P(14)<1.914E16 P(27)<2.007E31 P(40)<2.105E46 P( 2)= 261 P(15)<2.737E17 P(28)<2.871E32 P(41)<3.011E47 P( 3)= 3732 P(16)<3.915E18 P(29)<4.106E33 P(42)<4.307E48 P( 4)= 53379 P(17)<5.599E19 P(30)<5.873E34 P(43)<6.160E49 P( 5)= 763506 P(18)<8.009E20 P(31)<8.400E35 P(44)<8.811E50 P( 6)=10920771 P(19)<1.146E22 P(32)<1.202E37 P(45)<1.261E52 P( 7)<1.563E 8 P(20)<1.639E23 P(33)<1.719E38 P(46)<1.803E53 P( 8)<2.235E 9 P(21)<2.344E24 P(34)<2.459E39 P(47)<2.579E54 P( 9)<3.196E10 P(22)<3.353E25 P(35)<3.516E40 P(48)<3.688E55 P(10)<4.572E11 P(23)<4.795E26 P(36)<5.029E41 P(49)<5.275E56 P(11)<6.539E12 P(24)<6.858E27 P(37)<7.194E42 P(50)<7.545E57 P(12)<9.352E13 P(25)<9.810E28 P(38)<1.029E44 P(51)<1.080E59 The number of positions exactly N qtw from SOLVED is at most P(N), so the number of positions within N qtw of SOLVED is at most P(0)+P(1)+...+P(N). Since there are 7.07E53 marked and 7.40E45 colored positions, this would give us lower bounds of 40 qtw for the marked cube and 47 qtw for the colored cube. But we can improve these lower bounds by one each, using the parity hack I described some time ago. Every qtw is an odd permutation of the corner cubies, so the number of positions with even corner permutations within 2N+1 qtw of SOLVED is at most P(0)+P(2)+...+P(2N) and the number of positions with odd corner permutations within 2N+2 qtw of solved is at most P(1)+P(3)+...+P(2N+1). There are 3.70E45 colored positions with odd corner permutations, and fewer than 1.583E45 odd-length canonical processes with length at most 39. So some odd colored positions require at least 41 qtw to solve. There are 3.53E53 marked positions with even corner permutations, and fewer than 1.939E53 even-length canonical processes with length at most 46. So some even marked positions require at least 48 qtw to solve. Directions for future hacks Note that we could also distinguish between positions with even or odd edge permutations. The recurrence gets hairier, but my analysis of that problem indicates that the numbers get very close very quick, so no luck. We could divide the positions into buckets based on other quotients of the group. For instance, count the number of positions with each of the 729 possible corner orientations. This should be feasible, but probably no help for the 4^3 puzzle. For the 3^3, where there are 2187 corner buckets, some of which stay empty for a fair number of moves (I seem to recall 8), and our current lower bound is small, I think there is a chance of improvement. Any God's numerologist willing to hack the good hack? --- Date: Tue, 15 Jun 82 10:45:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Patterns for Rubik's Revenge CHECKERBOARDS I confirm Dave Plummer's result that it is impossible to make a checkerboard on all faces of a cube of even side. Proving this for the 2^3 is sufficient, and implies the corollary I sent last year that it is impossible to make S or Z or Zig-Zag patterns on all sides of the 3^3. This time I will outline my analysis of the problem. What we are asking for in each case is a pattern in which every face has matching diagonally opposite corner facets and contrasting adjacent corner facets. First, consider any position in which diagonally opposite corner facets match on each face. If we connect every pair of corner cubies that have diagonally opposite corner facets we get two tetrahedrons of corner cubies. A quick examination will show that the four cubies in such a tetrahedron must either be 1) Not all from the same cube, 2) Four copies of the same cubie, or 3) Four different cubies from the same cube, in the correct position and orientation relative to each other. Assuming case 3, we may place one tetrahedron in the home position and consider how the other tetrahedron has been rigidly rotated with respect to the first. There are 12 rotations of the tetrahedron. One is the identity, three are 180-degree rotations about the midpoints of two opposite edges, and six are 120-degree rotations about a vertex. In the identity every face's adjacent corner facets fail to contrast. The 180-degree rotations have the corners like the 3^3 Zig-zag pattern, where two faces have noncontrasting corners. The 120-degree rotations would make checkerboards, but violate the corner twist invariant. Approximate checkerboards can be made from the 180-degree rotation and from the 120-degree rotation with one corner twisted. In the 180-degree approximation, two faces have two wrong facets each. In the 120-degree approximation, three faces have one wrong facet each. Both are achievable with the 2^3 and 4^3, and I think these are as close as you can get on any even-sided cube. SPOTS Spot patterns of the 4^3 are those which have the pattern X X X X X Y Y X X Y Y X X X X X on all nonblank faces. There are a lot of them: every permutation of the centers is possible. There are thus 6! = 720 spot patterns. We may cut this number down by identifying positions that are M-conjugates (recolorings) of each other. As long as I am listing the permutations by conjugacy class, I may as well break them down by recoloring type. Last July I asked a question about the possible rearrangements of colors on the cube. I worked on the solution long enough to find that given a ``standard'' cube, there are five kinds of recoloring up to M-conjugacy. Identity -- The standard coloring. Reflection -- Identity in a mirror. Swap -- Identity with two adjacent colors exchanged. Wrench -- Identity with three adjacent colors cycled. Befuddler -- Wrench in a mirror. The Identity and Reflection are unique colorings. There are twelve Swaps and eight each of the Wrench and Befuddler recolorings. Each recoloring corresponds to 24 face permutations, achievable by whole-cube moves. Here, then, are the spot patterns. Columns correspond to the number of spots in the pattern. The row groupings show the kind of cube coloring the spot pattern comes from. The patterns are given as a permutation of faces: (...XY...) and (Y...X) both mean that face X has a spot colored Y, as shown at the beginning of this message. The number of permutations in each conjugacy class is also given. Number of spots 0 2 3 4 5 6 Coloring -------------------------------------------------------------------- Identity :8 (BUFD):6 (BUL)(FDR):8 (BF)(UD):3 (BF)(UL)(DR):6 -------------------------------------------------------------------- Reflection (BF):3 (BU)(FD):6 (BULFDR):8 (BF)(ULDR):6 (BF)(UD)(LR):1 -------------------------------------------------------------------- Swap (BU):12 (BFU):24 (BFUD):12 (BUFDL):48 (BFULDR):48 (BF)(UL):12 (BF)(UDL):24 (BF)(UDLR):12 (BU)(FDL):48 (BU)(FDLR):48 -------------------------------------------------------------------- Wrench (BUL):16 (BUFL):24 (BFUDL):48 (BFULRD):24 (BU)(FLR):48 (BUL)(FRD):8 (BU)(FLDR):24 -------------------------------------------------------------------- Befuddler (BFUL):48 (BFULD):48 (BFUDLR):16 (BU)(FL):24 (BUFLDR):24 (BFU)(DLR):24 (BU)(FL)(DR):8 -------------------------------------------------------------------- The answer: Fifteen six-spot patterns, six five-spots, eight four-spots, two three-spots, two two-spots, and one no-spot. CROSSES What cross patterns are possible on the 4^3? We must first ask what a cross pattern on the 4^3 should look like. I consider the following two kinds of cross. Thick Cross Thin Cross X O O X X O X X O O O O O O O O O O O O X O X X X O O X X O X X Every thick cross pattern is a rigid rotation or reflection of the edge and face center pieces with respect to the corners. This is just like the 3^3 case except that the 3^3 has face centers that are fixed relative to each other, and so does not allow reflec- tions. So in addition to the thick versions of Plummer's Cross and Cristman's Cross, there are three new crosses. Thick Pons Cross Thick Fliptwist Cross Thick Interlaced Cross U D D U U L L U D D D D B U U B L L L L D D D D U U U U L L L L U D D U U U U U U L L U B U U B L R R L F B B F R L L R L D D L F B B F R U U R R R R R B B B B L L L L U L L U D D D D B B B B U U U U R R R R B B B B L L L L L L L L D D D D B B B B U U U U L R R L F B B F R L L R L L L L L D D L F B B F R U U R U L L U D U U D D R R D U U U U L F F L F D D F R B B R R R R R U U U U F F F F D D D D B B B B R R R R D U U D F F F F D D D D B B B B D R R D L F F L F D D F R B B R B F F B B F F B F F F F D R R D F F F F F F F F R R R R F F F F B F F B R R R R B F F B D R R D For thin crosses, we first examine those in which the arms of the crosses meet at the edges. Again the figure facets are rigidly rotated and reflected with respect to the ground. This time cubie conservation becomes an issue, because of the impossibility of flipping an edge cubie, so there are only three such thin crosses. Thin Pons Cross Thin Plummer Cross Thin Interlaced Cross U U D U U U R U U U D U B B U B U U R U D D D D B B U B R R R R U U D U U U U U U U R U B B U B L L R L F F B F R L R R L L B L F F U F R F R R R R R R B B B B L L L L U U L U B B B B U U U U F F F F L L R L F F B F R L R R U U L U L L B L F F U F R F R R L L R L F F B F R L R R L L L L L L B L F F U F R F R R U U L U D D U D D D L D U U U U L L F L F F D F R B R R L L L L D D U D F F F F D D D D B B B B D D L D D D U D L L F L F F D F R B R R D D L D L L F L F F D F R B R R B B F B B B D B B B F B D D R D B B D B F F F F R R R R D D D D B B F B D D R D B B D B D D R D When we relax the constraint that thin cross arms must meet at the edges, the figure is no longer rigidly transformed with respect to the ground. Indeed, we might expect that adjacent crosses whose arms do not meet might have colors that are opposite on the cube. I carried out a long examination of the cases, and found that this does not happen. In fact, only one new color permutation arises. >Thin Fliptwist Cross U U B U B B B B U U B U U U B U L R L L F F U F R L R R B D B B L R L L F F U F L L L L B D B B R R R R U U U U R L R R D D D D L R L L F F U F R L R R B D B B D D F D D D F D F F F F D D F D The only other thin cross patterns in which not all crosses meet at the edges are 43 versions of the Thin Pons Cross (modulo my missing a case or two in the analysis). --- Date: Fri, 25 Jun 82 12:25:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: New Scientific American article Date: 6 August 1980 16:52 edt From: Greenberg.Multics at MIT-Multics Subject: Re: 'cube lovers digest' I am really interested in when the _ Gardner is going to get his act together and publish THE cubing article-- each month for the last n I have eagerly taken the cover of SciAm and been disappointed. This is clearly THE mathematical game (since the inception of SciAm, with the possible exception of Conway's LIFE), and I wonder what he's waiting for. About a week ago, I actually dreamt that I opened the SciAm wrapper and found the Cube on the cover, introducing a WHOLE ISSUE about it (Social implications, Ancient Cubing, Cubing in the Soviet Union, etc...) Well, there finally was a Metamagical Themas column on the cube in March '81. Unfortunately, that article was mostly old hat to the readers of Cube-Lovers. The July '82 issue, just out, is a different story. Hofstadter discusses about twenty different ``Cube'' puzzles, based on all the regular polyhedra (and the tesseract), several arrangements of twist axes and several coloring schemes. It even mentions cubing in the Soviet Union! Stan Isaacs is the Cube-Lovers representative for the new article. At last I can believe that Hofstadter's column will replace Gardner's. --- Date: Mon, 09 Aug 82 07:37:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Invisible Revenge When you have seen Rubik's Revenge, have you seen everything? Maybe not. Supergroups There is some confusion about the meaning of the term Supergroup for the larger cubes. There are two issues at stake: (1) In the 4^3 and larger cubes, there are pieces that may be permuted but are colored the same. Are positions that differ only in the permutation of identically- colored facets to be considered distinct? (2) In all odd-sized cubes, each face has a center facet that may be twisted. Are positions that differ only in the twist of face centers to be considered distinct? If the answer to (1) is `no', the puzzle is not a group, but a collection of cosets. I find this interesting only in that it is understood by the masses, and then the answer to (2) is `no'. If the answer to both (1) and (2) is `yes', we have what I would call the Supergroup. I mark my cubes so that I can distinguish patterns in this group. I discussed a way of doing this for the 3^3 in my message of 9 January 81 0551-EST. For Rubik's Revenge, I use a similar procedure, except now two spots must be cut out on each face: +-----------------------+ | | | | | | | *|* | | |-----+-----+-----+-----| | | *|* | | | | | *|* | |-----+-----+-----+-----| | | | *|* | | | | | | |-----+-----+-----+-----| | | | | | | | | | | +-----------------------+ Also, I now arrange the faces T-symmetrically, with the spots toward the girdle. Jim Saxe first brought it to my attention that we may answer `yes' to (1) and `no' to (2). We get a group that ignores face center orientation. This is probably what people mean when they say there is no Supergroup for Rubik's Revenge: This is the group of the puzzle, and the Supergroup (as I have defined it) is the same for the 4^3. But in the 5^3 this group is distinct both from the Supergroup and from the Color Cosets. The 57th Piece Alan Bawden, in his message of 5 June 82, despaired of explaining the mechanical workings of Rubik's Revenge. I will now rush in. If you take your Rubik's Revenge apart (as described in Ronald B. Harvey's message of 19 May 82, not recommended by Alan Bawden), you will find that the cubies ride around on a sphere: the mysterious 57th piece. Only the face centers are connected to the sphere; they have flanges that hold the edges in place, and the centers and edges have flanges that hold the corners in place. The tricky part is the linkage between the sphere and the face center cubies. The four center cubies of a face have extensions that together form a mushroom-shaped plug. Each plug extends from the center of the face inward and is cut in quarters lengthwise. There are six sockets on the sphere in which these plugs will fit and may rotate, but may not be pulled out. This is sufficient to implement a puzzle isomorphic to the 3^3, namely the 4^3 where we allow only face twists. The other necessity for a 4^3 is to be able to twist the six center slices, which we name after their adjacent faces. To accomplish this, there are grooves in the sphere that form three orthogonal great circles. Each groove has the cross section of half of a socket, and includes the four half-sockets that correspond to a center slice. When we twist one of those center slices, the half-plugs formed by pairs of face centers in that slice ride around the sphere in the grooves. Of course there is an adjacent center slice; when it is moved, it takes the sphere with it. The reason the grooves cannot have the cross-section of a socket is that then, when we twisted half the cube with respect to the other, the sphere might turn forty-five degrees, preventing center slice twists along the other great circles. When you twist the U center-slice of your cube, does the sphere move or stay fixed? To find out without taking the cube apart, hold the cube by the D center slice and repeatedly twist the U center slice clockwise. Don't touch the U or D faces while doing this. Mostly, the U face will turn and the D face will stay fixed, because the cubie-cubie friction is greater than the cubie-sphere friction. Eventually, however, you will either see the U face lag behind the U center slice, or the D face move to follow the U center slice. If the U face lags, the sphere is not moving; if the D face moves, the sphere is moving. I will take this opportunity to mention another feature of the interior sphere: It has screws in it. I took my screws out, but the sphere didn't come apart. Then I put them back in, on the `don't screw with it' principle. Perhaps they are there so Rubik's Revenge won't float? This issue was raised by Tom Davis (12 August 80) back when people were interested in solving the 3^3 underwater. The last I heard, Richard Pavelle (25 July 1980) was able to solve the cube with only five gulps of air. I imagine some of the 30-second whiz kids can solve Rubik's Cube while completely submerged. But Rubik's Revenge? Don't hold your breath. The Mechanical Invisible Group Alan Bawden's message posed an interesting question about the 57th piece, which I will state somewhat differently. Suppose we paint the sockets of the sphere according to the colors of the face centers that inhabit them. Then we mix up Rubik's Revenge and solve it. Must the sockets still match their face centers? The answer is no. In fact, the sphere may be in any of the twenty-four positions consistent with it having once matched the face centers. To show this, we will show how to perform a ninety-degree whole-cube move of the outside without moving the sphere. This is equivalent to turning the sphere ninety degrees, and we can repeat the procedure and its conjugates to move the sphere to any of its twenty-four positions. In order to twist Rubik's Revenge without moving the sphere, we place the cube in a position such that the U, F, and R center slices do not move the sphere and restrict ourselves to the moves: U1 Clockwise quarter twist of the U face U2 Clockwise quarter twist of the U half (face and center slice together) D1 Clockwise quarter twist of the D face U1',U2',D1' Counterclockwise quarter twists R1,R2,L1,R1',R2',L1' Likewise for R F1,F2,B1,F1',F2',B1' Likewise for F The move is actually fairly simple. The tricky part is moving the L center slice cubies without moving the sphere. To do this, remember the eight-flip X = (R1 L1 U1 D1 F1 B1)^2 from the 3^3. This exchanges the L and R center slices in the 4^3, allowing us to cycle the L center slice cubies in the R center slice. R2 L1' X R2 R1' X is a sphere-fixing whole-cube move taking 24 qtw after cancellation. The Theoretical Invisible Group So much for tawdry reality. As Allan C. Wechsler pointed out on 6 August 82, we can imagine a 4^3 puzzle that contains a 2^3 on the inside. If we solve the outside, must the inside be solved? The process shown above for the 57th piece implies not, for that process performs the RL antislice on the 2^3 with respect to the outside. Can any move of the 2^3 be accomplished? Elementary group theory says no, for odd permutations of the Rubik's Revenge edge cubies are also odd permutations of the 2^3's cubies. I ran the Furst, Hopcroft, and Luks algorithm on the problem. It turns out that the permutation parity is the only restriction on what can be done with the 2^3. Thus if we solve the outside, the inside may be in any one of the (8! 3^7)/2 positions obtainable in an even number of quarter twists on a 2^3 puzzle. This in particular includes all whole-cube moves of the 2^3. Unfortunately, I don't know any simple processes for whole-cube moves or for turning two adjacent faces. --- Date: Mon, 23 Aug 82 16:23:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Hypermove lower bounds There is an easy lower bound on the number of hypermoves needed to solve Rubik's Revenge. If we distinguish like-colored face centers, let us fix the BL center of the D face, permitting only the shallow moves B1, F1, U1, U3, L1, R1, and their inverses, and the deep moves F2, U2, R2, and their inverses. Let us compute the number of hypermoves needed to solve just the face centers of Rubik's Revenge. A shallow hypermove can achieve SF = 4^6 = 4096 different face center positions. A deep hypermove can achieve DF = 7! 3^6 = 3674160 different face center positions. So in four hypermoves, at most 1 + (SF + DF) + 2 SF DF + (SF + DF) SF DF + 2 SF DF SF DF = 453,021,789,719,303,692,337 face center positions can be achieved. Since this is fewer than the 23! = 25,852,016,738,884,976,640,000 face center positions of Rubik's Revenge, some face-center positions will require at least five hypermoves. If like-colored face centers are not distinguished, the best lower bound I can find using this method is three hypermoves. If stomach cubies are considered, I think both bounds increase by one, since only deep moves can touch them. It seems strange that this method relies only on the face center solution. Similar arguments about edges are not as good, because so many edge positions are achievable using shallow hypermoves. Corners are practically irrelevant, since they can be fixed using only shallow hypermoves. With respect to the question of odd sequences of hypermoves, Jim Saxe mentions that ``it is plausible that sequences of the form SDSDS may be sufficient while sequences of the form DSDSD may not.'' I would like to add the further plausibility that both types may be sufficient, while neither may suffice alone. --- Date: Thu, 02 Sep 82 07:55:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Re: Hypermove Lower Bounds Date: 31 Aug 1982 1022-PDT From: ISAACS at SRI-KL Could you explain to me how you got the formula of your message of 23 Aug. There are SF different shallow hypermoves and DF different deep hypermoves, and two similar hypermoves in succession can be collapsed into one. The formula expresses the number of alternating sequences of length at most four, which is the sum of the ``Number'' column below. Length Type Number 0 1 1 S SF 1 D DF 2 SD SF * DF 2 DS SF * DF 3 SDS SF^2 * DF 3 DSD SF * DF^2 4 SDSD SF^2 * DF^2 4 DSDS SF^2 * DF^2 I can see more-or-less what you're doing, but I haven't been able to parse the formula. Well, I did leave out the multiplication signs. Also, I haven't seen your notation before. I take it that "U3" is equivalent to "D1'", except hold the D1 in place. Right. I used this notation in "Lower Bounds for the 4x4x4" on 2 June and "Invisible Revenge" on 9 August. How do you represent half twists? Only by two quarters, or is there a shorthand? There is U3^2, not much of a shorthand. For the U slice move, I hinted at U21'. From a group theory perspective, is it easier to talk about hypermoves than slice moves? Hypermoves are a curiosity that Jim Saxe dreamed up. Any sequence of depth 1 (or 3) moves is a single hypermove, as is any sequence of depth 2 moves. I assume you mean to ask whether it's easier to talk the way I usually talk, in terms of what I will call "twist moves" to distinguish them from "slice moves". The question boils down to what set of generators (moves) you want to use when counting the length of a process. This topic was endlessly rehashed in 1980 when people were trying to decide whether to call a half-twist a single move or two. Jim Saxe nearly sent a message in 1980 about using only two generators to solve Rubik's cube. [As I recall, computer failure trashed the message and he never retyped it.] Certainly we can all do slices and half-twists. The question is how many moves to charge for such an operation. The richer the set of generators, the fewer the number of moves, but the more complex the explanation of the generators. I use the "quarter-twist" convention for the 3^3. The generators are 90-degree rotations of faces. This seems natural, because it is the minimal set that satisfies the following criteria. 1. Every possible cube position can be created using these generators, up to whole-cube moves. This is a basic criterion. 2. The inverse of every generator is a generator. This is necessary so that we have a metric. 3. Any position that can be reached by performing part of a generator is a generator. This criterion ties the mechanical operations used in the cube to the permutation group. Otherwise we could have generators like FUF and F'U' and perform F with their composition. Charging two moves for F in that circumstance is somewhat bizarre. 4. Every M-conjugate of a generator is a generator. This is an aesthetic consideration. We could leave out the D and D' twists and still solve the 3^3, but that breaks up the symmetry of the puzzle. Why do I want the generator set to be minimal? Well, we could make it maximal, but then we would have ``over 3 billion'' generators. What I am looking for is a canonical set, and minimality seems like the best way of choosing among metrics. Thus we exclude slice moves as generators because they are not necessary. For the 3^3, this set is particularly fortunate, because the converse of criterion 4 holds: Every two generators are M-conjugate. This allows us to identify some local maxima without long computations (14 December 1980) and to tighten lower bounds using parity principles (9 January 1981). Will that also be true on the 5^3, 6^3, etc? I would just as soon stick with a compatible metric. This is not to say that there cannot be abbreviations for these moves, simply that for the sake of asking ``how many moves does this take'' we count the number of quarter-twists. We unfortunately don't have the converse of criterion 4 for cubes larger than 3^3. For the 4^3, for instance, there are two flavors of move: deep and shallow. Dave Plummer (26 September 1981) described certain positions of the 4^3 as local maxima, but I have convinced him that we cannot demonstrate the truth of that assertion using known techniques other than exhaustive search. My note of 2 June was able to use only one kind of parity in the lower bound argument. Both problems are due to the lack of the converse. From a solving perspective, it seems clumsy. I'll agree that the generators are few in this scheme, but it is possible to generate macros. For instance, consider describing a slice move on the 3^3 cube. Singmaster uses the notation Fs to denote the F1B1' = F12'3 slice move. We can now also talk about the F12' slice move, which is how everyone actually does the move. I think this is much easier to remember than Allan Wechsler's IJK notation (introduced 18 July 1980) or Doug Landauer's HPS notation (27 August 1980) for dealing with whole-cube moves. I'm still not too happy about the state of RubikSong, but I think it's a matter of human engineering, and I like to stick with the mathematics. --- Date: Thu, 23 Sep 82 12:06:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: MegaMinx and orientation theory Funny you should ask about the positions of the MegaMinx. I analyzed this puzzle with the FHL algorithm. It was the longest run of that algorithm that I have heard of, something like 20 CPU hours. Necessity was the mother of checkpointing. The standard MegaMinx has 20 corners and 30 edges. Both the edge and corner permutation parities must be even. Corner and edge orientation parities are zero (mod 3) and (mod 2), respectively. These are the only invariants, so there are twenty-four orbits and (20! 3^20 30! 2^30)/24 ~ 1.007E68 positions. In the SuperMegaMinx, a 1/5 twist of a single face center is possible, so there are (20! 3^20 30! 2^30 5^12)/24 ~ 2.458E76 positions. I think the MegaMinx is going to be easier than Rubik's Revenge, not because there is more carryover from the cube, but because there is more of the puzzle that is not affected by a single generator. Computing a lower bound that takes account of generators that commute is going to be difficult, however: there are triples of commuting generators, and we can find commuting triples {A, B, C} and {A, B, D} such that C and D do not commute. A curious question: What do we mean by the corner orientation of the MegaMinx when the corner permutation is not the identity? On the cube, we took the corner colortabs on two opposite faces of a solved cube and marked both the tab and its position. Then in a scrambled cube we counted the position of each marked corner colortab relative to the marked position on its cubie. This procedure doesn't work on the dodecahedron: where should we mark the tabs on those corner cubies that are not on the two opposite faces? It was a year before I realized that the choice of placing the marks on opposite faces of the cube was arbitrary. The marked tabs and positions can be chosen any way that gives us one marked tab and one marked position per cubie, and has zero orientation parity in a solved cube. It is customary to enforce the second criterion by requiring that marked positions be the positions of marked tabs in a solved cube. The same argument holds for edges, and both generalize to the MegaMinx. Why is there orientation parity? When we twist an n-gon face, the edge cubies move in an n-cycle and their colortabs move in two n-cycles. We call this an ``untwisted cycle''. But we could conceive (see below) of a puzzle where the edge colortabs would move in a single 2n-cycle. This would be a ``twisted cycle'', and would violate orientation parity. Similar arguments hold for corner cubies, whose kn tabs must move in k n-cycles rather than k/d nd-cycles, for d a divisor of k (note that k=4 for the icosahedron (but the icoshahedron has two corner tab orbits, so quite a different argument applies)). To summarize, any puzzle that moves pieces in untwisted cycles must preserve orientation parity. I wonder if some argument of this type can be made for the tesseract. The argument depends on the orientation group being Abelian (it has in fact been cyclic in our examples), and at least some of the hypercubies have nonabelian orientation groups. Perhaps we have to use Abelian quotients of the orientation groups. Has anyone seen the paper on the tesseract that was mentioned by Hofstatder? Retreating to three dimensions, let's consider a variant on Rubik's cube. Suppose you had a gear (heh) embedded in the URF and BLD corners, such that whenever an edge cubie passed by one of these corners (e.g. from UR to UF by twisting U) it would flip (go from UR to FU). This would violate EOP on every quarter-twist! Of course, you know what positions would be possible in such a puzzle. So now let's consider gears in the FU, BL, and RD edges that twist corner cubies as they go by. I don't know about this puzzle, but I suspect that there are only four orbits. --- Date: Fri, 22 Oct 82 19:09:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: The 2x2x2x2 magic tesseract Allan Wechsler's message of 17 May 1982 contains some interesting comments on the four-dimensional hyper-cube, or tesseract. I will expand on them, and offer a correction. The tesseract has eight cubical sides, labeled Back, Front, Up, Down, Left, Right, Out, and In. Each side may be twisted in any of the twenty-four ways that a cube may be rotated in three-space. Since these twenty-four twists are generated by repeated application of the six quarter-twists of the cube, I consider a move to be a single quarter-twist of one of the cubical sides. I have picked three of the quarter-twists of the Out side to be the ``clockwise'' twists, given as Of, Ou, and Or below. Given the constraint that clockwise twists must be conjugates of each other with respect to the movement group of the tesseract in four-space, the remaining clockwise quarter-twists are determined. In the following list, the upper-case letter denotes the side to be twisted, and the quarter-twist is displayed as a permutation on the (square) faces of that (cubical) side. Of=(URDL) Ou=(RFLB) Or=(FUBD) If=(RULD) Iu=(FRBL) Ir=(UFDB) Ro=(UFDB) Rf=(OUID) Ru=(FOBI) Lo=(FUBD) Lf=(UODI) Lu=(OFIB) Ur=(OFIB) Uo=(FRBL) Uf=(ROLI) Dr=(FOBI) Do=(RFLB) Df=(ORIL) Fu=(ORIL) Fr=(UODI) Fo=(RULD) Bu=(ROLI) Br=(OUID) Bo=(URDL) These twists have the satisfying property that when two different twists move an edge from position E1 to position E2, then one of the twists is clockwise and the other counterclockwise. For instance, both the Dr and the Fr' twists move an edge from FID to FOD. Another property that mimics the three dimensional cube is that clockwise twists on opposite sides are reversed: The action of Of on the O side is the inverse of the action of If on the I side. To see how the table above is constructed we must describe the movement group of the tesseract (the group of whole-tesseract moves in four-space). I look at it as operating on quadruples VWXY of mutually adjacent sides. To see if VWXY->V'W'X'Y' is in the group, replace all occurrences of B, D, L, and I with F, U, R, and O, respectively. The resulting permutation must have the same parity as the number of replacements performed. Thus FLOD->UROB is in the group, because we perform three replacements to form FROU->UROF, an odd permutation. To tell whether a quarter-twist is clockwise or not, take the side V to be twisted, two consecutive letters WX from the permutation, and a fourth, orthogonal letter Y from {F, U, R, O}. If VWXY->OURF is in the movement group of the tesseract, then we have the clockwise quarter-twist Vy, otherwise the counterclockwise quarter-twist Vy'. For instance, if we twist the U side as (LFRB), then VWXY=ULFO->OURF is in the movement group (one replacement creates the four-cycle URFO->OURF), so we have the clockwise twist Uo. Let us now examine the reachable configurations of the corners of the tesseract. Every quarter-twist moves eight corners in two four-cycles, so only even permutations of the corners are achievable. The orientations of the corners are more complex. If we move corner VWXY to V'W'X'Y', then VWXY->V'W'X'Y' must be in the movement group of the tesseract. Thus only half of the twenty-four permutations of {V', W', X', Y'} are achievable, because of the permutation parity constraint. To define the orientation of the corners, we label the sides of each corner and each corner position with the letters VWXY, and read the orientation of a cubie as the letters it has in the V, W, X, and Y sides of its position. It is important here to obey the the permutation parity constraint when doing the labelling, so that each cubie may be placed in the home (VWXY) orientation in any position. For instance, one possible labelling is as follows, where each column refers to a corner: V F F F F F F F F B B B B B B B B W U U U U D D D D U U U U D D D D X R O L I O L I R O L I R R O L I Y O L I R R O L I R O L I O L I R Thus if the FURO corner (column 1) is in the FLUO position (column 2), then its orientation is VXYW. Any orientation that is an even permutation of VWXY is possible. The group of orientations, A4, is the same as the movement group of the tetrahedron (with vertices labeled VWXY) in three-space. As I suggested in my message of 23 September 1982, this orientation group is not Abelian, so the orientation of the last corner is not completely determined by the orientations of the other fifteen. To see what is determined, let us look at the tetrahedron with vertices at half of the corners of a three-dimensional cube, say the FUR, FDL, BUL, and BDR corners. As I reported on 15 June 1982, the twelve movements of the tetrahedron consist of the identity, three 180-degree rotations, and eight 120-degree rotations. The June message also mentions that if those corner cubies are moved as a unit, preserving their positions and orientations relative to each other, then the 180-degree rotations are achievable on the 3^3 (they are the corners of the Zig-Zag pattern) but the 120-degree rotations violate the corner twist invariant. Of course, four of them perform a net clockwise twist, and four of them perform a net counterclockwise twist. Define the twist of a tetrahedron movement to be the net clockwise twist it applies to the corners of the cube. Thus the twist of the movements of a tetrahedron VWXY is given by the following table. Twist 0: VWXY, WVYX, XYVW, YXWV Twist 1: VXYW, WYXV, XVWY, YWVX Twist 2: VYWX, WXVY, XWYV, YVXW By reasoning about the actions on corners of the cube, it is clear that the twist of the product of two movements is the sum of their twist, modulo three. Thus the twist group is an Abelian quotient of A4, isomorphic to the cyclic group on three elements. Since the orientation group of the tesseract corners is also A4, we may use the twist group to construct an orientation invariant of the corners of the tesseract. As described in the September message, each qtw moves the corners in untwisted cycles, so the sum of the twists of the orientations of the corners must be zero, modulo 3. I ran the Furst, Hopcroft, and Luks algorithm on the 2^4 tesseract and found that this is the only invariant of corner orientation. Therefore, the number of reachable positions of the tesseract is (15! / 2) (12^15 / 3) ~ 3.358 x 10^18. This is larger than Allan Wechsler's upper bound because he thought there were only six orientations of each corner. --- Date: 22 November 1982 1338-EST (Monday) From: Dan Hoey at CMU-CS-A To: SF-LOVERS Subject: James (A.) Mich(e)ner Recent digests have referred to an author named James Michner (sic). I am aware of an author named James Albert Michener; I have read his name on the outside of several very thick books. Is the author of Space a different person? Or has somebody managed to get through one of those vtb's without getting his name right? Or, horrors, are we the victims of an automatic spelling program gone amok? In the header of #80, there was even a cryptic reference to Micher! Da Hy [I confess that it was an editorial error. The name is indeed Michener. I seem to recall reading one of his books about 12 years ago, THE DRIFTERS, and thinking it was quite good: a bunch of young people wandering around Europe. -- Stuart] --- Date: Tue, 30 Nov 82 18:16:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Pentominoes A friend of mine has a set of pentominoes called ``Quintillions'', available from Kadon Enterprises, Inc. 1227 Lorene, Suite 16 Pasadena MD 21122 Basic Quintillions is a set containing the twelve planar pentominoes for $29.00. Super Quintillions is a set containing the nonplanar pentominoes for $39.00. (The literature says there are eighteen pieces, but I think there are only seventeen nonplanar pentominoes. Perhaps they include some extra piece so you can make a 3x5x6 rectangular prism) The basic set is a high-quality puzzle, each piece laser-cut from a single piece of wood, with a velour box. If you want to make your own, you can glue little cubes together. Here are patterns for the planar pentominoes: X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X For the nonplanar pieces, let U, D, and B stand for cubes on the upper level, lower level, and both levels. The pieces I know of are as follows, where an asterisk denotes a piece that can be reflected to form a new piece: * * * * * * B D D D B D D D B D U B D D B D D B D D D B D D B D B D D B D D D D D B B D B D D D ---