Date: 11 December 1982 20:43-EST
From: Alan Bawden
Subject: The Archive & Administrivia
To: CUBE-LOVERS at MIT-MC
Those of you who look through the archives of old Cube-Lovers mail
will notice that I have split off a new section of the archive. The
mail now lives in:
MC:ALAN;CUBE MAIL0 ;oldest mail in foward order
MC:ALAN;CUBE MAIL1 ;next oldest mail in foward order
MC:ALAN;CUBE MAIL2 ;more of same
MC:ALAN;CUBE MAIL3 ;yet more of same
MC:ALAN;CUBE MAIL4 ;still more of same
MC:ALAN;CUBE MAIL ;recent mail in reverse order
Those of you who are wondering if Cube-Lovers might be temporarily off the
air when TCP is installed on January 1 can rest assured that there is an
ITS TPC implementation in progress, and come January 1 the ITS machines
will probably be no worse off than the rest of the net. My biggest worry
is not that ITS won't be able to send mail (since I can always move the
list to another machine if that proves necessary), but that so many of you
all will be having difficulty recieving mail that I will be up to my neck
in error messages from various mailers around the net.
That is one of my reasons for splitting off a section of the archive at
this time. I'm willing to bet that a fair number of you will be requesting
the back mail that you have missed during the storm at the beginning of the
year, and this way I have a small file that I can easily send off to you.
Finally let me remind you all to please address your requests to
Cube-Lovers-Request at MIT-MC. If that address, or Cube-Lovers at MIT-MC
ever seems to be giving you trouble, you might also try Cube-Lovers at
MIT-Multics and Cube-Lovers-Request at MIT-Multics.
-Alan
Date: 21 December 1982 23:50-EST
From: Alan Bawden
Subject: Correction to previous message.
To: CUBE-LOVERS @ MIT-MC
It being so difficult to set up a Multics mailing list I'm retracting the
promise that those Multics addresses will ever work and will instead
just give out my personal Multics address as an emergency contact.
Date: Wednesday, 22 December 1982, 15:33-EST
From: Allan C. Wechsler
Subject: Hinton's cubes.
To: Cube-Lovers at MC
In September I received a query from Phil Servito, who
has since joined this mailing list, about a game or puzzle
called "Hinton's cubes". Does anybody have any information
about this toy besides the following?
Charles Howard Hinton was an American mathematician who
believed that anybody could learn to do four-dimensional
visualization if properly trained. He invented a set of
colored blocks which were supposed do this training.
Philip -- you said Martin Gardner knows more. Is this because
the cubes were once discussed in a Sci. Am. Mathematical
Games column? If so, the Sci. Am. cumulative index may help.
--- Allan
Date: 29 Dec 1982 0954-PST
Subject: article of interest.
From: Dave Dyer
To: cube-lovers@MIT-MC
The Christmas issue of NEW SCIENTIST has an article by Singmaster
about the basics and metaphysics of the cube. No great revelations,
but a literate discussion of cubeology.
-------
Date: 29 Dec 1982 19:01:04-EST
From: meister at mit-ccc
To: cube-lovers@mit-mc
Subject: 4x4x4 poll
i am interested i getting information on the various solving methods
used on the 4x4x4, and the times that it is being done in. (average)
my own method is to solve it as follows:
1) top layer (no general order to this)
2) the rest of the centers by layers
3) the edges on the center slices
4) bottom corners
5) bottom edges
average time: 1 min 55 sec - 2 min 5 sec depending on my blood-alcohol level.
please send me your general method and solving times.
i'll compile the results and put them on the list.
thanks for replying,
-phil
p.s. - send replies to meister@ccc@mc
Date: 30 December 1982 00:41-EST
From: Jonathan David Callas
Subject: Hinton's cubes.
To: ALAN @ MIT-MC
cc: CUBE-LOVERS @ MIT-MC
I remember reading about Hinton's cubes in an old Mathematical Games anthology,
so a cumulative index would be the thing. Gardner wrote about them and
apparantly they worked, but there were stern warnings not to play with them,
because (!) they cause insanity in some people(!!). Gardner said something
to the tune of that the human brain is not meant to do 4-dimensional geometry,
and these things will make your brain bugcheck. Ever since then, I have been
fascenated by the thought of a puzzle that would blow your mind literally! Of
course, this was in the days before it was fashionable to use chemical means
to do this. Anyone else know anything about them?
Jon
Date: 3 Jan 1983 0915-PST
From: ISAACS at SRI-KL
Subject: Hinton's Cubes
To: cube-lovers at MIT-MC
cc: isaacs at SRI-KL
Hinton's Cubes are mentioned in Martin Gardners "Mathematical Carnival",
Chapter 4, Hypercubes, a reprint of the November, 1966, Mathematical Games
column from Scientific American. He doesn't say much, mainly that "Hinton...
devised a system of using colored blocks for making three-space models of
sections of a tesseract." Hinton believed that they would help develop
an intuitive grasp of 4-space. The fullest account of them mentioned is
the book k"A New Era of Thought", by C. Howard Hinton, Swan Sonnenschein,
1888, apparantly reprinted in 1910.
Gardner also prints a letter he received from Hiram Barton, of England,
including "A shudder ran down my spine when I read your reference to Hinton's
cubes. I nearly got hooked on them myself in the nineeen-twenties. Please
believe me when I say that they are completely mind-destroying. The only
person I ever met who had worked with them seriously was Francis Sedlak, a
Czech neo-Hegelian philosopher...who lived in an Oneida-like community near
Stroud, in Gloucestershire.
"As you must know, the technique consists essentially in the sequential
visualizing of the adjoint internal faces of the poly-colored unit cubes
making up the large cube. It is not difficult to acquire considerable
facility in this, but the process is one of autohypnosis and, after a while,
the sequences begin to parade themselves through one's mind of their own
accord."
It goes on, but doesn't say a great deal more. I don't have my copy of
Hintons book "The Fourth Dimension", but maybe it will give some more
description.
If anybody does find some marketed versions of the cubes, put it on the list.
--- Stan
-------
Date: 4 January 1983 03:54-EST
From: Alan Bawden
Subject: Humor
To: CUBE-LOVERS @ MIT-MC
From "Special Deliverance" a recent novel by Clifford Simak:
"He also mentioned a cube," said Sandra. "I wonder what it could be.
Never before have I heard anything described simply as a cube."
Well I certainly have!
(And no, the book actually has nothing to do with Hungarian Cubes. It just
struck me as strange that someone could write that line at a time when an
object that frequently WAS described simply as "the cube" was enjoying some
popularity. Perhaps Sandra's ignorance is excusable in light of the fact
that she comes from an alternate universe...)
Date: 5 Jan 1983 1802-PST
From: ISAACS at SRI-KL
Subject: Other news
To: CUBE-LOVERS at MIT-MC
The new RUBIK'S magazine is out. Not as interesting (to me) as the first.
Several articles on the Snake, on cube contests, and some on other games.
A computer flow-chart for the game Awari, and an analysis of Chinese Rings
are included. The most interesting cube articles are one on how disordered
a cube can get; and one on pretty patterns in other cube universes (ie, when
an edge is flipped, what symmetric patterns are there).
If you haven't seen it, the book "INside Rubik's Cube and Beyond" by
Christoph Bandelow is very good. It's translated from German, and contains
a fairly technical discussion of the Mathematical Model, solving in the
supergroup, other magic polyhedra, a detailed flowchart of a cube-solving
program (which also checks the input for legality), and a comprehensive
Maneuver Index, which contains, among other things, a complete catalog of
3-cycles. It includes an index, a bibliography, and a good section of
colored pictures in the center (including one of a 5x5x5!!!). Recomended.
I've also heard a rumor that the solution to "Masquerade" has been
written (and maybe published). Has anyone heard anything of this?
-- Stan
-------
Date: 5 Jan 1983 1806-PST
From: ISAACS at SRI-KL
Subject: more on Hinton's Cubes
To: cube-lovers at MIT-MC
I got my "Speculations on the Fourth Dimension, Selected Writings of
Charles H. Hinton", Dover, 1980, back. It doesn't reprint Hinton's
description of his cubes, but Rudolf v.B.Rucker, in the introduction
describes something more of them:
"The second part of "A New Era of Thought" consists of a description
of how to visualize a tesseract by looking at various 3-D cross sections
of it. On is to construct a set of 12 cubes, coloring the faces, edges
and corners all manner of different colors. (Eighty-one different colors
are used, and some rather unfamiliar ones are resorted to. ...)Eight of
these cubes make up the boundaries of the hypercube, and the four others
are cross sections taken between pairs of opposite cubes. The way in
which all the cubes fit together is really explained rather well, if one
has the will to endure not only 81 colors, but the 81 Latin names which
Hinton assigns to the parts of the tesseract.
"In addition to the set of 12 large cubes, there was also to be a set of 81
small monochrome cubes, each representing a part of the tesseract. By
moving theese little cubes about one could better comprehend the fact that
rotation through the fourth dimension corresponds to mirror image reflection
in 3-D space."
In Hinton's book "The Fourth Dimension", published n 1904, he has a
streamlined version of the tesseract section models. "There were actually
three parts to the complete set of tesseract models. There was a set of 27
"slabs," actually cardboard squares; a set of 81 one-inch monochrome cubes,
each a different color; and a set of 12 multicolored "catalogue cubes,"
which were depicted in a color plate bound into "The Fourth Dimension". When
the book came out, one could buy a set consisting of the 27 slabs and the
81 little cubes for 16 shillings, or a set consisting of the 12 catalogue
cubes for 21 shillings."
If anyone on this list can find a copy of "The Fourth Dimension", I, for
one, would like to buy it. I wonder if any of the models are around anywhere?
--- Stan
-------
Date: 7-Jan-83 10:19:31 PST (Friday)
From: Pettit at PARC-MAXC
Subject: 4-D Graphics Program
In-reply-to: ALAN's message of 5 January 1983 23:40-EST
To: Alan Bawden
cc: Cube-Lovers at MIT-MC
Scott Kim, the author of Inversions, wrote a program about 4 or 5 years ago which ran on Tenex, and allowed one to rotate 4-D skeletal objects and view the 2-D projections (on an Imlac display). I don't know what language it was written in. It was apparently quite good at allowing one to achieve an intuition for 4-D space. I'll send him a message and ask if his program is available anywhere for playing with.
--Teri Pettit at Xerox OSD
Date: Monday, 24 January 1983 13:57-EST
From: Leonard N. Foner
To: Cube-Lovers @ MIT-MC
Subject: Shortest sequence of moves?
cc: Tk.Foner @ MIT-OZ
Reply-to: Foner at MIT-MC
I remember hearing about a program, probably running on the color LISP
machine, that could take an arbitrary cube and try to see what the
shortest move sequence to its slution is. Does anyone remember where
this program is and how to use it?
Specifically, I have been given the following cube and asked to find
the shortest solution:
GBG
BGW
GGG
RRR WYW ORO YYY
ORO GWY OOO WYB
RRR WWW ORO YWY
BBB
GBY
BGB
If anyone can either find the program I think I remember, or can
determine what they think is the shortest solution, I'd be \very/
grateful! Speed is of the essence.
Thanx much, everyone!
Date: 24 Jan 1983 1122-PST
From: ISAACS at SRI-KL
Subject: Masquerade
To: cube-lovers at MIT-MC
A small paperback version of Masquerade has come out in England, which
contains a history, who solved it, and what the solution is. I don't know
if it is available in the U.S. yet, but I have seen a copy, and got the
following info: The full title & subtitle is "The Treasure Hunt of the
Century / Masquerade / Kit Williams Tells the Answer to the Riddle",
ISBN 0 224 02937 1; Jonathan Cape (pub), Thirty Bedford Square, London.
I will check around to see if it is available --- Just did; At lease
one local book store (Printers Inc, in Palo Alto, Ca.) says it's on order,
and they expect in in a day or two.
If anyone wants a rough idea of how to find the solution, I can put it
on the net.
-- Stan
-------
Date: 24 January 1983 16:51 EST
From: David C. Plummer
Subject: Shortest sequence of moves?
To: FONER @ MIT-MC
cc: CUBE-LOVERS @ MIT-MC
Date: Monday, 24 January 1983 13:57-EST
From: Leonard N. Foner
Reply-to: Foner at MIT-MC
I remember hearing about a program, probably running on the color LISP
machine, that could take an arbitrary cube and try to see what the
shortest move sequence to its slution is. Does anyone remember where
this program is and how to use it?
Sorry, no such program. Don't we wish though!! If we understood
the mathematics of the cube well enough to write such a program,
we probably wouldn't have this mailing list anymore.
Date: 28 Jan 1983 3:33-EST
From: Dan Hoey
Subject: The shortest sequence of moves.
To: Foner at MIT-MC
Cc: Cube-Lovers at MIT-MC
In-Reply-To: Leonard N. Foner's message of Monday, 24 January 1983 1357-EST
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: 28 Jan 1983 1838-PST
From: ISAACS at SRI-KL
Subject: Circle Puzzles
To: cube-lovers at MIT-MC
cc: isaacs at SRI-KL
I just got some very nice examples of circle (group-theory) puzzles -
similar to the Lorente Grill puzzles shown in Hofstadters' Sci.Am.
article in July, 1982 (p. 26). They are made by Douglas Engel, under
the name of General Symmetrics, Inc, 2935 W. Chenango, Englewood, Co,
80110. He is selling some as experimental items, and one version he
hopes to have marketed "soon". They all consist of two intersection
circles, each of which rotate; I have 3 kinds: the "21 piece", similar
to 2/3 of Lorente's Trebol puzzle; the "35 piece", similar to the
one in the upper right corner of the article "Another Grill puzzle by
Lorente", and a "19 piece", similar to the 21 piece, except the circles
intersect in the center. Each of these are quite different from each other;
the 35 piece has 3 different pieces which rotate in 4 different cycles
(compare to the Cubes' 3 kinds of pieces - edge, corner, and center).
In the 35 piece, a straightforward "in in out out" (R'LRL') type move
will move the centers in a 3-cycle, the "square" pieces in a pair of
2-cycles, and the "triangles" in 2 separate 5-cycles.
(Doug is selling these at $10.00 for the 19 or 21 piece, $20 for the
35 piece.)
Doug Engel has also written a paper called "Some Problems Suggested
By Circle Puzzles", mostly asking questions about various kinds of
symmetry in this type, whether there are an infinite number of them,
etc. I wonder what the best way to talk about them and analyze them
from a group theory perspective is. I'll try to put in more information
and theories as I work on them; I'd like to hear any thoughts or
suggestions. Right now, I want to go home for dinner.
-- Stan
-------
Date: Saturday, 29 January 1983 23:33-EST
From: Leonard N. Foner
To: Dan Hoey
Cc: Cube-Lovers @ MIT-MC, Tk.Foner @ MIT-OZ
Reply-to: Foner at MIT-MC
Subject: The shortest sequence of moves.
In-reply-to: The message of 28 Jan 1983 03:33-EST from Dan Hoey
Thanx for the solution... we determined independently that 12 qtw
seemed to be minimal, but couldn't be absolutely sure.
Since you say with a couple of days of CPU time you could deal with 18
qtw processes, doesn't this mean that \any/ cube process can be
checked for minimality? I can't recall whether the maximum number of
moves from solved is 17 or 19... if the former, 18 qtw may be
unnecessary. If the latter, then almost every cube process can be
checked directly, save the absolute longest ones (which are then
provably 19 anyway, since that's all they can be). Is my reasoning
faulty here? In any case, exactly how much more work in involved for
each qtw in solving the cube? In other words, how fast does it grow
(what's the power on the exponent, if describable this way)?
Thanx much folks.
Date: 30 January 1983 00:40 EST
From: Alan Bawden
Subject: The shortest sequence of moves.
To: FONER @ MIT-MC
cc: CUBE-LOVERS @ MIT-MC, Tk.Foner @ MIT-OZ, HOEY @ CMU-CS-A
In-reply-to: The message of 29 Jan 1983 23:33-EST from Leonard N. Foner
The maximum number of moves (qtw) from solved is certainly not 17 or 19.
All we know about that number is that it is greater than or equal to 21.
It could be even larger. There is a fair amount of sentiment that it is
probably around 28, but that's just intuition.
Date: 30 Jan 1983 3:15-EST
From: Dan Hoey
Subject: Finding optimal processes
To: Cube-Lovers at mit-mc
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: Monday, 31 January 1983 21:48-EST
From: Leonard N. Foner
To: Alan Bawden
Cc: CUBE-LOVERS @ MIT-MC, HOEY @ CMU-CS-A, Tk.Foner @ MIT-OZ
Reply-to: Foner at MIT-MC
Subject: The shortest sequence of moves.
In-reply-to: The message of 30 Jan 1983 00:40 EST from Alan Bawden
Ugh. I see the problem is far more intractable than I had first
assumed. I suppose it'll be quite some time indeed before we see any
sort of complete optimality solution if the maximum number of moves
from solved is anything larger than the low twenties. I'll hunt
through the list archives for what's been accomplished on proving what
that number is... if anyone feels like giving me a brief refresher
instead, I'd appreciate it, though the whole list might not like to
see it all again.
Thanx again everyone.
Date: 1 February 1983 13:20 EST
From: David C. Plummer
Subject: The shortest sequence of moves.
To: FONER @ MIT-MC
cc: CUBE-LOVERS @ MIT-MC, ALAN @ MIT-OZ, Tk.Foner @ MIT-OZ,
HOEY @ CMU-CS-A
What you really want is some deep mathematical insight. You
know, the kind Gauss and Fermat had...
Date: Tue 15 Feb 83 15:04:02-PST
From: ISAACS@SRI-KL.ARPA
Subject: "6-T" pretty pattern
To: cube-lovers@MIT-MC.ARPA
A friend of a friend says he can do the 6-T pattern in 16 moves
(he may call 1/2 turns a move, I'm not sure). Does anybody know if
this is a minimum? I'll try to get the sequence.
-- Stan
-------
Date: Wednesday, 16 February 1983, 09:24-EST
From: Bernard S. Greenberg
Subject: 5 x 5 x 5
To: cube-lovers at MIT-MC
I have seen and touched a 5 x 5 x 5 Rubik cube device. It was
allegedly a prototype by Meffert, the people who created the
Megaminx. It was about the same size as a 4 x 4 x 4, with
slightly smaller cubies. It had never been devirginized, nor
did its owner want it to be. The face coverings are of the
same material as the coverings of the Megaminx. No clue as to
how it operates, although looking at the black surface exposed
by partial twists, there seemed to be new techniques involved, of
protuberances coming down from cubies sliding behind other
cubies, at least. Although stated to be a prototype, it seemed
completely developed, and I would expect to see it available
soon.
Date: 24 Feb 1983 0618-PST
From: JAY
Subject: NxNxN: Finite N
To: cube-lovers@MIT-MC
I have a program, not finished, which allows manipulation of a NxNxN
(N^3) cube. Presently it WILL manipulate any NxNxN cube (i tried up
to 23) but it has a VERRY BAD user interface. I plan to improve the
interface in the near future (this morning?) I hope to be able to
parse the Cube-Talk mentoined in the first message in the archive
alan;cube mail1 (or 2?), or a super-set of it (like being able to save
cube's on disk, save move seq's (macros), defining macros with
parameters, and make logfiles of especialy hairy session). As for
output... For small cubes (up to 8^3) i can use the normal air-plane
pattern of display, for medium cubes (8^3 <= size <= 12^3) i can put it
all on the normal terminal, but for larger cubes (24^3 >= cube >=
12^3) all i can do is display a face, or maybe two.
[Implementation]
I am interested in a, WORKING, N^3 simulator, not speed or space. As
a result my representation of the cube is loosing on both counts.
(yes it realy is a NxNxN array of cubes (a record of six integers!))
It is written in CLU for TOPS-20 os.
However my rep. brought up an interesting super-groop, immagin a cube
realy made of N^3 cubies. Each of these cubies would be a 'Miniature'
N^3 in color scheme. Now this new device (a 'compleatly colored'
cube) is solved only when ALL cubies are oriented correctly (ie. all
have red up and blue forward), and positioned correctly. In the 3^3
we would not only have to solve the centres, but also the imaginary
inside cubie (is it ever un-solved?)
[Questions]
What do you (readers) think is a good display scheme for a N^3,
remember it should be useable on a 24x80 h19? Is a N^3 simulator even
interesting? What sort of speed improvement could be gained from a
comp-cube? with or without macros?
Is the 'compleatly colored' cube interesting? For what sizes is it
similar to the 'partialy colored' (normal) cube (1^3 and 2^3 for
sure...)? Could the solution of compleat-5^3 be a solution of the
outer shell, and the inner 3^3?
Is a simulation of a 'compleatly colored' cube interesting? How
would one view the manny inside faces?
What other reps for the cube are there? (other than the obvious two;
an array of color tabs, or a 3d array of cubies..) Which reps
optimize storage, time, or simplicity to compute a twist, or even ease
of compairison? Just occured to me that each cubie could be rep'd as
a number twixt 1 and 24 (as a cube has only 24 orientations). This
optimization would reduce storage by a factor of 6 (not too bad!)
enough..... enough.....
j'
-------
Date: 24 February 1983 1815-EST (Thursday)
From: Dan Hoey at CMU-CS-A
To: Cube-Lovers at mit-mc
Subject: Whole-Cubing
Message-Id: <24Feb83 181536 DH51@CMU-CS-A>
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: 24 May 1983 2218-EDT
From: James.Saxe@CMU-CS-A (C410JS30)
To: Cube-Lovers@MIT-MC
Subject: Cubists do it . . .
Message-Id: <24May83.221845.JS30@CMU-CS-A>
. . . in over three billion positions.
Date: 25 May 1983 1001-PDT
Sender: OLE at SRI-CSL
Subject: Anybody there?
From: Ole at SRI-CSL (Ole J. Jacobsen)
To: Cube-Lovers at MIT-MC
Cc: Alan at MIT-MC
Message-ID: <[SRI-CSL]25-May-83 10:01:13.OLE>
Several months have gone by without a word from this list.
Have we lost our interest (or have I been removed from the
list)!?? What about the 5x5x5 that somebody reported having
actually touched, anyone seen any on sale?
Regards,
|-+-+-|
|O+L+E|
|O+L+E|
|O+L+E|
|-+-+-|
Date: 25 May 1983 20:17 EDT
From: David C. Plummer
Subject: Anybody there?
To: Ole @ SRI-CSL
cc: CUBE-LOVERS @ MIT-MC, ALAN @ MIT-MC
Date: 25 May 1983 1001-PDT
From: Ole at SRI-CSL (Ole J. Jacobsen)
Several months have gone by without a word from this list.
Have we lost our interest (or have I been removed from the
list)!??
I don't know that much of interest has happened. Maybe I'll find
a little time some year and try a couple things.
What about the 5x5x5 that somebody reported having
actually touched, anyone seen any on sale?
It will never be sold in mass. MANY stores are stuck with 4x4x4s
that nobody will buy.
Date: Thu 26 May 83 09:27:30-PDT
From: ISAACS@SRI-KL.ARPA
Subject: anybody there; 5x5x5; circular
To: cube-lovers@MIT-MC.ARPA
There doesn't seem to be much happening with the cube, but the (at least)
3 newletters are still being published. Ideals "Rubik's Cube Newsletter" no.
3 came, marked winter, 1983. Mostly about contests, also an article on
computer cubing and the calendar cube. Rubik's magazine from Hungary is
also on issue 3, with article on contests, other games and toys, and a little
bit of mathematics. Singmasters "Cubic Circular" is on issue 5/6 (phisically,
the forth issur), and is the best of the lot mathematically. He describes
and talks some about rotating rings, about Tsukuda's square (and how to
solve it), generalized Hungarian rings, the Incredi-ball (equivalent
to the corners of a Magic Dodecahedron without centers?? anyway, about
2*10**25 positions), rotating rings of cubes and tetrahedra (STarburst,
Kaleido Puzzle, etc), some notes on the 4x4x4 (his suggested order: 2
opposite face centers, say L and R; Pair up and place the F,C,B edge
pairs on the L & R faces; D corners; Pair up FD & store them, then pair BD
edges, then put these edge pairs in place; check parity of U corners - if
odd, apply U; 3-cycle U edges to get UR & UL edge pairs; EXAMINE, carefully,
the parity of the 4 edge pieces at UF&UB - if odd, r2D2l'D2r2, which 4 cycles
these edges; get all edges together and place; do U corners; do centers with
3-cycles like [[r,b],U]. phew. If people are interested, he gives
slightly more information on his method, also "Useful moves", and some other
strategies taken from the literature. He talks about "Evisceration",
that is, the principle of Duality, that if you replace capitals with small
letters and vice versa, in any move sequence, you turn the cube inside out -
corners become invisable centers, edges become face centers, etc. Singmaster
uses this to transfer knowledge of 3x3x3 to 4x4x4. He guesses the minimum
for God's Algorithm on the 4x4x4 to be about 44 "hand moves" or 66
quarter turns. (question, from DS: how should we count moves? "r" is
really 2 hand moves - Rr followed by R' - while Rr and even Rrl' could be
counted as a single move.) The circular talkes about Pyraminx, and gives
God's Algorithm as between 8 and 17 moves; there was some work on that done
in the Journal of Recreational Mathematics (a minimum solution was
presented), but I can't find the issue right off hand. Also a bunch of
Pyraminx patterns are given. There is an article on the prehistory of
the cube,and a little on the legal problems. Anyway, this parenthetical
paragraph is way out of hand - if anybody wants more, or more organized,
on the Circular, let me know.)
The 5x5x5: Yes, I saw one and played with it (a very little bit) at
Jerry Slocums' puzzle party. I also got an add from Meffert for one, and
have sent him my money, but it hasn't come yet. Neither has my Skewb, for
which I sent money half a year ago or so.
What else is new? Well, nothing much. Sales in the stores are slow,
and the number of puzzles available has lessened. Doug Engels rotating
circles are ready for production, and his manufacturer is mainly waiting
for the "right time" to release them. (These are 2 overlapping rotating
circles, with 3 piece overlap and 21 pieces all together.) He is trying
to decide between 2 colorings; if he choses the more difficult one, it
is a fairly hard puzzle, very cube like, but harder to get the already
solved pieces "out of the way".
Sorry this turned out so long and rambling - I was just going to
write a short note, and got carried away. Happy puzzling.
-- Stan
-------
Date: 26 May 1983 23:44 EDT
From: Alan Bawden
Subject: [DCP: 5x5 cubes]
To: CUBE-LOVERS @ MIT-MC
Date: Thursday, 26 May 1983 13:20-EDT
From: DCP at SCRC-TENEX
To: Bernard S. Greenberg
cc: ALAN, cmb at SCRC-TENEX
Re: 5x5 cubes
Date: Thursday, 26 May 1983, 10:02-EDT
From: Bernard S. Greenberg
From: David C. Plummer
What about the 5x5x5 that somebody reported having
actually touched, anyone seen any on sale?
It will never be sold in mass.
What, pray tell, are the details and source of this information?
As if there were anything I could do with it other than stare at it...
A person at Games People Play believes Ideal will never produce a
5x5x5 commercially. He believes the only people that seriously
bouhght the 4x4x4 were those that solved the 3x3x3 without a solution
book. He finally said he is stuck with many 4x4x4 that he fears he
won't be able to get rid of. The economics of making a 5x5x5 just
don't sound very good.
Date: Tue 31 May 83 09:52:44-PDT
From: ISAACS@SRI-KL.ARPA
Subject: economics
To: cube-lovers@MIT-MC.ARPA
Meffert claimed in an early letter, that he could produce his strange
products (Skewb, 5x5x5, and many others) if he had some not-to-big number
of guaranteed sales, on the order, if I remember, of 1000 or so. He has
a "club", that is, we paid about $10 to him up front. Then, when he is
"ready" with something, he sends an order form; they cost about $20 or so.
So far, he has done this with the Skewb, about 5 months ago, and the 5x5x5
recently. However, we have not actually received either of these yet.
I talked to about 3 other people who ordered them and have not received
them. So we don't actually know whether this system will work. We know
he has produced real, working prototypes, though, since we have seen them.
If they ever do come, I'll put up a message here. (Assuming I still
have access to this list.)
-- Stan
-------
Date: 1 June 1983 1939-EDT (Wednesday)
From: Dan Hoey@CMU-CS-A
To: cube-lovers@MIT-MC
Subject: Eccentric Slabism, Qubic, and S&LM
Message-Id: <01Jun83.193917.DH51@CMU-CS-A>
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: Wed 22 Jun 83 09:54:45-PDT
From: ISAACS@SRI-KL.ARPA
Subject: 5x5x5 and "bricks"
To: cube-lovers@MIT-MC.ARPA
I got my 5x5x5 today, from Meffert in Hong Kong. Whether they will
appear in regular (puzzle) stores, I don't know, but I would assume they will
be available from him. His address is
Puzzles Club
P.O.Box 31008
Causeway Bay
Hong Kong.
I haven't had a chance to do much with it yet; it seems well and strongly
made. I have not taken it apart because I don't know how to do it safely.
The corners seem to have the usual flanges. The center edges seem to have
a very deep tab, perhaps to go completely through the second layer. The
non-center middle pieces seem to be some kind of "caps" over the edge
extensions. That's all I can tell from "peeking" in the cracks.
One of the suggestions in Singmaster's "Cubic Circular" was to take
a regular 3x3x3 and tape over some cracks to limit the movement. The idea
is to take each pair of cubies and tape them together into one "brick", 2x1x1.
If you do it right, it makes a very interesting variation. For taping, I used
labels from another cube; that way the colors can be make to look right.
The pattern I used is as follows:
Choose a corner. It will be the only single cubie (except for a center).
Make the other 2 cubies along each edge projecting from the chosen corner,
into one brick (by putting tape on both cracks separating the cubies).
Now, in each of the 3 faces bordering the chosen corner are 4 untaped
facies in a square. Tape to make 2 adjacent bricks (don't forget the
other side of the edge bricks). Note that when you have done the first
face, you will have 3 parallel bricks; the other 2 faces should have
their parallel bricks with the "same handedness" - If you look down from
the chosen corner, the 3 faces should have rotational symmetry. (I haven't
tried an irregular pattern yet; it might have different properties than
this one). Anyway, all that is left is a 2x2x2 sub-cube, diagonally
across from the original chosen corner. Picture that as 4 1x1x2 bricks
piled with one pair crossways from the other. One brick, of course, includes
the very center of the cube (invisible), and will leave the only other untaped
facie - namely one center. Which one is the center doesn't matter, but I
think there is a clockwise/counter-clockwise (relative to the outer handedness)
choice here.
When all that is done, you will have a very interesting new puzzle. Any
twist must include the chosen corner! Home position is easy to recognize -
it is when the chosen corner is back in its original place, and the bricks
around it are in their positions (not necessarily with the correct colors
together). I have not solved it yet, but it seems that the sub-cube is
both hard to mix up, and easy to fix once you have. It looks as if all the
interesting moves can be done with just the 3 faces surrounding the chosen
corner.
Have fun..
-- Stan
-------
Date: 23 Jun 83 12:20:43-EDT (Thu)
From: Stuart Stirling
Return-Path:
Subject: Singmaster's "Cubic Circular"
To: cube-lovers@Mc
Cc: silver.Emory@Rand-Relay
Via: Emory; 23 Jun 83 23:31-PDT
Where is this available?
Stuart Stirling {sb1,sb6,msdc,gatech}!emory!silver
Math and Computer Science silver.emory@rand-relay
Emory University
Atlanta, GA 30322 404/329-5637
Date: 27 June 1983 19:04 EDT
From: Alan Bawden
Subject: Bizarre Bricks
To: CUBE-LOVERS @ MIT-MC
A bizarre variant of the "bricks" described by Isaacs last week is
currently sitting on the front desk of the SIPB office at MIT. Imagine
that you took three cubies along any edge of a cube and welded them
together (perhaps by taping over the cracks as Singmaster suggests). Now
imagine that you perform the same mutilation on a second cube. Now imagine
that you arrange to \share/ the same 1 x 1 x 3 cubie between the two cubes.
The resulting arrangement looks like this from above:
XXX
XXX
XXXXX
XXX
XXX
A moment's thought should convince you that sharing the 1 x 1 x 3 cubie has
done \nothing/ to increase the difficulty of the puzzle. Amazing what
lengths puzzle manufacturers will go to to try and squeeze a few more bucks
out of the Cube Craze.
Date: Tue 28 Jun 83 09:04:29-PDT
From: ISAACS@SRI-KL.ARPA
Subject: Cubic Circular address
To: silver.emory@RAND-RELAY.ARPA
cc: cube-lovers@MIT-MC.ARPA
The address for the "Cubic Circular" is indeed that of David Singmaster:
David Singmaster
87 Rodenhurst Road
London, SW4 8AF ENGLAND.
Hope this helps.
-- Stan
-------
Date: Thu 30 Jun 83 10:07:06-PDT
From: ISAACS@SRI-KL.ARPA
Subject: double cube
To: alan@MIT-MC.ARPA
cc: cube-lovers@MIT-MC.ARPA
I've heard of the double cube - do you have any idea where to buy one?
Another strange cube I've seen, is a normal 3x3x3 with extra cubies glued on
three faces so that it looks like a 4x4x4; of course, it twists in a very
lopsided manner. The main problem in making one (which I have not solved)
is how to grind or cut the flanges off cubies before gluing. Without
equipment, can anyone think of a good, practical way to do this?
-- Stan
-------
Date: 30 June 1983 20:47 EDT
From: Alan Bawden
Subject: [Barry Margolin: double vision]
To: CUBE-LOVERS @ MIT-MC
Date: 30 June 1983 16:57 edt
From: Barry Margolin at MIT-MULTICS
To: Alan Bawden
Re: double vision
Well, I got it at the Harrod's department store in London (they say you
can buy ANYTHING at Harrod's). I was in Games People Play last week and
didn't see it, so maybe it hasn't gotten to this country yet.
Sorry I can't be of more help.
barmar
Date: 21 July 1983 1450-PDT (Thursday)
From: cline at AEROSPACE (Ken Cline)
Subject: put me on your mailing list!
To: cube-lovers at mit-mc
Please include me (CLINE@AEROSPACE) in your Rubik's Cube mailing-list.
My address will change in September to SCGVAXD!4CCVAX!KCLINE@CIT-VAX,
but I will let you know when this occurs.
Thank you,
Ken Cline
Date: Monday, 21 November 1983 10:08-EST
To: cube-lovers at mc
From: BSG
Subject: Meffert cube availability
Someone asked me from afar where to get the hairy Meffert
cube-like things. It was a long time ago that I ordered a
five-cube from somewhere in Los Angeles. Would somebody care to
repeat the name and address of that store, or some other stores?
Thank you.
Date: 21 November 1983 20:30 EST
From: Alan Bawden
Subject: Rubik's cube cornered
To: CUBE-LOVERS @ MIT-MC
>From mit-eddie!genrad!decvax!dartvax!andyb Tue Oct 25 00:03:36 1983
Relay-Version: version B 2.10.1 6/24/83; site mit-vax.UUCP
Path: mit-vax!mit-eddie!genrad!decvax!dartvax!andyb
From: andyb@dartvax.UUCP
Newsgroups: net.puzzle
Subject: Rubik's cube cornered
Message-ID: <307@dartvax.UUCP>
Date: Tue, 25-Oct-83 00:03:36 EDT
Article-I.D.: dartvax.307
Posted: Tue Oct 25 00:03:36 1983
Date-Received: Tue, 25-Oct-83 08:53:25 EDT
Lines: 7
It is possible to solve the corners of the Rubik's Cube in no more
than 11 turns. Over 4/5 of all possible patterns can be solved in
9 turns or fewer, but over half take a full 9 turns. Ten turns are
enough to solve more than 99.9% of all scrambled states. (Only
2,644 states require 11 turns).
This from L. John Kelley, solver of the Magic Pyramid.
Date: 23 November 1983 17:01 EST
From: Alan Bawden
Subject: [genrad!decvax!dartvax!andyb: Rubik's cube cornered]
To: CUBE-LOVERS @ MIT-MC
Date: 23 Nov 1983 06:56:09-EST
From: genrad!decvax!dartvax!andyb at mit-eddie,
Received: by decvax.UUCP (4.12/4.2)
id AA26306; Wed, 23 Nov 83 03:10:45 est
Date: Wed, 23 Nov 83 03:10:45 est
From: decvax!dartvax!andyb
Message-Id: <8311230810.AA26306@decvax.UUCP>
To: decvax!genrad!mit-eddie!ALAN@MIT-MC, genrad!decvax!dartvax!andyb@MIT-EDDIE
Subject: Rubik's cube cornered
Cc: ALAN@MIT-MC
Alan:
Feel free to rebroadcast any of this discussion to the cube-lovers list.
(Could you enroll me on the list, also?)
Both solutions were generated by "brute force", using a fairly short PL1
program running on a VAX. The solutions are tables which express the
information "if the pyramid/cube's state is X, the best move is Y" for all
possible states. In that sense, they are optimal solutions, but if you wanted
to know the best solution for any particular state, you would have to carry the
entire table around with you. Perhaps we could publish the list :-)
The Magic Pyramid is the one sold under the name "Pyraminx" -- it's the
tetrahedron that rotates in only 4 planes.
The cube solution is for corners only, with no reference to centers or edges.
You could think of it as a complete solution to the "Pocket Cube", which is
a 2x2x2 cube.
Glad to help.
Andy Behrens (& L. Kelley)
decvax!dartvax!andyb
Date: Sat 26 Nov 83 22:35:59-EST
From: Tai
Subject: cube solvers
To: cube-lovers@MIT-MC.ARPA
cc: Jin@COLUMBIA-20.ARPA
hi, are there any programs out there that solve the cube? i would like
to get a copy of the source if possible. also, are there any general
methods for solving the cube?
thanks...tai
-------
Date: 29 February 1984 23:08-EST
From: Alan Bawden
Subject: [CL.BOYER: A Programming Language for Group Theory (Dept. of Math)]
To: CUBE-LOVERS @ MIT-MC
Some of the group theory hackers amoung us might be interested in this
abstract. Of course the talk has already happened, but perhaps one of you
knows more about this?
Date: Sun 26 Feb 84 17:06:23-CST
From: Bob Boyer
To: AIList
Re: A Programming Language for Group Theory (Dept. of Math)
[Forwarded from the UTexas-20 bboard by Laws@SRI-AI.]
DEPARTMENT OF MATHEMATICS COLLOQUIUM
A Programming Language for Group Theory
John Cannon
University of Sydney and Rutgers University
Monday, February 27, 4pm
The past 25 years has seen the emergence of a small but vigorous branch of
group theory which is concerned with the discovery and implementation of
algorithms for computing structural information about both finite and infinite
groups. These techniques have now reached the stage where they are finding
increasing use both in group theory research and in its applications. In order
to make these techniques more generally available, I have undertaken the
development of what in effect is an expert system for group theory.
Major components of the system include a high-level user language (having
a Pascal-like syntax) and an extensive library of group theory algorithms. The
system breaks new ground in that it permits efficient computation with a range
of different types of algebraic structures, sets, sequences, and mappings.
Although the system has only recently been released, already it has been
applied to problems in topology, algebraic number theory, geometry, graphs
theory, mathematical crystalography, solid state physics, numerical analysis
and computational complexity as well as to problems in group theory itself.
Received: From ti-csl.csnet by csnet-relay; 25 Jun 84 20:44 EDT
Date: Mon, 25 Jun 84 14:30 CST
From: Gil Gamesh
To: cube-lovers@mit-mc.arpa
Subject: Recent Activity?
Is this mailing list still alive? Does anyone know of any
recent activity in the cube world? Are there still any
Cube Newsletters that anyone knows of? Has anyone ever seen
any of the many puzzles I read about in places such as 'Scientific American' and 'Omni', ex.
the Skewb, the Double Pyramid, the 5x5x5 cube, etc.?
Dan Nichols
Dnichols.ti-csl@csnet-relay
Date: Tue 26 Jun 84 11:00:18-PDT
From: ISAACS@SRI-KL.ARPA
Subject: cubes dead?
To: cube-lovers@MIT-MC.ARPA
I don't see much about cubes these days. And, as a puzzle collector, I'm still
looking. Singmaster and Ideal have both discontinued their newsletters;
however, the Hungarian "Rubics Magazine" still is being published. It has
broadened somewhat to talk more about puzzles in general. I also found last
Saturday, that there is a childrens cartoon about Rubics Cube - in fact
the cube is the hero. It is truly awful.
As Alan says, most of the objects mentionsed have been seen. But they
are hard to get nowadays. Meffert, in Hong Kong, is silent. I ordered
a dozen or so 5x5x5's more than 6 months ago, and have yet to hear anything.
Or get my money back. And he never sent me any skewbs.
Well, it was an exciting couple of years in the puzzle world; now, I guess,
things are more normal. Stores no longer have puzzle sections, and I have to
write to specialty places to find new puzzles. For me, wood puzzles are back
in. I've been digging up old puzzle patents, and hope to find someone to make
some of the puzzles described for me.
-- Stan Isaacs
(isaacs@hplabs)
-------
Received: from SCRC-CONCORD by SCRC-STONY-BROOK via CHAOS with CHAOS-MAIL id 54973; Tue 26-Jun-84 10:22:30-EDT
Date: Tue, 26 Jun 84 10:20 EDT
From: "Bernard S. Greenberg"
Subject: Recent Activity?
To: ALAN@MIT-MC.ARPA
cc: cube-lovers@MIT-MC.ARPA
In-Reply-To: The message of 25 Jun 84 23:23-EDT from Alan Bawden
Message-ID: <840626102050.3.BSG@CONCORD.SCRC.Symbolics>
Date: 25 June 1984 23:23-EDT
From: Alan Bawden
Date: Mon, 25 Jun 84 14:30 CST
From: Gil Gamesh
Subject: Recent Activity?
Is this mailing list still alive? Does anyone know of any recent activity
in the cube world?
More significantly, has anyone heard of any progress in the
important theoretical problems (God's number/algorithm)?
Date: 28 June 1984 00:17-EDT
From: Alan Bawden
Subject: The Cube meets Massive Parallelism
To: CUBE-LOVERS @ MIT-MC
cc: CM-I @ MIT-MC
In-reply-to: Msg of Tue 26 Jun 84 10:20 EDT from Bernard S. Greenberg
Since I spend most of my time these days thinking about designing and
programming massively parallel computers, it occured to me to think about
applying such machines to exploring the Cube's Group. Here are some
preliminary thoughts.
When we say "massively parallel" we are talking at least a quarter million
simple processors. This is enough processors to give all of the positions
5 or fewer quarter twists away from home their own processor. A million
processors would be enough to get up to 6 Qs, but lets not push our luck.
Given a machine like the MIT Connection Machine we could set up a database
in which every processor representing a configuration knew the addresses ot
the 12 other processors representing its 12 closest neighbors, in almost no
time at all. (Processors 5 Qs away from home would have null pointers for
their unrepresented 6 Q neighbors.) A conservative statement would be
that operations like generating a list of all identities of length 10 or
less (which has previously taken us hours to accomplish) could be done so
fast that the machine could generate output faster than you could read it.
Since this is all so absurdly easy, there must be ways to go beyond this to
generate significant new results using this (promised) new kind of
hardware. Perhaps Dave Christman, who is both a cube hacker, and a
designer of algorithms for massively parallel machines, could be persuaded
to devote some spare cycles to figuring out ways to brute-force the Cube
using such a machine.
Date: Fri 13 Jul 84 15:24:23-PDT
From: Micheal Hewett
Subject: Please add me to your mailing list
To: cube-lovers@MIT-MC.ARPA
Thanks.
Mike Hewett (HEWETT@SU-SCORE.ARPA)
-------
Date: Tue 24 Jul 84 15:30:18-PDT
From: Haym Hirsh
Subject: God's number
To: cube-lovers@MIT-MC.ARPA
Can anyone verify a rumor - that some Princeton student, as an
undergraduate thesis, solved the problem of how far from start one
can get (i.e., the longest sequence God's algorithm would give for
any position)? The number I heard was 26.
Haym
-------
Date: 1 Aug 1984 11:57-EDT
From: Dan Hoey
Subject: Pocket cube program
To: cube-lovers at mit-mc
The UNIX-SOURCES@BRL mailing list recently forwarded this note from
Usenet.
Date: Tue, 31 Jul 84 13:47:22 EDT
From: news@BRL-TGR.ARPA
Subject: /usr/spool/news/net/sources/397
Path: brl-tgr!seismo!hao!hplabs!zehntel!ihnp4!ihnet!eklhad
From: eklhad@ihnet.UUCP (K. A. Dahlke)
Subject: solve the 2x2x2 Rubix cube in a minimum number of moves
Date: Mon, 30-Jul-84 10:49:48 EDT
Article-I.D.: ihnet.142
Organization: AT&T Bell Labs, Naperville, IL
After solving the Rubix cube 4 years ago, I turned my attention to
more interesting (and more difficult) questions.
How can one find the minimum path solution for an arbitrary position?
How far away is the farthest positions?
Is there one position diametrically opposed to start,
or does it fan out into billions?
Recently, I have started playing again, and have made some progress.
Here is a computer program (C/unix) which solves the 2x2x2 cube
in a minimum number of moves.
The 2 cube is not as common as the 3 cube, but it is commercially
available.
If you only have a 3 cube (standard), just ignore the sides and centers,
and use the corners.
This effectively simulates a 2 cube.
Thanks to ATT-BL for the use of their computing facilities.
Later versions may come, if i am ambitious.
Unfortunately, my program cannot be expanded to handle the 3 cube.
Nobody has that much memory/CPU time.
I will have to come up with something better.
Feel free to contact me with any ideas about this subject.
----------------------------------------------------------------
The note is followed by about 1000 lines of c code that I can make
available if you want it.
Unfortunately, the program seems to believe that there are 870 * 729 =
634230 positions of the 2^3, while assiduous cube lovers realize the
number is actually (7! / 2) * 3^6 = 2520 * 729 = 1837080 positions.
The number 870 = 29 * 30 is strange. I guess it is an approximation of
6! + 5! + 4! + 3! + 2! = 872, since the code for encoding a position as
an integer contains a table of those factorials.
Dan
Date: 7 Aug 1984 19:24-EDT
From: Dan Hoey
Subject: The pocket cube: correction, calculation, and conjectures
To: cube-lovers at MIT-MC
Well, maybe this list is dead after all, if I can tell you there are
(7!/2)(3^6) positions of the pocket cube, and have it stand for a week.
The correct number is of course (7!)(3^6) = 3674160, since the
generators are odd.
But not being one to eat crow with a straight face, I have hacked the
good hack, so I can give you the exact number P(N) of pocket cube
positions exactly N quarter-turns from solved. (This was done in
September 1981 for the half-twist metric; see the archives.) I have
also computed the number L(N) of local maxima at each distance. These
numbers are given below.
N P(N) L(N)
0 1 0
1 6 0
2 27 0
3 120 0
4 534 0
5 2256 0
6 8969 0
7 33058 16
8 114149 53
9 360508 260
10 930588 1460
11 1350852 34088
12 782536 402260
13 90280 88636
14 276 276
An approach for dealing with these numbers (suggested to me by Dale
Peterson) is to form the Poincare polynomial
p(x) = SUM P(i) x^i
i
in hopes that it can be factored nicely. Unfortunately, this doesn't
work out--with the exception of the obvious factor (x+1), p(x) is
irreducible. I have also tried to decompose p(x) using the power
(1+x)^2
series for ------------, which agrees with the first five terms of p(x)
3 - 2(1+x)^2
due to the lack of non-trivial identities. I haven't found any good
ways of expressing p(x), but there may be something there. The point
of all of this is that it could conceivably lead to a conjecture--or
even a derivation--of God's number for the 3^3 puzzle.
I might pass along another fuzzy recollection from a year and a half
ago, in hopes that it is more informative than incorrect. Dale
mentioned another classical method for dealing with group diameters.
It seems there is a class of groups, called reflection groups, for
which tight diameter bounds can be derived. A reflection group is a
group of matrices with eigenvalues of plus and minus one. Some
properties generalize to pseudo-reflection groups, where the
eigenvalues all have complex magnitude one. We managed to construct
isomorphisms between the 3^3 edge group and a reflection group, and
between the corner group and a pseudo-reflection group. As I recall,
he was fairly certain that the full cube group did not qualify, but
that was beyond my depth.
So if you think cubes are dead, remember it's not because the
results are all in.
Dan
Date: 20 Aug 1984 4:34-EDT
From: Dan Hoey
Subject: The pocket cube and corners of the full cube
To: cube-lovers at mc
Cc: umcp-cs!seismo!ihnp4!ihnet!eklhad at NRL-AIC
Karl Dahlke, the author of the pocket cube program I mentioned on 1
August, sent me a note about the appearance of the unusual constant 870
in his program. It turns out that the program is correct, and the
constant arises in an interesting way.
Recall that the pocket cube has 729 orientations and 5040 permutations
of the pieces. Dahlke had noticed that the ``reflections and
rotations'' of a position need not be stored, since they are the same
distance from start. By reflections and rotations, he means the
S-conjugates, where S is the six-element symmetry group of the pocket
cube with one corner fixed.
It turns out that the pocket cube has 2 permutations with a six-element
symmetry group, 16 permutations with a three-element symmetry group,
138 permutations with a two-element symmetry group, and 4884
permutations with a one-element symmetry group. Thus the number of
permutations that are distinct up to S-conjugacy is 2 + 16/2 + 138/3 +
4884/6 = 870.
This discussion of symmetry recalls a question I have meant to propose
to Cube-Lovers for some time: How many positions are there in Rubik's
Cube? We know from Ideal that the number is somewhat over three
billion. Most cube lovers will tell you a number of about 43
quintillion. But I really don't see why we should count twelve
distinct positions at one quarter-twist from solved--all twelve are
essentially the same position. So the question, suitably rephrased, is
of the number of positions that are distinct up to conjugacy in M, the
48-element symmetry group of the cube. I think this is an interesting
question, but I don't see any particularly easy way of answering it.
My best guess is that it involves a case-by-case analysis of the 98
subgroups of M, or at least the 33 conjugacy classes of those
subgroups. In ``Symmetry and Local Maxima'', Jim Saxe and I examined
five of the classes, which we called M, C, AM, H, and T.
Even finding the numbers for the pocket cube is a little tricky. If we
limit ourselves to symmetry in S, I believe the pocket cube has 2
positions with a six-element symmetry group, 160 positions with a
three-element symmetry group, 3882 positions with a two-element
symmetry group, and 3670116 positions with a one-element symmetry
group, for 613062 positions distinct up to S-conjugacy. But the
numbers for M-conjugacy are still elusive; I am not even sure how to
deal with factoring out whole-cube moves in the analysis. I hope to
find time to write a program for it.
I expanded my pocket cube program to deal with the corner group of
Rubik's cube. This group is 24 times as large as the group of the
pocket cube, having 3^7 * 8! = 88179840 elements. The number of
elements P(N) and local maxima L(N) at each (quarter-twist) distance N
from solved are given below.
N P(N) L(N)
0 1 0
1 12 0
2 114 0
3 924 0
4 6539 0
5 39528 0
6 199926 114
7 806136 600
8 2761740 17916
9 8656152 10200
10 22334112 35040
11 32420448 818112
12 18780864 9654240
13 2166720 2127264
14 6624 6624
The alert reader will notice that rows 10 through 14 contain values
exactly 24 times as large as those for the pocket cube. This is not
surprising, given that the groups are identical except for the position
of the entire assembly in space, and each generator of the corner cube
is identical to the inverse of the corresponding generator for the
opposite face except for the whole-cube position. Thus when solving a
corner-cube position at 10 qtw or more from solved, it can be solved as
a pocket cube, making the choice between opposite faces in such a way
that the whole-cube position comes out right with no extra moves.
Dan
Date: 22 Aug 1984 18:06-EDT
From: Dan Hoey
Subject: An outer automorphism of the cube group
To: cube-lovers at mit-mc
If you have a Rubik's cube where all the edges flip on each
quarter-turn, you can solve it by using bifocals when it's odd.
I noticed this while drawing a Hasse diagram of the subgroups of M. It
turns out that M has a similar automorphism, where the odd elements are
reflected through the center of the cube.
If anyone wants the Hasse diagram, I can send it--it takes about 30
minutes to draw in the lines, for which directions are included.
If you know whether there are other outer automorphisms of M, please
let me know.
Dan
Date: Fri, 7 Sep 84 9:16:44 EDT
From: Michael Frishkopf
Subject: list request
To: CUBE-LOVERS@mit-mc.arpa
Cc: mfrishkopf@BBNCCY.ARPA
Dear sir/ms:
Please place me on your arpa mailing list:
mfrishkopf@bbnccy
Thank you,
Michael Frishkopf
Received: by gyre.ARPA (4.12/4.7)
id AA09303; Mon, 1 Oct 84 21:10:44 edt
Date: Mon, 1 Oct 84 21:10:44 edt
From: Rehmi Post
Message-Id: <8410020110.AA09303@gyre.ARPA>
To: cube-lovers@mc
Subject: Archives
Does anyone have copies (partial or otherwise) of the cube-lovers mailing
list? I need it as a reference generator/thought provoker, and if I could
ftp it all from someone, it'd be nice...
- rehmi at maryland
Date: 5 October 1984 17:07-EDT
From: Alan Bawden
Subject: Moleculon wins a round!
To: CUBE-LOVERS @ MIT-MC
From today's Boston Globe:
DOVER, Del. --- A massachusetts firm that claimed it had the first patent
on the Rubik's cube puzzle has won a patent infringement suit against CBS
Inc. and its subsidiary Ideal Toy Corp., which manufactures the puzzle. US
District Court Judge Walter Stapleton issued the ruling Tuesday, validating
the patent held by Moleculon Research Corp. of Cambridge, Mass. The ruling
said CBS infringed on the patent with its various Rubik's cube products.
Moleculon's attorney, Robert Perry, said if no appeal is filed, the case
would continue to a second trial to determine monetary damages. Moleculon
is seeking $60 million in damages and an undetermined amount in profits
from Rubik's cube and related sales.
Received: from CheninBlanc.ms by ArpaGateway.ms ; 08 OCT 84 08:57:05 PDT
Date: 8 Oct 84 08:58:06 PDT (Monday)
From: Lynn.es@XEROX.ARPA
Subject: Re: Moleculon wins a round!
In-reply-to: ALAN's message of 5 Oct 84 18:01 EDT
To: Cube-Lovers@MIT-MC.ARPA
cc: Lynn.es@XEROX.ARPA
A similar article in the LA Times went on to say that the fellow at
Moleculon had patented a 2x2 cube held together with magnets, but
mention was made in the patent of larger cubes and mechanical linkages.
How specific the mentions were is not clear. He was also quoted to the
effect that they do not dispute that Rubik invented the present cube,
but it infringes on their patent. Moleculon apparently offered to sell
rights to their toy to Ideal before Rubik and were turned down.
/Don Lynn
Received: from SCRC-DUPAGE by SCRC-STONY-BROOK via CHAOS with CHAOS-MAIL id 185428; Tue 26-Feb-85 11:09:54-EST
Date: Tue, 26 Feb 85 11:00 EST
From: Richard Pavelle *