Date: Fri, 28 Jan 83 03:33:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: The shortest sequence of moves. Leonard, The process (R U^2 B^2 L')^2 will restore your cube in twelve quarter-twists when executed with the Green face Up and the White face Front, and twelve is the minimum sufficient number of quarter-twists. Dave Plummer's discouraging word is usually right--we know of no algorithm to let us find optimal processes for most positions. This is because the only known algorithms involve exhaustive breadth-first search, and there are far too many positions of the cube to make this practical in either time or space. But when the optimal process is sufficiently short, some headway can be made. Having some megabytes and CPU-hours at my disposal, I was able to list (A) all positions reachable in five qtw from your cube, and (B) all positions reachable in five qtw from SOLVED. Finding that sets (A) and (B) are disjoint, I conclude that there is no ten qtw process for the pattern, so the twelve qtw process is optimal. I discovered the optimal process by hand. Of course, I could have just run the program one more qtw and it would give me the process, along with any other twelve-qtw processes that may exist. The problem with that approach is that I don't have that many megabytes and CPU-hours. My program, by the way, is written in C and runs under Unix. It trades time and storage efficiency for programmer laziness, making extensive use of the Unix sort utility. Dave Plummer has written a much optimized program, in assembler language for the PDP-20, that uses very clever hacks (some of them my own). As I recall, he and I estimated that with about 150 megabytes and a day or two elapsed time on an unloaded machine it could take the search three more quarter-twists. Does anyone need to settle a bar bet on an eighteen qtw process? Dan --- Date: Sun, 30 Jan 83 03:15:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Finding optimal processes The best known bounds put the maximum number of qtw at between 21 and 104. At most about 1 percent of the cube's positions are within 18 qtw of solved. At each qtw, the number of positions increases by a factor of almost sqrt(12+5*sqrt(6))+sqrt(6)+2 ~ 9.374. [I say ``almost'' because this rate of increase does not take into account the identities of length 12 qtw or greater. Eventually, long identies reduce this factor to zero. But between six and seven qtw, the factor is about 9.356]. If we want to show a 2n qtw process optimal, we need only scan the table of n-1 qtw processes, so the increase is more like a factor of 3 per qtw. Finally, I would like to call attention to the fact that showing an 18 qtw process to be optimal requires about 150 megabytes and two days on a PDP-20 for each such proof. Finding someone to lend you a big machine and a big disk for two days is not something you can take for granted. And if you want to do it on your Apple, be prepared to sit around swapping 2400 floppies in and out for the next decade or so, as that two day figure is mostly disk latency rather than CPU time. --- Date: Thu, 24 Feb 83 18:15:00 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Whole-Cubing When we describe cube positions, we typically fix the position of the face centers. This avoids counting different positions of the same pattern more than once. But suppose we wished to distinguish between different positions of a pattern? How should we form this group G* of spatially oriented patterns? A simple way of generating G* is to adjoin generators for C, the motion group of the cube, to generators for G, the usual Rubik group. Generators for C were discussed in early Cube-Lovers mail as I, J, and K, three orthogonal quarter-twists of the whole cube in space, although there was some disagreement about which was which. We generate G with B, F, U, D, L, and R as usual. Unfortunately, the two kinds of generators are not conjugates, which was a nice thing about our generators for G. Also the generators do not interact very strongly. If we have an identity on {IJKBFUDLR}, the substring on {IJK} must be an identity in C, and there is a simple way of transforming the substring on {BFUDLR} to be an identity in G. In @i, Berlekamp, Conway, and Guy described another way of generating G*, by appending the slice moves, which they name by mnemonic greek letters; this labeling scheme was also reported in Hofstadter's column. Here we have some stronger interaction between the two kinds of generators, but they are still two different kinds: they are not conjugate. This has never really bothered the English, though; they gratuitously include half-twists as generators as well. I thought up a scheme involving what I will call depth-2 moves named B2, F2, U2, D2, L2, and R2. Readers of my reports on the 4^3 and 5^3 cubes will find these familiar. Essentially, a depth-2 move is performed by turning a face together with its adjacent center slice. Thus F2 involves holding the B face immobile and turning the rest of the cube a quarter-turn clockwise, as seen from the front. Clearly the depth-2 moves are M-conjugate. Unfortunately, they do not generate all of G*, nor even all of G. This can be seen easily by noticing that each depth-2 move is an even permutation of the edge cubies, while G includes odd permutations of edges. We can look at this a different way by observing that a depth-2 move is the same as a vanilla depth-1 move of the opposite face together with a whole-cube quarter-twist. Thus we can perform any depth-1 process using depth-2 moves, and observe the spatial orientation of the cube at the end. If we performed an odd number of depth-2 moves, then there were an odd number of whole-cube moves, so the cube cannot be in its home orientation at the end. So just what group do the depth-2 moves generate? It turns out that they generate precisely half of G*, the half that contains even edge permutations. Suppose we want to produce such a position in G*. First operate in G, simulating depth-1 moves as described above, to produce a position that is an even number of whole-cube moves from the desired one. Then use M-conjugates of the process F2 L2 D2' B2' D2' F2 L2 B2 L2 U2' F2' D2' R2' B2, which performs a whole-cube third-twist. [This was derived from identity I14-4]. Since all the even whole-cube moves are generated from third-twists, this is all you need. What can we do about generating all of G* with a set of conjugate generators? Sad to say, that is impossible. For supposing we had such generators, their cycle structures would have to be the same; in particular, they would have to have the same permutation parities. Applying an odd number of such generators would yield those parities, and applying an even number would yield even parity on every kind of cubie. But G* includes four different parity classes: Face centers Edges Corners even even even even odd odd odd even odd odd odd even so at most half of G* can be generated with a set of conjugate generators. --- Date: Wed, 01 Jun 83 19:39:00 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Eccentric Slabism, Qubic, and S&LM I don't know whether Isaacs or Singmaster know just what a bombshell was contained in the Cubic Circular. I am somewhat frightened at the possibilities. Section 1 discusses the history of metrics for N^3 puzzles and proposes a new one. Section 2 describes new symmetries of the generators of the 4^3 puzzle. Section 3 outlines a theory of symmetry and local maxima for the 4^3 puzzle. Section 4 indicates directions for further work. 1. Cutism, Slabism, and Eccentric Slabism ========================================= Let's start with the question that was posed by Stan Isaacs in his message of 26 May: what is a quarter-turn on the 4^3 or larger cube? On the N^3 puzzle, each set of N-1 parallel ``cuts'' divides the cube into N ``slabs''. There seem to be two straightforward metrics. The Slabist defines a move to be a turn of one slab with respect to the rest of the cube. The Cutist defines a move to be a turn of a connected part of the cube with respect to another connected part, the two parts being separated by a cut. [In the terminology I used on 2 September 1982, the Slabist counts ``slice moves'' while the Cutist counts ``twist moves.''] I have heretofore espoused Cutist theory. For one thing, it agrees with our current theories on the 3^3 in disallowing a turn of a center slice as a single move. This seems to be a good idea, since the current quarter-turn theory has the advantage of conjugate generators, which it would lack if we allowed center-slice moves. [This is presumably not a problem for Singmaster, who allows the squared moves, which are not conjugate.] Another reason for Cutism is that it makes it easier to equate positions that arise from a whole-cube move of the N^3. A third reason is that it makes the parity hack (see my message of 1 June 1982) easier. The last two reasons are for convenience only; the arguments can still be made in a Slabist formulation. But as I admitted, I solve the cube as a Slabist. Slabs are probably convenient because they minimize the degree of each generator. I casually dismissed this tawdry practicality until I was struck by Evisceration. In the course of my examination of Evisceration I have experienced an epiphany which converted me to Eccentric Slabism. I now define a move to be a turn of any slab except one whose interior contains the center of the cube. In other words, any slab except a center slice. At first glance, Eccentric Slabism looks like a hack, since there is an excluded slab only in the case of a puzzle of odd size. I believe that the truth is more complicated, but the explanation is partly beyond the scope of this note and partly beyond my knowledge. If you really want an answer I suggest you study tic-tac-toe. 2. Evisceration, Inflection, and Exflection =========================================== The (Eccentric) Slabist moves of the 4^3 puzzle form the 24-element set Q4={B,B',b,b',...,r'}, where upper-case refers to turning a side (an outslab move) and lower-case refers to turning the adjacent internal slab (an inslab move). We consider these moves as generators of G4, the ``Theoretical Invisible Group'' [Invisible Revenge, 9 August 1982] in which the inslabs turn the eight stomach cubies like a 2^3 puzzle. Thus two positions in G4 are equal if and only if all sixty-four pieces of the cube are in their home position and orientation. [Actually, this is not quite the Theoretical Invisible Group, since we do not equate positions that differ by a whole-cube move. I feel confident that the identification can be performed, but I will speak of the unidentified group here.] Consider the following permutations on Q4: Rotations: I=(FRBL)(F'R'B'L')(frbl)(f'r'b'l'), J=(FUBD)(F'U'B'D')(fubd)(f'u'b'd'), Reflection: R=(FB')(F'B)(RL')(R'L)(UD')(U'D)(fb')(f'b)(rl')(r'l)(ud')(u'd), Evisceration: V=(Ff)(F'f')(Bb)(B'b')(Rr)(R'r')(Ll)(L'l')(Uu)(U'u')(Dd)(D'd'), Inflection: N=(fb')(f'b)(rl')(r'l)(ud')(u'd), Exflection: X=(FB')(F'B)(RL')(R'L)(UD')(U'D). Permutations I, J, and R are familiar generators of M, the group of rotations and reflections of the cube. Singmaster introduced Evisceration, which consists of swapping each outslab with the adjacent inslab. I extend the list with Inflection and Exflection. Inflection consists in swapping each inslab with the inverse of its parallel inslab; Exflection swaps each outslab with the inverse of its parallel outslab. It is well known that M is a group of automorphisms on G4. Singmaster observed that Evisceration is also an automorphism. I observe that Inflection and Exflection are automorphisms, too. Thus M4, the 192-element group generated by is a group of automorphisms on G4. [Actually, since R=NX and X=VNV, M4=. The group M4 is also the automorphism group of the game of Qubic, or 4^3 tic-tac-toe.] I began to doubt Cutism when I noticed that M4 sometimes maps cut moves to pairs of cut moves. I went home last night wondering why this might be so. I nearly got to sleep before I realized the big news: M4 is Q4-transitive! Eccentric slabs are conjugate! 3. Symmetry and Local Maxima ============================ This section relies especially heavily on ``Symmetry and Local Maxima'' [14 December 1980; available as file "MC:ALAN;CUBE S&LM" on MIT-MC]. Following the argument in S&LM, consider the symmetry group of the Pons Asinorum (with the face-centers each half-twisted, as is customary). We already know Pons is M-symmetric; by examination, the symmetry group of Pons also contains Evisceration and Inflection. Thus Pons is M4-symmetric. The result is that Pons is a local maximum in G4. This is the first local maximum to be found in a close relative of Rubik's Revenge. It is not hard to show that we can dispense with fixing the Pons in space, and it is only slightly harder to carry out in general. Unfortunately, I see no way of showing that Pons is a local maximum if we ignore the stomach cubies without ignoring the corners. 4. Open problems ================ This is a pretty random collection of directions for further work. Some of these were posed in the text. The ones I think likely to be impossible are labeled (*). Conjecture: The automorphism group of the Eccentric Slabs of the N^3 puzzle is the same as the automorphism group of N^3 tic-tac-toe. I don't believe this has been rigorously done for any N>1. Stronger conjecture: The automorphism groups of the N^D puzzle and N^D tic-tac-toe are the same. (Hint: There are at least two definitions of the N^D puzzle. I think both work.) Extension: The relation between the automorphism groups is too amazing to be accidental. What is really going on here? Search: There is published literature on tic-tac-toe automorphisms; in particular the group of automorphisms of N^D tic-tac-toe is well known. I seem to recall seeing some horribly theoretical work, approaching the problem from the standpoint of algebraic geometry or some such. At that time I settled for scanning the results. Now I have questions that need a general treatment. If the world's leading expert on Qubic has his bibliography on line, I think there's a reference I'd appreciate. Actually, I'll take references from anybody and send the compilation to any requestors. Query: Why must slabism be eccentric? Query: Can Cutism be saved? Are cut moves conjugate in some sense? Easy extension: Equate positions that differ by whole-cube moves. Hard extensions (*): Equate positions that differ only internally. Equate positions that differ only in the permutation of like-colored face cubies. Problem: Prove that the Pons requires 12 quarter-turns in the 4^3 puzzle. Ditto for 12 qtw in the N^3 puzzle(*?). Prove or disprove for 4D qtw in the N^D puzzle (*). Problem: Find the Q4-transitive subgroups of M4, then list all the Q4-symmetric local maxima in the 4^3. Problem: Describe all symmetric local maxima of the N^3(*), or place useful conditions on them. Problem: Demonstrate an infinite class of local maxima (Ponses?). Final query: Did someone ask if Cubism was dead? Dan Hoey HOEY@CMUA.ARPA --- Date: 10 Aug 1983 13:26-EDT From: Dan Hoey To: SF-LOVERS Subject: Re: The Transporter; why it can't do that Gary Samuelson, in V8 #44, brings up a ST episode (which I haven't seen) called ``The Day of the Dove''. In this some Klingons had their transporter trip put in a holding pattern. Scotty claimed that they were in the transporter during the delay. Gary concludes that ``if information ... can be stored, it can be copied.'' In the case of Star Trek, I am not sure that objects en route via the transporter are information. Perhaps they are some third state of matter/energy, or some sort of astral essence. I have enough disregard for ST's internal consistency to consider the question worthless. But Star Dreck aside, I am very uncomfortable with Gary's last statement. Known ways of transmitting information, including transmission into and out of a storage medium, do involve copying. But I can't think of any reason why the ability to transmit and store information implies the ability to copy it. Any takers? Dan --- Date: 16 Nov 1983 18:02 EST From: Dan Hoey Subject: MSGGROUP#2197 Digesting and ending To: Human-Nets@rutgers, MsgGroup@brl There have recently been discussions in Human-Nets (V6 #71) about standards for separating the messages in a digest. This recalls a discussion begun by Bill Wells in MsgGroup this past May (among messages 2017-2054) about the need for ending markers in messages. Mabry Tyson notes that you can't use ``separators the way it is currently done.'' The problem is that any fixed sequence that marks the end of messages may be included in the body of a message, leading to false recognition of the end of the message. Many message systems use some quoting scheme to prevent the ending string from occurring in the message. These schemes have led to such abominations as extraneous angle brackets on lines beginning with the word ``From'' and duplication or removal of periods at the beginning of lines. Mabry suggests using a character count at the beginning of each message, and notes several problems involving CR LF versus LF, NULs, and the previously-mentioned abominations. These problems are easily overcome by using a line count instead of a character count, but I still find the scheme distasteful: remember how hard it is to read Fortran's 9HHollerith specifications for strings? Fortunately, there is a solution to the problem. Given any message, it is fairly easy to find a string that does not occur in the message. Such a string may be used to mark the end of the message. The string itself can be mentioned in the message header, so that a reader seeing the beginning of the message will know where the end is. Thus: Date: 16 Nov 1983 18:02 EST From: Luser@Random-Site End-marker: XYZ Message not containing that string. End-of-message: XYZ An added frill is to reverse the string in the message header, in our example ``End-marker: ZYX''. This prevents the end marker from occurring anywhere in the message, even in the header, and yields the amusing bonus of allowing a context-free syntax for messages. I dearly hope that there will be some work done to make message endings more recognizable by humans and machines. Dan Hoey hoey@NRL-AIC --- Date: 17 Nov 1983 14:11-EST From: Dan Hoey To: SF-LOVERS Subject: M. A. Foster I have enjoyed M. A. Foster's books for a long time, and also wondered about the author's sex. When book reviews and some discussions in SF-Lovers (around 1980-81?) used the male pronoun, I wondered. After all, Tiptree had everyone confused too, and there were those well-developed female characters in the books. Somehow the whole tone of tWoD seemed the kind of sensitive, caring writing that I have come to expect from Bradley, Clayton, and Norton and no male authors. My doubts were put to rest when I read (and I believe this was in SF-Lovers) a note from someone who knew Meg Foster and claimed she was the woman who wrote as M. A. Foster. Last month I went to RoVaCon and met Mike Foster, the author of all those good books. We talked about the ler language--he says it's derived from Chinese. I urged him to work on an idea he had considered --a collection of short ler stories, perhaps along the lines of a fable that was included in tWoD or tGoZ. There is clearly a lot of lerology that appears in none of the three published novels. The biography from the RoVaCon program book appears at the end of this message. I thought he had come out with a sequel to Waves, though, with a title something like Pressure Man. I don't recall it as being very good, which would explain its being omitted from the bio. Dan Hoey ----- Michael Anthony Foster from Greensboro, North Carolina, is one of DAW Books' leading SF authors. His first book, The Warriors of Dawn, billed on the back cover as a ``fine new novel'' and ``the debut of a great SF talent,'' appeared in 1975. The cover was designed by our own Frank Kelly Freas [sponsor of the RoVaCon Art Scholarship]. The novel was the first in a trilogy about genetically created supermen and superwomen, one of whom teams up with a normal human male against interstellar pirates. The next book was The Gameplayers of Zan, published in 1977 (a prequel to Warriors), and the third book was The Day of the Klesh, 1979. Foster's next book was Waves (1980), and in 1981 DAW brought out The Morphodite. Its sequel, The Transformer [probable typo--my copy omits the definite article], appeared in 1983. Hallucinations>, four short novels under one cover (only one of which is previously published) will appear in 1984. A work in progress is to be called Candastara, and will tentatively be out in 1985. M. A. Foster is a two-time nominee for the John Campbell Award for Best New Writer which is given annually by the World Science Fiction Convention. He is a former data systems analyst and was an ICBM launch crew commander in the U. S. Air Force. Since 1978 he has been employed as a salesman of welding supplies and industrial/medical gasses, and he is as involved currently with metallurgy as he was formerly with electronics and signal propagation. He is a semi-professional photographer, a novice bass guitarist, and also an articulate panelist at conventions here and elsewhere. M. A. Foster has already made his mark among the cadre of science fiction novelists, and we are proud to have him on the RoVaCon Advisory Board. ---