From velucchi@cli.di.unipi.it Fri Jan 12 13:01:39 1996 Return-Path: Received: from mailserver.cli.di.unipi.it (alice.cli.di.unipi.it) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07886; Fri, 12 Jan 96 13:01:39 EST Organization: Centro di Calcolo - Dip. di Informatica di Pisa - Italy Received: from helen.cli.di.unipi.it (helen.cli.di.unipi.it [131.114.11.38]) by mailserver.cli.di.unipi.it (8.6.12/8.6.12) with ESMTP id SAA14090; Fri, 12 Jan 1996 18:27:05 +0100 From: Mario Velucchi Received: (velucchi@localhost) by helen.cli.di.unipi.it (8.6.12/8.6.12) id SAA29843; Fri, 12 Jan 1996 18:27:03 +0100 Message-Id: <199601121727.SAA29843@helen.cli.di.unipi.it> Subject: CUBE PUZZLE To: cube-lovers-request@ai.mit.edu Date: Fri, 12 Jan 1996 18:27:03 +0100 (MET) Cc: cube-lovers@ai.mit.edu X-Mailer: ELM [version 2.4 PL24] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 556 Dear FRIENDS, Is this list only for CUBE PUZZLE or PUZZLE in general? THANKS -- Yours Sincerely, MV \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\//////////////////////////////// Mario Velucchi University of PISA Via Emilia, 106 Department of Computer Science I-56121 Pisa e-mail:velucchi@cli.di.unipi.it ITALY talk:velucchi@helen.cli.di.unipi.it http://www.cli.di.unipi.it/~velucchi/intro.html \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\//////////////////////////////// From mark.longridge@canrem.com Sun Jan 14 22:25:30 1996 Return-Path: Received: from itchy.crso.com (itchy.canrem.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA20327; Sun, 14 Jan 96 22:25:30 EST Received: by canrem.com (PCB-UUCP 1.1f) id 206F74; Sun, 14 Jan 96 22:13:52 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Cube Theory From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.1278.5834.0C206F74@canrem.com> Date: Sun, 14 Jan 96 22:03:00 -0500 Organization: CRS Online (Toronto, Ontario) Here is some more Cube Theory: On the standard Rubik's Cube Using < R, L, F, B, U > to generate D1 Let A = R1 L3 F2 B2 R1 L3, then A U1 A = D1 A U1 A = R1 L3 F2 B2 R1 L3 U1 R1 L3 F2 B2 R1 L3 (17 q, 13 q+h) Using < R2, L2, F2, B2, U2 > to generate D2 Let A = R2 F2 B2 L2, then A U2 A = D2 A U2 A = R2 F2 B2 L2 U2 R2 F2 B2 L2 (18 q, 9 q+h) Slice group pattern, 6 spot, 4 slice moves p1 = (F1 B3) (L1 R3) (U1 D3) (F1 B3) (8 q) Slice group antipode, 6 spot + pons asinorum, 6 slice moves p2 = (F2 B2) (T1 D3) (F1 B3) (L3 R1) (T1 D3) (12 q) p2^6 = I p7a Cube in a cube U2 F2 R2 U3 L2 D1 (B1 R3) ^3 + D3 L2 U1 (15 q+h, 20 q) if A = U3 L2 D1, then let A' = inverse of A p7a = U2 F2 R2 + A + (B1 R3) ^3 + A' Or if we want something more symmetric, there is Mike Reid's... p7b Symmetric Maneuver (R3 U1 F2 U3 F3 L1 F2 L3 F1 R1 C_X ) ^ 2 (20 q+h , 24q) One might even call this maneuver to be "cyclic decomposable". Even the first half of this sequence generates an interesting pattern. It would appear that using symmetric maneuvers does not ensure minimal q or q+h turns. Perhaps p7a is simpler in terms of notational expression. p7a is how I actually do "Cube in a cube" in real cubing. Note also that p7a uses all 6 generators and p7b uses and there may be a tighter symmetric "Cube in a cube". Mike, have you tried using the pattern generated by the first half under your Kociemba algorithm for q turns?? ---------------------------------------------------------------------- Megaminx (platonic dodecahedron) 12 faces, 20 corners, 30 edges tetrahedron = 4 axis cube = 3 axis dodecahedron = 6 axis In constructing a dodecahedron, build a bottom, place the 5 adjacent faces to form a bowl. The top edges now form a skew decagon. Build another bowl and connect the two bowls together to form a dodecahedron. ------------------------------------------------------------- Recall that the Halpern-Meier Tetrahedron has 3,732,480 states. In this count we consider the 4 centre pieces immobile. The picture H-M tetrahedron has 3,732,480 * 3^3 = 100,776,960 states. In essence, we can rotate any 3 centres at will, the 4th is forced. That number may seem familar to some of the more fanatical cubists, has the picture Skewb has 3,149,280 * 2^5 = 100,776,960 states! Additionally the possible rotations of the centres of the H-M tetrahedron are (), (+ -), (+++) , (---), (-++-), (+--+), (+++-), (--+-) # Order (tetra, r * d) = 45 OR (r+ d+)^45 = I Note that (r+ d+)^45 is still the identity, even on the picture H-M tetrahedron, as 45 is divisible by 3. ------------------------------------------------------------- -> Mark <- From mreid@ptc.com Thu Jan 18 14:13:01 1996 Return-Path: Received: from poster (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA28413; Thu, 18 Jan 96 14:13:01 EST Received: from ducie.ptc.com by poster (5.x/SMI-SVR4-NN) id AA05671; Thu, 18 Jan 1996 14:08:43 -0500 Message-Id: <9601181908.AA05671@poster> Received: by ducie.ptc.com (1.38.193.4/16.2.nn) id AA06925; Thu, 18 Jan 1996 14:38:00 -0500 Date: Thu, 18 Jan 1996 14:38:00 -0500 From: michael reid To: cube-lovers@ai.mit.edu Subject: Re: Cube Theory mark writes [ ... ] > p7a Cube in a cube U2 F2 R2 U3 L2 D1 (B1 R3) ^3 + D3 L2 U1 > (15 q+h, 20 q) for what it's worth, on may 19, 1992, i gave the maneuver L1 F1 L1 D3 B1 D1 L2 F2 D3 F3 R1 U3 R3 F2 D1 (15f, 18q) which is minimal in both the face turn and the quarter turn metric. [ ... ] > Or if we want something more symmetric, there is Mike Reid's... > > p7b Symmetric Maneuver (R3 U1 F2 U3 F3 L1 F2 L3 F1 R1 C_X ) ^ 2 > (20 q+h , 24q) i think this maneuver is well-known, so it shouldn't be attributed to me. at least it seems to be a "standard" way of producing the cube in a cube pattern. [ ... ] > Mike, have you tried using the pattern generated by the first half > under your Kociemba algorithm for q turns?? do you mean the position generated by R3 U1 F2 U3 F3 L1 F2 L3 F1 R1 (which is just a three cycle of corner-edge pairs) ? this maneuver is minimal in both metrics. back in the days before i did computer-cubing, i found an interesting maneuver for "cube in a cube" that only turns three faces. what's the shortest such maneuver that you know? mike From mark.longridge@canrem.com Tue Jan 23 18:00:31 1996 Return-Path: Received: from itchy.crso.com (itchy.canrem.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA21009; Tue, 23 Jan 96 18:00:31 EST Received: by canrem.com (PCB-UUCP 1.1f) id 2081FF; Tue, 23 Jan 96 17:23:59 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: New Rubik's Cube Web Page From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.1281.5834.0C2081FF@canrem.com> Date: Tue, 23 Jan 96 17:19:00 -0500 Organization: CRS Online (Toronto, Ontario) I've started my own Web Page for Rubik's Cube. It has my rubik's chronology and full move list. Eventually all issues of Domain of the Cube will reside there! www.dis.on.ca/~cubeman email: mark.longridge@canrem.com or cubeman@admin.dis.on.ca -> Mark <- From mreid@ptc.com Mon Feb 5 16:05:20 1996 Return-Path: Received: from poster (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07090; Mon, 5 Feb 96 16:05:20 EST Received: from ducie.ptc.com by poster (5.x/SMI-SVR4-NN) id AA04779; Mon, 5 Feb 1996 16:00:57 -0500 Message-Id: <9602052100.AA04779@poster> Received: by ducie.ptc.com (1.38.193.4/16.2.nn) id AA23969; Mon, 5 Feb 1996 16:31:26 -0500 Date: Mon, 5 Feb 1996 16:31:26 -0500 From: michael reid To: cube-lovers@ai.mit.edu Subject: cube in a cube recently i wrote > back in the days before i did computer-cubing, i found an interesting > maneuver for "cube in a cube" that only turns three faces. what's the > shortest such maneuver that you know? there was never any response to this, but i'll give my solution anyway. let X = U2 F R' F2 R F2 R F2 R' F U2 . then X produces two two-cycles of corner-edge pairs. the commutator [ X , C_UFR ] produces "cube in a cube" in 22 face / 32 quarter turns and only turns the faces U, F and R. the notation C_UFR refers to a rotation of the whole cube, and [ a, b ] denotes the commutator a b a^-1 b^-1 . mike From rcs@cs.arizona.edu Mon Feb 5 18:19:06 1996 Return-Path: Received: from optima.cs.arizona.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA15372; Mon, 5 Feb 96 18:19:06 EST Received: from leibniz.cs.arizona.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA09076; Mon, 5 Feb 1996 16:19:05 MST Date: Mon, 5 Feb 1996 16:19:03 MST From: "Richard Schroeppel" Message-Id: <199602052319.AA10033@leibniz.cs.arizona.edu> Received: by leibniz.cs.arizona.edu; Mon, 5 Feb 1996 16:19:03 MST To: cube-lovers@ai.mit.edu Subject: Group/graph status? Has anyone tabulated the number of positions are reachable (from the initial cube) in one move, two moves, etc.? Is the diameter of the graph known? Rich Schroeppel rcs@cs.arizona.edu From news@nntp-server.caltech.edu Mon Feb 5 21:19:04 1996 Return-Path: Received: from gap (gap.cco.caltech.edu) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA25371; Mon, 5 Feb 96 21:19:04 EST Received: by gap (SMI-8.6/DEI:4.45) id SAA28438; Mon, 5 Feb 1996 18:18:22 -0800 To: mlist-cube-lovers@nntp-server.caltech.edu Path: whuang From: whuang@cco.caltech.edu (Wei-Hwa Huang) Newsgroups: mlist.cube-lovers Subject: Re: Group/graph status? Date: 6 Feb 1996 02:18:21 GMT Organization: California Institute of Technology, Pasadena Lines: 13 Message-Id: <4f6dpd$rok@gap.cco.caltech.edu> References: <199602052319.AA10033@leibniz.cs.arizona.edu> Nntp-Posting-Host: accord.cco.caltech.edu X-Newsreader: NN version 6.5.0 #12 (NOV) "Richard Schroeppel" writes: >Has anyone tabulated the number of positions are reachable (from the >initial cube) in one move, two moves, etc.? Is the diameter of the >graph known? Well, the diameter of the graph would obviously be the upper bound of God's algorithm. -- Wei-Hwa Huang, whuang@cco.caltech.edu, http://www.ugcs.caltech.edu/~whuang/ --------------------------------------------------------------------------- Did you know Africa has more sand than the entire Sahara Desert? From bagleyd@hertz.njit.edu Tue Feb 6 10:00:56 1996 Return-Path: Received: from hertz.njit.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA22364; Tue, 6 Feb 96 10:00:56 EST Received: (from bagleyd@localhost) by hertz.njit.edu (8.7.3/8.6.9) id JAA02959 for cube-lovers@life.ai.mit.edu; Tue, 6 Feb 1996 09:37:50 -0500 Date: Tue, 6 Feb 1996 09:37:50 -0500 From: bagleyd Message-Id: <199602061437.JAA02959@hertz.njit.edu> To: cube-lovers@life.ai.mit.edu Subject: xpuzzles and winpuzz Hi My new X-Windows puzzles are out again. Here's a brief description: 5.2 Puzzles now can change size dynamically. Puzzles for the most part have no maximum size. For example, you can have a 10x10x10 Rubik's cube. Saved format has changed on most puzzles, should be more understandable. Drag and drop on a face to move pieces now works on all puzzles. Lesstif-0.36 works OK with all puzzles. Lesstif still has many bugs but I have only seen cosmetic and bugs with radio buttons and sliders using the puzzles. Lots of minor bug fixes and minor improvements. MS Windows, port in progress, E-Mail author if interested They are still free and source code is still included. :) The best puzzles will be converted last, since they are more complicated. (xabacus -> wabacus: port complete (not a puzzle)) xcubes -> wcubes: port complete xtriangles -> wtriangl: port in progress Cheers, /X\ David A. Bagley // \\ bagleyd@hertz.njit.edu (( X xlockmore, new stuff for xlock @ ftp.x.org//contrib/applications \\ // altris, tetris games for x @ ftp.x.org//contrib/games/altris \X/ puzzles, magic cubes for x @ ftp.x.org//contrib/games/puzzles From JBRYAN@pstcc.cc.tn.us Tue Feb 6 12:24:07 1996 Return-Path: Received: from PSTCC4.PSTCC.CC.TN.US by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA02724; Tue, 6 Feb 96 12:24:07 EST Resent-From: JBRYAN@pstcc.cc.tn.us Resent-Message-Id: <9602061724.AA02724@life.ai.mit.edu> Received: from pstcc.cc.tn.us by pstcc.cc.tn.us (PMDF V5.0-3 #11457) id <01I0W5NR906Y8WWAHI@pstcc.cc.tn.us>; Tue, 06 Feb 1996 12:25:57 -0400 (EDT) Resent-Date: Tue, 06 Feb 1996 12:25:57 -0400 (EDT) Date: Tue, 06 Feb 1996 12:25:56 -0400 (EDT) From: Jerry Bryan Subject: Re: Group/graph status? In-Reply-To: <199602052319.AA10033@leibniz.cs.arizona.edu> Sender: JBRYAN@pstcc.cc.tn.us To: Richard Schroeppel Cc: cube-lovers@ai.mit.edu Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 7BIT On Mon, 5 Feb 1996, Richard Schroeppel wrote: > Has anyone tabulated the number of positions are reachable (from the > initial cube) in one move, two moves, etc.? Is the diameter of the > graph known? In the quarter turn metric, the number of positions has been tabulated out to eleven moves from Start. The diameter of the graph is known to be at least 24 quarter turns because there is one position whose length has been verified to be 24q. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990 From JBRYAN@pstcc.cc.tn.us Tue Feb 6 13:15:48 1996 Return-Path: Received: from PSTCC4.PSTCC.CC.TN.US by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA06910; Tue, 6 Feb 96 13:15:48 EST Resent-From: JBRYAN@pstcc.cc.tn.us Resent-Message-Id: <9602061815.AA06910@life.ai.mit.edu> Received: from pstcc.cc.tn.us by pstcc.cc.tn.us (PMDF V5.0-3 #11457) id <01I0W7H2EIZK8WWAHI@pstcc.cc.tn.us> for cube-lovers@ai.mit.edu; Tue, 06 Feb 1996 13:17:49 -0400 (EDT) Resent-Date: Tue, 06 Feb 1996 13:17:49 -0400 (EDT) Date: Tue, 06 Feb 1996 13:17:44 -0400 (EDT) From: Jerry Bryan Subject: Large Searches with Small Memory Sender: JBRYAN@pstcc.cc.tn.us To: Cube-Lovers Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 7BIT I have access to less computing resources than I used to have. As a result, I have been thinking about ways to conduct large searches with less memory. There are no results here, just some thoughts. I will assume a quarter turn metric. It would be easy to generalize the proposals below to other metrics, but I will not do so. We let C[n] be the set of all positions of length n. C[0] is just {Start}, and C[1] is just Q, the set of twelve quarter turns. We let T[n] be the union of C[k] for k in 0..n. We assume that any computerized breadth first search for God's Algorithm would build (in turn) C[0], C[1], etc., and would store each C[k] in memory in some reasonable indexed and searchable data structure. The details of the data structure do not (I think) matter for the purposes of this note. We assume that the primary constraint on the search is memory size rather than time. These days, most anybody has access to a machine (or machines) where a problem can be allowed to run for hundreds or thousands of hours if necessary. A 486 or Pentium on your desk would serve nicely, and a UNIX work station would be even better. I have used both a 486 (running OS/2 for multitasking) and a UNIX work station in this manner. The machines could be used for other things while the cube problems were running. We assume that n is the largest n for which we can store C[n]. We assume that if we can store C[n], we can also store T[n]. For all practical purposes, T[n] and C[n] are about the same size close to Start because C[n] is a little more than nine times larger than C[n-1]. With this structure in hand, we could form all products XY for X and Y in T[n]. We would simply form the products; we would not try to store them. But having done so, we would have created all positions in T[2n]. In some ways, this is not very useful. That is, in general we would not know the length of any particular XY, nor would we know the size of C[k] for k in n+1..2n. But as we formed the products, we could check them against any position of interest, or against a small set of positions of interest. We could then determine if any of the interesting positions were in T[2n], and thus bound their length. (We assume that none of the interesting positions are in T[n]. Otherwise, we could determine their length directly and none of these Draconian measures would be necessary.) Such a half-depth search has been discussed quite a few times before in Cube-Lovers. But here follows what I think is a new idea. What if we formed all products XY for X in C[n] and Y in C[1]. Since C[1] is Q, this is really just the procedure for a standard depth first search. But we can't store C[n+1]. Can we determine the size of C[n+1] anyway? Try the following. The length of each XY is either n-1 or n+1. Verify which case we have by reference to C[n-1], and throw away the products of length n-1. But if the length of XY is n+1, do we count it, or do we not? The problem is that we might have XY=VW for X and V in C[n], Y and W in C[1], X not equal V, and Y not equal W. Which do we count and which do we not? Actually, there may be up to twelve such products, so we need a way uniquely to determine which product to count and which not to count. Suppose we have XY in hand and wish to know whether to count it. Form all products (XY)Z for Z in C[1]. There are twelve such products, and at least one of them will be in C[n]. We assume that C[1] can be ordered (probably already is) by our data structure. Hence, we count XY only if Y'=Z*, where Z* is the first Z such that XY(Z) is in C[n]. (Strictly speaking, we would not have to form all products XY(Z). We would stop once we found the first Z such that (XY)Z was in C[n]. We would then either have Y'=Z*, or we wouldn't. But this only reduces the number of products down from twelve to an average of six.) It seems to me that this procedure would work in principle, but I am not sure how practical it would be. The problem is that there would be a lot of products XY(Z) to calculate and test. Is there any shorter method to determine whether or not to count XY? I normally write my sets C[k] out to a file. Any analysis I wish to do is then run against the file after the fact. With the new procedure I am describing, any analysis of C[n+1] would have to be done as the products were being formed. We can use a similar procedure to determine the size of C[n+2], C[n+3], etc. up through C[2n], but things get more complicated and more impractical. For C[n+2], form all XY for X in C[n] and Y in C[2]. All such products are in C[n-2], C[n], or C[n+2]. As before, we look up XY in C[n-2] and in C[n], and throw it away if it is already there. We then form all XY(Z) for Z in C[2] (there will be 114 such products), and count the product only if Y'=Z*, where Z* is the first Z in C[2] such that XY(Z) is in C[n]. But this case is even more time consuming than the C[n+1] case because we will on the average have to look at 57 products (57=114/2). As an aside, I have considered creating C[n+1] as the product of XY with X in C[n-1] and Y in C[2], rather than as the product of XY with X in C[n] and Y in C[1], even before running out of memory to store the results. We still have to check for positions whose length is less than n+1, and we still have to check for duplicate positions of length n+1. But using C[n-1] and C[2] would automatically eliminate from the search duplicate positions such as ZRR'=Z or ZRL=ZLR. Or better still, perhaps to create C[n+1] we should take X from C[n/2] and Y from C[(n/2)+1]? Has anybody tried anything like that? C[n+3] gets worse still. If we form all XY for X in C[n] and Y in C[3], the length of XY may be n-3, n-1, n+1, or n+3. We dispose of the n-3 and n-1 cases as before, but then we would have to have a way to distinguish between the n+1 and n+3 cases. I think the procedure becomes truly impractical at this point. Anyway, that's it. Has anybody ever tried anything along the lines I have outlined for a problem too big to store? If so, did it work? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990 From pbeck@qa.pica.army.mil Tue Feb 6 15:25:05 1996 Return-Path: Received: from qa.pica.army.mil by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17957; Tue, 6 Feb 96 15:25:05 EST Received: from [129.139.96.34] (hipmac8.pica.army.mil) by qa.pica.army.mil with SMTP (1.37.109.16/16.2) id AA098367470; Tue, 6 Feb 1996 15:11:10 -0500 Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Tue, 6 Feb 1996 15:19:03 -0500 To: cube-lovers@ai.mit.edu From: pbeck@qa.pica.army.mil (Peter Beck) Subject: museum exhibition Cc: ilanab@wam.umd.edu, jhbeck@gwis2.circ.gwu.edu, KCEBL@aol.com The "Morris Museum", 6 Normandy Heights Road, Morristown, NJ 07960, 201-538-0454 is having and exhibit called "THESE ARE A FEW OF MY FAVORITE THINGS, A LOOK AT COLLECTORS AND THEIR MAGNIFICENT COLLECTIONS". I have lent them the following Rubik's cube items to be included. 1. ephemera 1.1 "Rubik's Cube Solution Poster" 1.2 "The Rubik's Cube Puzzle Poster" - 1.3 "Rubik's Cube Clinic Poster" - 1.4 "Rubik's Cube Button Pin Collection" - 1.5 "We Have The Original Promotion Poster" - 1.6 cardboard dipslay cube 2. Puzzles 2.1 3x3x3 stuff 2.1.1 57 mm 3x3x3 curiosity cubes 2.1.1.1 Russian box, orange cardboard box with Russian writing 2.1.1.2 Deluxe cube, sold by Ideal Toy Co 2.1.1.3 Blindmans, source unknown 2.1.1.4 Disney Characters , source unknown 2.1.1.5 Pennant, source unknown 2.1.1.5 Calendar Cube, Ideal Toy Co 2.1.1.6 Video cassette promo Cube, 2.1.2 57 mm 3x3x3 shape adaptations 2.1.2.1 ball in cube, unpackaged, custom non-production 2.1.2.2 "Rubik's World", sold by Ideal Toy Co 2.1.2.3 Japanese "Space Cube" 2.1.2.4 "Magique Cube", common name "Space Shuttle" 2.1.2.5 crystal, custom made by Greg Steven's Seattle WA 2.1.3 3x3x3 size variatations 2.1.3.1 20mm Ideal necklace cube, sold by Ideal Toy Co 2.1.3.2 38mm keychain cube, sold by Dynasty Products 2.2 non-3x3x3 variatations 2.2.1 2x2x2 called Rubik's Pocket Cube", sold by Ideal Toy Co 2.2.2 2x3x3 called "Magic Domino", sold by Politoys with a 1982 copyright, this version is popularly know as the blind mans version because it has raised spots for markings instead of paint or stickers. 2.2.3 4x4x4 called "Rubik's Revenge" , sold by Tsakuda in Japan 2.2.4 5x5x5 called "Rubik's Wahn", sold by Arxon, not distributed in USA 3. Memorabilia 3.1 CUBE in Bottle, custom made by Lee Dian, Malaysia 3.2 Ceramic Lamp Base decorated as a cube, Jessica Beck, USA 3.3 "Le Vrai Magicube" build yourself a cube kit CHange is IRresistible ...CHAnge is Irresistible ...CHange is IRResistible ... Peter Beck ... aGENT of cHANGe ^^^^^^^^^^ e-mail * temporary B-92 x2383 b-62 x5580 VOICE: 201-724-6684 * DSN:880 * 800-831-2759-1-#-*-4-6684 FAX: 201-724-4026 POSTAL - ARDEC, P. Beck, B-92, Picatinny Arsenal, NJ 07806-5000 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ SOFTWARE QUALITY ENGINEERING BRANCH, ... ARDEC, AMSTA-AR-QAT-A, B-62, Picatinny Arsenal, NJ 07806-5000 --> http://qa.pica.army.mil/qat/sqe/sqe.html * VOICE:201-724-5580 <-- ... pb...pb...pb...pb...pb.._ 31 JAN 96 release _..pb...pb...pb...pb...pb... From mark.longridge@canrem.com Wed Feb 7 03:00:03 1996 Return-Path: Received: from itchy.crso.com (itchy.canrem.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA13843; Wed, 7 Feb 96 03:00:03 EST Received: by canrem.com (PCB-UUCP 1.1f) id 20A151; Wed, 7 Feb 96 02:54:24 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: < U, F, R > group From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.1288.5834.0C20A151@canrem.com> Date: Wed, 7 Feb 96 02:47:00 -0500 Organization: CRS Online (Toronto, Ontario) > there was never any response to this, but i'll give my solution anyway. I am working on an engine to search optimal paths for < U, F, R > but it's not done yet. It's certainly within the bounds of computibility: Size (u_f_r) = 170,659,735,142,400 (hmmm, 170 trillion maybe not!) > let X = U2 F R' F2 R F2 R F2 R' F U2 . > > then X produces two two-cycles of corner-edge pairs. the commutator > [ X , C_UFR ] produces "cube in a cube" in 22 face / 32 quarter turns > and only turns the faces U, F and R. > > the notation C_UFR refers to a rotation of the whole cube, and > [ a, b ] denotes the commutator a b a^-1 b^-1 . > > mike Brilliant. Although harder to remember, X + ( X * C_UFR) will do. U2 F1 R3 F2 R1 F2 R1 F2 R3 F1 U2 F2 R1 U3 R2 U1 R2 U1 R2 U3 R1 F2 (22 f, 32 q) -> Mark <- From mark.longridge@canrem.com Wed Feb 7 03:00:03 1996 Return-Path: Received: from itchy.crso.com (itchy.canrem.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA13842; Wed, 7 Feb 96 03:00:03 EST Received: by canrem.com (PCB-UUCP 1.1f) id 20A152; Wed, 7 Feb 96 02:54:24 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Cube Musings From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.1289.5834.0C20A152@canrem.com> Date: Wed, 7 Feb 96 02:48:00 -0500 Organization: CRS Online (Toronto, Ontario) Further Cube Musings ==================== We usually think of positions antipodal to start only, but there are positions antipodal to any given position. Given a small enough subgroup of the cube, i.e. one which we can exhaustively study, it is not hard to determine some examples. Let's use the square's group and the good ol' pons asinorum. Pons is antipodal to position X. Pons + X = Antipode (let's use position p135) p135 2 X, 4 T L2 B2 D2 F2 T2 F2 T2 L2 T2 D2 F2 T2 L2 D2 F2 Solving for position X is easy enough.... X = Antipode - Pons Position X = F2 D2 L2 D2 F2 L2 T2 F2 T2 F2 T2 F2 L2 The idea of (-1) * pons or (-pons) is equivalent to the inverse of pons, since (+pons) + (-pons) = identity. So Pons and Position X are antipodes of each other. Using this straightforward method we can find an antipode to any position in the square's group, or for any other positions in another small subgroup. This brings up the idea of a "Rubik's Tour". Such a tour would touch on a set of interesting patterns within a given subgroup, or potentially the entire cube group. Of course, "God's Tour" would not only touch on all the interesting patterns, it would also sequence all the patterns AND orient them in space such that the number of q turns would be minimal for the tour! I am currently working on "God's Tour" for some of the lesser subgroups, touching on say a dozen patterns for the square's group. If humans and computers ever resolve "God's Algorithm" there is some solace that there are problems even more intractible. Hmmmm, I just had a thought. It would probably be best to group all the patterns closer to start and work outwards towards the more antipodal ones. With the smaller groups a "Total Tour" would be possible! Visit all elements! -> Mark <- From Robert_Buckley@orkney.fc.uhi.ac.uk Tue Feb 13 10:32:57 1996 Return-Path: Received: from torridon.uhi.ac.uk by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AC22547; Tue, 13 Feb 96 10:32:57 EST Received: from fc.uhi.ac.uk (fc-gw.uhi.ac.uk [194.35.192.4]) by torridon.uhi.ac.uk (8.6.8.1/8.6.13) with SMTP id PAA01309 for ; Tue, 13 Feb 1996 15:02:49 GMT Date: Tue, 13 Feb 96 15:00:01 0 From: Robert_Buckley@orkney.fc.uhi.ac.uk (Robert Buckley) Organization: UHI Project Office Subject: Subscribe To: cube-lovers@life.ai.mit.edu Message-Id: <9571.ensmtp@fc.uhi.ac.uk> Priority: normal X-Mailer: ExpressNet/SMTP v1.1.5 Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit subscribe -- -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- Sent via ExpressNet/SMTP(tm), Internet Gateway of the Gods! ExpressNet/SMTP (c)1994-95 Delphic Software, Inc. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- From JBRYAN@pstcc.cc.tn.us Tue Feb 13 15:45:47 1996 Return-Path: Received: from PSTCC4.PSTCC.CC.TN.US by life (4.1/AI-4.10) for /com/archive/cube-lovers id AA04850; Tue, 13 Feb 96 15:45:47 EST Resent-From: JBRYAN@pstcc.cc.tn.us Resent-Message-Id: <9602132045.AA04850@life> Received: from pstcc.cc.tn.us by pstcc.cc.tn.us (PMDF V5.0-3 #11457) id <01I15VO79IYO8WXE00@pstcc.cc.tn.us> for cube-lovers@ai.mit.edu; Tue, 13 Feb 1996 11:27:57 -0400 (EDT) Resent-Date: Tue, 13 Feb 1996 11:27:55 -0400 (EDT) Date: Tue, 13 Feb 1996 11:27:51 -0400 (EDT) From: Jerry Bryan Subject: Re: Large Searches with Small Memory In-Reply-To: Sender: JBRYAN@pstcc.cc.tn.us To: Cube-Lovers Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 7BIT On Tue, 6 Feb 1996, Jerry Bryan wrote: > But here follows what I think is a new idea. What if we > formed all products XY for X in C[n] and Y in C[1]. Since > C[1] is Q, this is really just the procedure for a standard > depth first search. But we can't store C[n+1]. Can we > determine the size of C[n+1] anyway? As is often the case, there is nothing new under the sun. I believe that the "new" idea I was suggesting is very similar to, or perhaps identical with, certain aspects (or all) of Shamir's algorithm. The best references I have found in the archives are as follows: Alan Bawden 27 May 87 Shamir's talk really was about how to solve the cube! Michael Reid 16 Dec 94 Re: Cyclic Decomposition David Moews 23 Jan 95 Shamir's method on the superflip = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990 From mreid@ptc.com Tue Feb 13 16:14:27 1996 Return-Path: Received: from poster (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA01056; Tue, 13 Feb 96 16:14:27 EST Received: from ducie.ptc.com by poster (5.x/SMI-SVR4-NN) id AA28288; Tue, 13 Feb 1996 16:09:42 -0500 Message-Id: <9602132109.AA28288@poster> Received: by ducie.ptc.com (1.38.193.4/16.2.nn) id AA12740; Tue, 13 Feb 1996 16:40:40 -0500 Date: Tue, 13 Feb 1996 16:40:40 -0500 From: michael reid To: cube-lovers@ai.mit.edu Subject: Re: Group/graph status? Cc: rcs@cs.arizona.edu rich schroeppel asks > Has anyone tabulated the number of positions are reachable (from the > initial cube) in one move, two moves, etc.? Is the diameter of the > graph known? first note that there are two common ways to define a "move", any twist of a face (face turn metric), or any 90 degree turn of a face (quarter turn metric). jerry bryan was counting (and storing) positions close to start on magnetic tape. he gave figures for positions within 7 face turns on july 19, 1994 and positions within 11 quarter turns on february 4, 1995. (jerry, how many reels of tape did this take?) the diameter isn't known. the best lower bounds are 20 face turns, or 24 quarter turns, both from considering the position "superflip". the best upper bounds are 29 face turns, or 42 quarter turns. mike From alan@curry.epilogue.com Wed Feb 14 18:45:13 1996 Return-Path: Received: from curry.epilogue.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA18706; Wed, 14 Feb 96 18:45:13 EST Received: (from alan@localhost) by curry.epilogue.com (8.6.12/8.6.12) id SAA27698; Wed, 14 Feb 1996 18:45:04 -0500 Date: Wed, 14 Feb 1996 18:45:04 -0500 Message-Id: <14Feb1996.174115.Alan@LCS.MIT.EDU> From: Alan Bawden Sender: Cube-Lovers-Request@ai.mit.edu To: Cube-Lovers@ai.mit.edu Subject: Welcome to the future of the Internet As those of you who have been reading Cube-Lovers for the last few months are well aware, we have been suffering through (almost) weekly advertisements sent by some nutcase trying to sell magazines. In the past, I have been able to defeat unwanted advertising on Cube-Lovers by simply having a chat with the advertiser (or his postmaster). But the magazine guy is determined to send a weekly copy of his advertisement to every mailing list in the world, despite all objections -- there's really no way to shut him off short of some form of mailing list moderation. So we're forced to make Cube-Lovers a moderated mailing list. Starting with this message, every message sent to Cube-Lovers will be screened before it gets distributed to the rest of you. For the moment, some of the steps in the screening process are manual, so there may be a delay before a message you submit gets out to the rest of the list. That's the price we pay to keep Cube-Lovers from becoming a conduit that delivers more advertising than content. From your point of view, this change should be completely invisible (beyond the improved content and increased latency). It is still the case that you should address all submissions to Cube-Lovers@AI.MIT.EDU and all administrative correspondence to Cube-Lovers-Request@AI.MIT.EDU. There are some other advantages to the new scheme beyond filtering out advertising: 1. Filtering out other inappropriate messages, such as misdirected subscription requests. 2. Better handling of mailer bounce messages. This change should almost entirely eliminate cases where you submit a message to Cube-Lovers and some mailer sends you an error report. Almost all such messages should now be routed correctly to me. (Of course, mailers will still sometimes screw up -- please forward any mailer errors you -do- get back to me.) 3. Less messages like this one. 4. For the moment, the archive at ftp://ftp.ai.mit.edu/pub/cube-lovers continues to accumulate the un-filtered messages. But eventually, I hope to keep it free of trash as well. If this message is delivered smoothly, it should be followed by two more messages that arrived while I was debugging this stuff. And you will -never- see the magazine advertisement that was submitted last weekend! - Alan (Cube-Lovers-Request@AI.MIT.EDU) From tmartin@accucomm.net Thu Feb 15 07:09:27 1996 Return-Path: Received: from relay2.UU.NET by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA16506; Thu, 15 Feb 96 07:09:27 EST Received: from accucomm.net by relay2.UU.NET with SMTP id QQadae25227; Thu, 15 Feb 1996 07:09:23 -0500 (EST) Received: from the.accucomm.net by accucomm.net (8.6.9/SMI-4.1) id MAA09438; Thu, 15 Feb 1996 12:06:18 GMT Date: Thu, 15 Feb 1996 12:06:18 GMT Message-Id: <199602151206.MAA09438@accucomm.net> X-Sender: tmartin@the.accucomm.net X-Mailer: Windows Eudora Light Version 1.5.2 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: Cube-Lovers@ai.mit.edu From: "Thomas H. Martin" Subject: Resolution of the cube My son has dug out my cube and has a burning interest in it now. Also, he has revived my interest in it. My question is, is there somewhere I can get the solution for him? I would take a mailing address, printed copy or even an old E-mail message. My son is 13 and quite anxious to work on it and solve it. Thanks, Tommy Martin Dublin, GA tmartin@accucomm.net From JBRYAN@pstcc.cc.tn.us Thu Feb 15 10:41:04 1996 Return-Path: Received: from PSTCC4.PSTCC.CC.TN.US by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA00157; Thu, 15 Feb 96 10:41:04 EST Resent-From: JBRYAN@pstcc.cc.tn.us Resent-Message-Id: <9602151541.AA00157@life.ai.mit.edu> Received: from pstcc.cc.tn.us by pstcc.cc.tn.us (PMDF V5.0-3 #11457) id <01I18MLFP5KI8WYZ5B@pstcc.cc.tn.us> for cube-lovers@ai.mit.edu; Thu, 15 Feb 1996 10:39:58 -0400 (EDT) Resent-Date: Thu, 15 Feb 1996 10:39:58 -0400 (EDT) Date: Thu, 15 Feb 1996 10:39:54 -0400 (EDT) From: Jerry Bryan Subject: Shamir on Breadth First Searches Sender: JBRYAN@pstcc.cc.tn.us To: Cube-Lovers Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 7BIT Armed with some newfound understanding of Shamir's method, I would like to revisit the issue of large searches in small memory. However, I will be proposing the application of Shamir's method in a slightly different form than it has been applied before. The best discussion of Shamir's method in the archives is probably Alan Bawden's note of 27 May 87 "Shamir's talk really was about how to solve the cube!". The thrust of Shamir's talk was how to determine the minimal solution for a given position in a reasonable time and with a modest (relatively speaking!) amount of memory. My take on the Shamir's method is two-fold. First, let T[n] be the set of positions no greater than n moves from Start, and let x be the position in question. Shamir's method first involves taking the intersection of T[n] with xT[n]. If the intersection is null, then x is greater than 2n moves from Start. Otherwise, the distance from Start can be determined rather easily. This is our old friend which I call the half-depth search. The efficacy of a half-depth search is dependent on n. A reasonable n of say 5 or 6 only permits testing x up to a distance of about 10 or 12 moves from Start. The second component of Shamir's method is the clever part. You store T[n] and create sort of a virtual T[2n] which doesn't have to be stored. You do the same thing with xT[n] to create a virtual xT[2n]. Forming the intersection of T[2n] with xT[2n] lets you test positions up to a distance of 4n from Start while only storing T[n] and xT[n]. So for n=5, we can test for distances up to 20 moves from Start. My primary interest lies in creating T[n] for the largest possible n, rather than testing for particular positions. Hence, I want to talk about just the portion of Shamir's method that lets us get from a real T[n] to a virtual T[2n]. Let me start be reviewing my understanding of key points of Shamir's method. Given two sets of positions S and T, Shamir tells us how to form all the products st for s in S and t in T with the products being created in lexicographic order. The storage required is order N rather than order N^2 (provided of course that the products are only created and are not stored). For the algorithm to work, T itself has to be in lexicographic order. I don't think S has to be in lexicographic order (see below). But S and T may well be the same set, and in any case there is no loss of generality in requiring that S be in lexicographic order as well. Furthermore, T must be stored as a tree, and we might just as well store S as a tree, too. Alan gives an excellent description of the required tree structure. The structure itself is a very old concept and is not unique to Shamir's method. It could be used, for example, to store a dictionary for a spell-checker. Such a tree would branch 26 ways (American alphabet) for each of the 26 possible first letters. The tree would branch again in up to 26 ways for the second letter and for each subsequent letter, etc. For Shamir's tree, the "letters" are (usually one byte) numbers defining the permutations, where the permutation is simply a vector listing (in order) the values of the permutation. Choose a particular s[j] in S and consider all the products (s[j])(t[k]) for t[k] in T and for k in 1..n. There is some ordering of the t[k] values which will put the {s[j])(t[k]) values in proper lexicographic order. The t[k] values themselves are obviously not in lexicographic order, and may indeed appear to be in a "random" order. But the order is far from random; it is quite carefully considered. The genius of Shamir's method is that it tells us exactly how to accomplish the proper ordering of the t[k] values to yield lexicographic ordering of the {s[j])(t[k]) values. Notice that the required order of the t[k] values is different for each s[j]. My brief description of the magic is that (s[j])' is used as a template to tell us how to traverse the T tree to make the t[k] values come out in the required order to make the (s[j])(t[k]) values come out in lexicographic order. See Alan's note for additional details. (Alan doesn't mention (s[j])' explicitly, but that is what it comes down to. Shamir reverse engineers s[j], runs it backwards if you will, to figure out how to make (s[j])(t[k]) come out right.) The rest of the algorithm is a little fuzzy to me, but here is how I think it has to work. Suppose S contains m elements and T contains n elements. What we have done so far is to create a single sequence of products (s[j])(t[k]) for some particular, fixed s[j]. The sequence contains n elements (one for each t in T), and is in lexicographic order. We must produce m such sequences, one for each s[j]. Then, we must perform an m-way merge of the m sequences. The result of our merge is the desired sequence of products st in lexicographic order. It is the fact of this merge that leads me to believe that the s values do not have to be in lexicographic (or any other particular) order. If m is very large (more than a few dozen), such a merge is not quite so easy as it sounds, and it is the details of the merge that are most fuzzy to me in Alan's note. The merge would normally be accomplished by forming an ordered queue containing the first element of each sequence. The first element would be popped off the queue, then the next element from that sequence would be calculated and put into the queue. The tricky part is that the queue has to be kept ordered. It has to be ordered in the first place. Then, when an element is popped off and a new element added, the new element has to be added in the correct place. Hence, I would probably implement the queue itself as another tree, separate from the S and T trees. Now, we return to our main discussion. Let Q[k] be the set of positions which are k quarter turns from Start. (I used C[k] in my last note). Q[1] is just Q, the set of 12 quarter turns. Store each Q[k] for k in 0..n in its own "Shamir tree". Create a virtual Q[n+1] as the lexicographically ordered set of products st for s in Q[n] and t in Q[1]. Shamir does not do everything for us. We have to do some of the work ourselves at this point. The first issue is that some of the products will be duplicate. But the lexicographical ordering makes the duplicates easy to detect. So detect the duplicates and throw them away. The second issue is that some of the products are in Q[n-1] rather than in Q[n+1]. But since Q[n-1] is also in lexicographical order, we can keep a finger or toe pointed to Q[n-1], scanning through it in step with the products which are generated. Any product which is found in Q[n-1] is not counted as being in Q[n+1]. Creating virtual Q[n+2] is like unto creating virtual Q[n+1]. We form products from Q[n] and Q[2]. An additional complication is that our fingers and toes must point to and step along both Q[n] and Q[n-2] looking for products which are shorter than n+2 quarter turns, and which therefore are not to be counted. Now comes the really interesting part --- creating virtual Q[n+3]. We form the products from Q[n] and Q[3]. As we create the products, we must track along through the Shamir trees for Q[n-3], Q[n-1], and Q[n+1]. But the Shamir tree for Q[n+1] is virtual, and isn't really there! Here is how we do it. We must create virtual Q[n+1] and virtual Q[n+3] at the same time, keeping them more or less in step, with Q[n+1] equal to or one step ahead of Q[n+3]. That way, we have the one real element available of the virtual Q[n+1] that we need to test the virtual Q[n+3] against. As a really *old* programmer, I would describe what we are doing with Q[n+1] and Q[n+3] as a match/merge. Given the requirement to generate Q[n+1] as we generate Q[n+3], there is no real reason to generate Q[n+1] by itself. If we have enough fingers and toes to point to and count everything, we might just as well produce Q[n+1] and Q[n+3] on the same pass of the data. For that matter, we might just as well get Q[n+1], Q[n+3], through Q[2n-1] on the same pass. Similarly, we might as well get Q[n+2], Q[n+4], through Q[2n] on the same pass. This is all very simple in principle. But in my experience, keeping track of all those pointers and counters is a real pain to program. Can we go again? That is, can we go from Q[2n] to Q[4n]? I think not. Shamir's method requires that of the S and T trees, at least the T tree really be there. We have to traverse it many times and in all kinds of orders. Being there virtually is not enough. Finally, what about local maxima? We cannot detect local maxima by forming Xq for a position X and for all q in Q, testing to see of all Xq are closer to Start. (The Xq are not in lexicographical order.) I am thinking about the following as a way to find local maxima, but it may be bogus. See what you think. Suppose a position in one of the virtual Q[n+k]'s that we are creating is not the product of any st for s in Q[n] and t in Q[k+2]. For example, suppose there is an element p in Q[n+1] which is not the product of any st for s in Q[n] and t in Q[3]. (We could find all such p easily in our scan of the virtual Q[n+k] trees.) Could we say that all such p are local maxima? I am not sure. This method works for sure to find local maxima in Q[n-1] when creating Q[n+1]. In fact, this method is the way I find local maxima with my large tape searches. That is, the method works when you are only going one step ahead. If you use Q[n] and Q[1] to create Q[n+1], then all the products are in Q[n+1] or Q[n-1], and any element of Q[n-1] which is not a product of Q[n] and Q[1] is a local maximum. But can we say that any element of Q[n+1] that is not a product of Q[n] and Q[3] is a local maximum? I just don't know. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990 From awechsle@bbn.com Thu Feb 15 11:20:11 1996 Return-Path: Received: from chaplin.bbn.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA02896; Thu, 15 Feb 96 11:20:11 EST Received: from chara.BBN.COM (CHARA.BBN.COM [128.33.161.114]) by chaplin.bbn.com (8.6.12/d4m-bbn) with ESMTP id LAA20529; Thu, 15 Feb 1996 11:20:10 -0500 From: Allan Wechsler Received: by chara.BBN.COM (8.6.10) id LAA03366; Thu, 15 Feb 1996 11:20:09 -0500 Date: Thu, 15 Feb 1996 11:20:09 -0500 Message-Id: <199602151620.LAA03366@chara.BBN.COM> To: tmartin@accucomm.net Cc: Cube-Lovers@ai.mit.edu In-Reply-To: <199602151206.MAA09438@accucomm.net> (tmartin@accucomm.net) Subject: Re: Resolution of the cube Reply-To: awechsle@bbn.com Date: Thu, 15 Feb 1996 12:06:18 GMT From: "Thomas H. Martin" My son has dug out my cube and has a burning interest in it now. Also, he has revived my interest in it. My question is, is there somewhere I can get the solution for him? Tommy Martin Dublin, GA tmartin@accucomm.net Now you've pushed my button. When the cube first came out, a bunch of us at MIT were wild to solve it. There were _no_ published solutions. At least three or four of us solved the cube by ourselves, independently. We twisted and turned, drew arcane diagrams to show what went where, and although it sometimes took a couple of weeks, we each managed it. Then the books started to come out, and as far as I can tell, no one ever solved it independently again. The cube is a solvable puzzle. It is challenging, but it eventually yields to analysis and experimentation. Why don't you and your son _not_ cheat, and actually solve the thing? You'll be the first to do it on your own for more than a decade. What fun is it to read the answer from a book? -A From DHUNT1@ukcc.uky.edu Thu Feb 15 14:35:38 1996 Return-Path: Received: from UKCC.uky.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA18237; Thu, 15 Feb 96 14:35:38 EST Received: from UKCC.UKY.EDU by UKCC.uky.edu (IBM VM SMTP V2R3) with BSMTP id 7472; Thu, 15 Feb 96 14:34:04 EST Received: from ukcc.uky.edu (NJE origin DHUNT1@UKCC) by UKCC.UKY.EDU (LMail V1.2a/1.8a) with BSMTP id 2801; Thu, 15 Feb 1996 14:31:29 -0500 Date: Thu, 15 Feb 96 14:31:11 EST From: "Andrew F. Hunt" Subject: Subscription To: CUBE-LOVERS@life.ai.mit.edu X-Mailer: MailBook 95.01.000 Message-Id: <960215.143128.EST.DHUNT1@ukcc.uky.edu> Please add me to the ube list. Thanks, Andrew F. Hunt ANDREW F. HUNT UNIVERSITY OF KENTUCKY From mark.longridge@canrem.com Thu Feb 15 15:18:57 1996 Return-Path: Received: from itchy.crso.com (itchy.canrem.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA21477; Thu, 15 Feb 96 15:18:57 EST Received: by canrem.com (PCB-UUCP 1.1f) id 20AE8D; Thu, 15 Feb 96 15:13:47 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Re: Resolution of the cub From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.1299.5834.0C20AE8D@canrem.com> In-Reply-To: <199602151620.LAA03366@chara.BBN.COM> Date: Thu, 15 Feb 96 15:07:00 -0500 Organization: CRS Online (Toronto, Ontario) -> Date: Thu, 15 Feb 1996 12:06:18 GMT -> From: "Thomas H. Martin" -> -> My son has dug out my cube and has a burning interest in it now. -> Also, he -> has revived my interest in it. My question is, is there somewhere I -> can get -> the solution for him? -> -> Tommy Martin -> Dublin, GA -> tmartin@accucomm.net -> -> Now you've pushed my button. -> -> When the cube first came out, a bunch of us at MIT were wild to solve -> it. There were _no_ published solutions. At least three or four of -> us solved the cube by ourselves, independently. We twisted and -> turned, drew arcane diagrams to show what went where, and although it -> sometimes took a couple of weeks, we each managed it. -> -> Then the books started to come out, and as far as I can tell, no one -> ever solved it independently again. Bzzzzzz ...... wrong. I do understand that Allan Wechsler was one of the original solvers, before the glut of books on the subject, however I solved the cube and the megaminx independently. Even though there were many cube books, there was only one megaminx (rubik-type dodecahedron) book, and it was rather hard to follow. My advice to anyone who likes puzzles of this type who is already adept at solving the cube is to solve it using a subgroup like < U, R > or < U, F, L >. One of the problems I'm working on is how to get the spot patterns on the megaminx. To the best of my knowledge this information is not recorded anywhere on the planet. (Yes, I can just solve it that way, I'm looking for a short algorithm, and no one and no program can help!) So even though we can make mincemeat of the pyraminx, dino cubes, square 1, Fisher's Cube, Skewbs, The UFO, Rubik's Revenge, Rubik's Wahn, etc etc there are still a couple of exceptional difficult problems: Spot Patterns on the Megaminx in a short number of moves. Dan Hoey's Tartan Cube. God's Algorithm on the standard cube. -> Mark <- From JBRYAN@pstcc.cc.tn.us Fri Feb 16 12:22:06 1996 Return-Path: Received: from PSTCC4.PSTCC.CC.TN.US by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA00292; Fri, 16 Feb 96 12:22:06 EST Resent-From: JBRYAN@pstcc.cc.tn.us Resent-Message-Id: <9602161722.AA00292@life.ai.mit.edu> Received: from pstcc.cc.tn.us by pstcc.cc.tn.us (PMDF V5.0-3 #11457) id <01I1A4EZL7X48WZUFO@pstcc.cc.tn.us> for cube-lovers@ai.mit.edu; Fri, 16 Feb 1996 12:20:57 -0400 (EDT) Resent-Date: Fri, 16 Feb 1996 12:20:57 -0400 (EDT) Date: Fri, 16 Feb 1996 12:20:50 -0400 (EDT) From: Jerry Bryan Subject: Re: Shamir on Breadth First Searches In-Reply-To: <9602151929.AA29120@> Sender: JBRYAN@pstcc.cc.tn.us To: Cube-Lovers Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 7BIT On Thu, 15 Feb 1996, Don Woods wrote: > > Can we go again? That is, can we go from Q[2n] to Q[4n]? > > I think not. Shamir's method requires that of the S and T > > trees, at least the T tree really be there. We have to > > traverse it many times and in all kinds of orders. Being > > there virtually is not enough. > > But wait a sec. Can't we go from Q[2n] to Q[3n]? We still > have T sitting there. As we generate each element of Q[2n], > we could use it to generate Q[2n] x T, couldn't we? Or do > you also need S to "really be there", too? (I didn't go back > over your description to try to figure that out; I'm just > basing my suggestion on the quoted paragraph.) As I said earlier, this is the part of Shamir's method about which I am most uncertain. In my description of forming products st from S and T, I emphasized the role of T. But if I understand the method correctly, the width of what I called an m-way merge is controlled by the size of S (remember that S contains m elements and T contains n elements). So the merge queue itself will also have m elements. If you try to generate Q[2n] x T, the width of the merge (and the size of the merge queue) will have to be as large as Q[2n], which is too large to store. In answer to your specific question, I would say that the merge queue has to really be there. S might or might not have to really be there, depending on exactly how you program the interaction between S and the merge queue. But in any case, the merge queue is as big as S. (I would gladly accept any and all help discussing these issues with anyone who has actually programmed the algorithm.) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990 From AirWong@aol.com Sun Feb 18 15:41:30 1996 Return-Path: Received: from mail04.mail.aol.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA29427; Sun, 18 Feb 96 15:41:30 EST Received: by mail04.mail.aol.com (8.6.12/8.6.12) id PAA25903 for Cube-Lovers@ai.mit.edu; Sun, 18 Feb 1996 15:41:29 -0500 Date: Sun, 18 Feb 1996 15:41:29 -0500 From: AirWong@aol.com Message-Id: <960218154129_225194632@mail04.mail.aol.com> To: Cube-Lovers@ai.mit.edu Subject: Re Resolution of the cube A few messages ago yo was this -> Now you've pushed my button. -> -> When the cube first came out, a bunch of us at MIT were wild to solve -> it. There were _no_ published solutions. At least three or four of -> us solved the cube by ourselves, independently. We twisted and -> turned, drew arcane diagrams to show what went where, and although it -> sometimes took a couple of weeks, we each managed it. -> -> Then the books started to come out, and as far as I can tell, no one -> ever solved it independently again. -Bzzzzzz ...... wrong. -I do understand that Allan Wechsler was one of the original -solvers, -before the glut of books on the subject, however I solved the -cube and -the megaminx independently. Even though there were many cube -books, -there was only one megaminx (rubik-type dodecahedron) book, and -it was -rather hard to follow. I, too, solved the cube independent of a book. However, after I was done, I found a few books and other algorithms (as well as some friends) and compared the solutions. There are many ways to solve it, and it was fun trying to solve the cube combining the different ideas. When I hunt down Thistlewaite's algorithm it should get even more interesting. Aaron WOng AirWong@AOL.com From JBRYAN@pstcc.cc.tn.us Tue Feb 20 10:51:48 1996 Return-Path: Received: from PSTCC4.PSTCC.CC.TN.US by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA05232; Tue, 20 Feb 96 10:51:48 EST Resent-From: JBRYAN@pstcc.cc.tn.us Resent-Message-Id: <9602201551.AA05232@life.ai.mit.edu> Received: from pstcc.cc.tn.us by pstcc.cc.tn.us (PMDF V5.0-3 #11457) id <01I1FMFANMA48X1JD9@pstcc.cc.tn.us> for cube-lovers@ai.mit.edu; Tue, 20 Feb 1996 10:50:33 -0400 (EDT) Resent-Date: Tue, 20 Feb 1996 10:50:33 -0400 (EDT) Date: Tue, 20 Feb 1996 10:50:31 -0400 (EDT) From: Jerry Bryan Subject: Re: Cube Musings In-Reply-To: <60.1289.5834.0C20A152@canrem.com> Sender: JBRYAN@pstcc.cc.tn.us To: Cube-Lovers Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 7BIT On Wed, 7 Feb 1996, Mark Longridge wrote: > Further Cube Musings > ==================== > > We usually think of positions antipodal to start only, but there are > positions antipodal to any given position. > > Given a small enough subgroup of the cube, i.e. one which we can > exhaustively study, it is not hard to determine some examples. I guess I didn't understand the thrust of this note. Isn't it a bit simpler? Let H be some subgroup of G, let A be the set of antipodes of Start within H, and let h be some element of H. Then, don't we simply have that the antipodes of h are the set hA, where hA={ha | a in A}? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990 From JBRYAN@pstcc.cc.tn.us Tue Feb 20 16:06:52 1996 Return-Path: Received: from PSTCC4.PSTCC.CC.TN.US by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA02988; Tue, 20 Feb 96 16:06:52 EST Resent-From: JBRYAN@pstcc.cc.tn.us Resent-Message-Id: <9602202106.AA02988@life.ai.mit.edu> Received: from pstcc.cc.tn.us by pstcc.cc.tn.us (PMDF V5.0-3 #11457) id <01I1FXF1NAVY8X1JD9@pstcc.cc.tn.us> for cube-lovers@ai.mit.edu; Tue, 20 Feb 1996 16:05:42 -0400 (EDT) Resent-Date: Tue, 20 Feb 1996 16:05:42 -0400 (EDT) Date: Tue, 20 Feb 1996 16:05:34 -0400 (EDT) From: Jerry Bryan Subject: Re: Group/graph status? In-Reply-To: <9602132109.AA28288@poster> Sender: JBRYAN@pstcc.cc.tn.us To: Cube-Lovers Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 7BIT On Tue, 13 Feb 1996, michael reid wrote: > jerry bryan was counting (and storing) positions close to start > on magnetic tape. he gave figures for positions within 7 face > turns on july 19, 1994 and positions within 11 quarter turns on > february 4, 1995. (jerry, how many reels of tape did this take?) It was a little better than 100 tapes. It was roughly 20GB of data. I stored 14 bytes per position (could have done it in 13 bytes, but I stored the lengths with each permutation). Each "position" was really a representative of an equivalence class of M-conjugates (usually) containing 48 elements. Hence, it took about 14/48 bytes (about 2.33 bits) to store each position. This isn't too shabby, but it is nowhere as compact as the coding scheme discussed in the "How Big is Big?" thread. > > the diameter isn't known. the best lower bounds are 20 face turns, > or 24 quarter turns, both from considering the position "superflip". > the best upper bounds are 29 face turns, or 42 quarter turns. A 24q process is known for superflip. It is known that superflip is greater than 19f. Is a 20f process known for superflip? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990 From mreid@ptc.com Wed Feb 21 18:14:30 1996 Return-Path: Received: from poster (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA03956; Wed, 21 Feb 96 18:14:30 EST Received: from ducie.ptc.com by poster (5.x/SMI-SVR4-NN) id AA03108; Wed, 21 Feb 1996 18:10:02 -0500 Message-Id: <9602212310.AA03108@poster> Received: by ducie.ptc.com (1.38.193.4/16.2.nn) id AA11210; Wed, 21 Feb 1996 18:41:32 -0500 Date: Wed, 21 Feb 1996 18:41:32 -0500 From: michael reid To: CRSO.Cube@canrem.com, cube-lovers@ai.mit.edu Subject: Re: < U, F, R > group mark writes > I am working on an engine to search optimal paths for < U, F, R > but > it's not done yet. It's certainly within the bounds of computibility: > > Size (u_f_r) = 170,659,735,142,400 (hmmm, 170 trillion maybe not!) it should be possible to write a good searching program for this subgroup. use the filtration , , <> (which is just the last two stages of the three stage filtration i gave on may 22, 1992), and a kociemba-type searching method. i don't know if it will be feasible to find optimal paths, but this technique should get pretty close. let us know what you find out! mike From mreid@ptc.com Thu Feb 22 17:10:57 1996 Return-Path: Received: from poster (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA19958; Thu, 22 Feb 96 17:10:57 EST Received: from ducie.ptc.com by poster (5.x/SMI-SVR4-NN) id AA20333; Thu, 22 Feb 1996 17:06:31 -0500 Message-Id: <9602222206.AA20333@poster> Received: by ducie.ptc.com (1.38.193.4/16.2.nn) id AA11649; Thu, 22 Feb 1996 17:38:03 -0500 Date: Thu, 22 Feb 1996 17:38:03 -0500 From: michael reid To: cube-lovers@ai.mit.edu Subject: "simplest" solution of the cube? mark writes > This brings up the idea of a "Rubik's Tour". Such a tour would > touch on a set of interesting patterns within a given subgroup, > or potentially the entire cube group. Of course, "God's Tour" > would not only touch on all the interesting patterns, it would > also sequence all the patterns AND orient them in space such that > the number of q turns would be minimal for the tour! I am currently > working on "God's Tour" for some of the lesser subgroups, touching on > say a dozen patterns for the square's group. If humans and computers > ever resolve "God's Algorithm" there is some solace that there are > problems even more intractible. there's a general graph theory conjecture that cayley graphs are hamiltonian (i.e. have hamiltonian circuits). if we take the cayley graph formed by generators {F, F', L, L' U, U', R, R', B, B', D, D'}, the conjecture asserts that there is a sequence of N quarter turns that visits every position exactly once and returns to START. (here N = 43252003274489856000 is the order of the group.) so the proposed "simplest" solution to the cube is to apply such a hamiltonian sequence. at some point, in the middle of the sequence, the cube will be solved! no need to continue with the rest of the sequence. i don't think the general conjecture is close to being proved, but it is known for some special groups and generators. it would be interesting to know if anyone can verify the conjecture for the cube group with quarter turn generators. (face turn generators would also be interesting.) mike From @uconnvm.uconn.edu:dmoews@xraysgi.ims.uconn.edu Fri Feb 23 00:39:22 1996 Return-Path: <@uconnvm.uconn.edu:dmoews@xraysgi.ims.uconn.edu> Received: from UConnVM.UConn.Edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA06036; Fri, 23 Feb 96 00:39:22 EST Received: from venus.ims.uconn.edu by UConnVM.UConn.Edu (IBM VM SMTP V2R2) with TCP; Fri, 23 Feb 96 00:39:17 EST Received: from xraysgi.ims.uconn.edu by venus.ims.uconn.edu (4.1/SMI-4.1) id AA04295; Thu, 22 Feb 96 16:36:36 EST Received: by xraysgi.ims.uconn.edu (931110.SGI/911001.SGI) for @venus.ims.uconn.edu:cube-lovers@life.ai.mit.edu id AA10513; Fri, 23 Feb 96 00:39:02 -0500 Date: Fri, 23 Feb 96 00:39:02 -0500 From: dmoews@xraysgi.ims.uconn.edu (David Moews) Message-Id: <9602230539.AA10513@xraysgi.ims.uconn.edu> To: cube-lovers@life.ai.mit.edu, dmoes@xraysgi.ims.uconn.edu Subject: Implementing Shamir's method Since there seems to be a surge of interest in Shamir's method, I thought I would mention a few points about it and my implementation of it: 1. How the group must be represented in order to use Shamir's method. We suppose that elements of our group G are represented by ordered tuples, which can be ordered lexicographically; we want to generate the list ST in this lexicographical order. Suppose that we have an element s of S, and elements t and u in T which first differ in coordinate i. For Shamir's method to work, we need to be able to order st and su given only the length i initial segments of t and u. This is true for permutation groups if we represent them as acting on {1,...,n} (st compares to su as s(t(i)) compares to s(u(i)).) It is also true for the wreath products occurring in the cube group: suppose G = H wr K, where H is a permutation group acting on {1,...,n}, and K is a product of cyclic groups with index set {1,...,n}. Then if we write an element g of G as ( g(1), ..., g(n), g'(1), ..., g'(n) ), the g(i)'s being in {1,...,n} and the g'(i)'s in the cyclic groups, we can write ( h(1), ..., h(n), h'(1), ..., h'(n) ) ( k(1), ..., k(n), k'(1), ..., k'(n) ) = ( h(k(1)), ..., h(k(n)), h'(k(1)) + k'(1), ..., h'(k(n)) + k'(n) ). Hence if t and u's first difference is in t(i) != u(i), st and su compare as s(t(i)) and s(u(i)), and if t and u's first difference is in t'(i) != u'(i), st and su compare as s'(t(i)) + t'(i) and s'(u(i)) + u'(i). Since you do a lot of composition in Shamir's method, I felt it best to leave the permutations unpacked. I used the wreath product representation above, with H = S_8 x S_12 and K = (Z/3Z)^8 x (Z/2Z)^12. Each permutation then used 8 + 12 + 8 + 12 = 40 bytes. All members of both S and T must be stored in memory (see below.) This used up a lot of memory. (You could, of course, also represent the cube group as a permutation group on the 48 facelets.) 2. The data structure for T. Jerry Bryan has alluded to this. I used a tree each of whose leaves contained a member of T, and each of whose internal nodes contained an index indicating which tuple coordinate was being branched on, a value of this coordinate for each son, and pointers to each son. I also included a pointer to the father to make traversal easier. The data structure for T does not change during the algorithm; you can use it with more than one S at once. 3. The data structure for S. By traversing the T tree approriately, we can output the sequence X(s) = (lexicographical sort of {st | t in T}) for each s. For all elements s of S, we need to store s itself, and a marker to show our position in X(s) (for me, this was just a pointer to the T tree.) We also need enough structure to make merging the X(s)'s easy. I used a `tree of losers' (cf. Knuth, Chapter 5.) Since there seems to be some uncertainty about this, I will go into detail. Let S = {s_0, ..., s_(N-1)}. The tree will then have 2N nodes: N internal ones, 0 through N-1, and N leaves, N through 2N-1. Each internal node i contains a pointer to a leaf. The leaves contain the actual s_j's, as well as the pointers to T. Node i has nodes 2i and 2i+1 as sons if 0 0 do if the next element of X(s_a_0) is greater than the next element of X(s_a_i) then swap a_i and a_0 (we have a new loser) i := floor(i/2) od As you see, we perform many comparisons between the first elements of the X(s_i)'s. It is convenient to store the next element of X(s_i) in the data structure with s_i. This uses up much more memory (a comparable amount with that taken by S and T themselves) but does speed up the program somewhat. -- David Moews dmoews@xraysgi.ims.uconn.edu From mreid@ptc.com Fri Feb 23 17:07:38 1996 Return-Path: Received: from poster (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA05550; Fri, 23 Feb 96 17:07:38 EST Received: from ducie.ptc.com by poster (5.x/SMI-SVR4-NN) id AA07793; Fri, 23 Feb 1996 17:03:11 -0500 Message-Id: <9602232203.AA07793@poster> Received: by ducie.ptc.com (1.38.193.4/16.2.nn) id AA13439; Fri, 23 Feb 1996 17:34:47 -0500 Date: Fri, 23 Feb 1996 17:34:47 -0500 From: michael reid To: cube-lovers@ai.mit.edu Subject: superflip in 20f jerry asks > A 24q process is known for superflip. It is known that superflip is > greater than 19f. Is a 20f process known for superflip? on may 17, 1992, dik winter gave ) Superflip: ) (13+7=20): F B U^2 R F^2 R^2 B^2 U' D F U^2 R' L' U B^2 D R^2 U B^2 U in my exhaustive search for superflip maneuvers of length <= 19f, several (but not all) branches of my search found maneuvers of length 20f. all were equivalent to dik's under the three operations * conjugation of the sequence by a symmetry of the cube * cyclic permutation of the sequence * inversion of the sequence perhaps it is the case that dik's maneuver is "unique" up to these operations. mike From mark.longridge@canrem.com Sat Feb 24 01:13:35 1996 Return-Path: Received: from itchy.crso.com (itchy.canrem.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA18904; Sat, 24 Feb 96 01:13:35 EST Received: by canrem.com (PCB-UUCP 1.1f) id 20BD28; Sat, 24 Feb 96 00:58:14 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Hamiltonian Circuits From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.1310.5834.0C20BD28@canrem.com> Date: Sat, 24 Feb 96 00:25:00 -0500 Organization: CRS Online (Toronto, Ontario) Mike wrote: > there's a general graph theory conjecture that cayley graphs are > hamiltonian (i.e. have hamiltonian circuits). > > if we take the cayley graph formed by generators > {F, F', L, L' U, U', R, R', B, B', D, D'}, the conjecture asserts > that there is a sequence of N quarter turns that visits every > position exactly once and returns to START. > (here N = 43252003274489856000 is the order of the group.) Here's an easy example: Hamiltonian Circuit for < u2, r2 > 12 elements, 12 moves in group to reach each element Identity / \ 1. u2 r2 12. | | 2. r2 u2 11. | | 3. u2 r2 10. | | 4. r2 u2 9. | | 5. u2 r2 8. | | 6. r2 u2 7. \ / Antipode Position at 6. is the antipode Position at 12. is the identity Also, I seem to remember that the slice-squared group had 8 elements, and if you graphed a route through the elements it formed a cube. After drawing such a graph it is not hard to find a hamiltonian circuit (using the edges of the cube as a pathway). This may be true in general for all the platonic solids. (I need to re-check "Regular Polytopes" by Coxeter). So we have 2 examples and no counter-examples of the general graph theory Mike mentions. -> Mark <- From JBRYAN@pstcc.cc.tn.us Thu Mar 7 13:54:55 1996 Return-Path: Received: from pstcc6.pstcc.cc.tn.us by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA18982; Thu, 7 Mar 96 13:54:55 EST Received: from PSTCC6.PSTCC.CC.TN.US by PSTCC6.PSTCC.CC.TN.US (PMDF V5.0-4 #11457) id <01I225GG71DS000HG1@PSTCC6.PSTCC.CC.TN.US> for cube-lovers@ai.mit.edu; Thu, 07 Mar 1996 13:53:23 -0500 (EST) Date: Thu, 07 Mar 1996 13:53:22 -0500 (EST) From: Jerry Bryan Subject: Shamir and M-Conjugacy To: Cube-Lovers Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 7BIT With most of my large breadth-first searches of God's Algorithm, I have used M-conjugacy, where M is the set (and group) of 48 rotations and reflections of the cube. Using M-conjugacy reduces the size of the problem by about 48 times, and allows me to search one or two levels deeper than would be possible without M-conjugacy. I haven't even written a basic program for Shamir's method yet, but it occurs to me that if Shamir's algoritm could be combined with M-conjugacy, tremendous benefits would accrue. As before, we define Q[n] to be the set of positions which are n quarter turns from start, and T[n] to be the union of Q[k] for k in 0..n. I have been thinking in terms of using Shamir's method on T[5] to get Q[6] through Q[10]. But T[5] isn't exactly tiny as it contains 105046 elements. Plus, we already have Q[0] through Q[11] calculated by other means, so we wouldn't be learning anything new. Define Q*[n] to be the set of representative elements of M-conjugacy classes of length n, and T*[n] to be the union of Q*[k] for k in 0..n. T*[5] only contains 2229 elements, which is much more manageable than 105046 elements. T*[6] contains 20624 elements. This is still quite manageable, and might well permit us to calculate Q[12], which would be something new. T*[7] contains 192153 elements. This is right on the bare edge (maybe past the bare edge) of what could be handled on most machines. But if we could handle it, we possibly could calculate Q[13] and Q[14] -- a really major advance in our knowledge of God's algorithm. I haven't yet figured out entirely how to marry Shamir's method with M-conjugacy. But let me provide a general outline of what would have to be done, and identify the major problem areas. Without repeating all the details, recall that we can in theory modify Shamir's method to calculate T[2n] (and all the respective Q[k]'s) as the product (T[n] x T[n]). Very, very roughly speaking, we seek to calculate T*[2n] as the product {T*[n] x T*[n]). But there are many, many complications along the way. Here are some preliminaries. First, given a representative X in Q*[n], we can calculate its entire M-conjugacy class as {m'Xm | m in M}. I usually just write this set as {m'Xm}. In group theory, an element m'Xm is often written as X^m and the set {m'Xm} is often written as X^M. I will adopt the group theory notation to some extent in the remainder of this paper. Given Q*[n], we can create Q[n] by simply expanding the M-conjugacy classes for each X in Q*[n]. In most of my work, the Q[n] which is thus created is sort of virtualized -- created but not stored. I will denote the virtualized version of Q[n] as Q*^M[n] to distinguish it from the real version. Notice that we do have Q*^M[n]=Q[n], so Q*^M[n] can serve as a surrogate for Q[n] most anytime we need it to. Similarly, we denote the virtualized version of T[n] as T*^M[n]. Second, we define * to be a function (not a permutation) which can be composed with permutations to calculate a representative element. We define X* to be Repr(X), which is really Repr{X^M}. So we can have such things as XY* or (X*)(Y*). I have generally implemented X* as min{X^M}. By this, we mean place X^M in lexicographic order, and choose the first element. Basing the representative element of X^M on lexicographic order fits in well with Shamir's method. We now return to the idea of calculating T*[2n] as the product (T*[n] x T*[n]). We first note that the product of representatives is not necessarily a representative, so we would have to calculate (T*[n] x T*[n])* to assure that all we have is representatives. We also note that if we simply calculate all the products st* for s and t in T*[n], we will have about 48 times too few products. On the other hand, if we calculate st* for s and t in T*^M[n], we will have about 48 times more products than we need. What is required is to calculate st* for s in T*[n] and t in T*^M[n]. In other words, we expand the equivalence classes for t but not for s. In a sense, this is what I have always done for my non-Shamir searches, except that I have only advanced by one level of the search at a time. That is, I have calculated (Q*[n] x Q*^M[1])* to get to Q*[n+1]. But remember that Q*^M[1] is just Q[1], which in turn is just Q, the set of quarter turns. That was the sanitized version. The dirty version is that you have to calculate (in lexicographic order) o'(s(m'tm))o, for all o in M, for all m in M, and for all t in T*[n]. The s is a fixed element of T*[n], and the results for all s in T*[n] are merged in standard Shamir fashion. Finally, these products will include representatives and non-representatives alike, and you have to keep only representatives and throw away the non-representatives. Calculating these products is trivial. Getting them to come out in lexicographic order is the hard part. As I said at the beginning, I am not sure I know how to do it yet. But I have some ideas about it that I will be sharing. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990 From zilla@netcom.com Sat Mar 9 05:43:22 1996 Return-Path: Received: from netcom16.netcom.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA01407; Sat, 9 Mar 96 05:43:22 EST Received: by netcom16.netcom.com (8.6.13/Netcom) id CAA23995; Sat, 9 Mar 1996 02:43:16 -0800 From: zilla@netcom.com (Jay Majer) Message-Id: <199603091043.CAA23995@netcom16.netcom.com> Subject: Cube keychains? To: cube-lovers@ai.mit.edu Date: Sat, 9 Mar 1996 02:43:15 -0800 (PST) X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 595 Greetings fellow cubers! I hope someone out there can help me. For the longest time I've been searching for a Rubik's 3x3 Mini Cube Keychain. Are they still being manufactured? If anyone can help me aquire one of these, please e-mail. _______________________________________________________________________ Jay Majer "One must avoid all the chewy chunks in zilla@netcom.com order to attain pure spiritual creaminess." jmajer@ucla.edu -A wise man _______________________________________________________________________ From mouse@collatz.mcrcim.mcgill.edu Wed Mar 13 07:00:50 1996 Return-Path: Received: from Collatz.McRCIM.McGill.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA20095; Wed, 13 Mar 96 07:00:50 EST Received: (root@localhost) by 16027 on Collatz.McRCIM.McGill.EDU (8.6.12 Mouse 1.0) id HAA16027 for cube-lovers@ai.mit.edu; Wed, 13 Mar 1996 07:00:45 -0500 Date: Wed, 13 Mar 1996 07:00:45 -0500 From: der Mouse Message-Id: <199603131200.HAA16027@Collatz.McRCIM.McGill.EDU> To: cube-lovers@ai.mit.edu Subject: Re: Shamir and M-Conjugacy > T*[7] contains 192153 elements. This is right on the bare edge > (maybe past the bare edge) of what could be handled on most machines. Two hundred thousand elements is on the edge? Even assuming an extremely noncompact representation of 20 bytes each (one per non-center cubie), that's only four megabytes. The _smallest_ RAM load I have at home (never mind the machines I have access to at work) is 8 megs, and one machine has 28. Keeping such a list entirely in-core would be no problem at all. Nowhere near the edge. But Jerry Bryan knows what he's talking about too well to make this simple a blunder. Could some kind soul explain what I've obviously missed? der Mouse mouse@collatz.mcrcim.mcgill.edu From JBRYAN@pstcc.cc.tn.us Thu Mar 14 08:56:29 1996 Return-Path: Received: from pstcc6.pstcc.cc.tn.us by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA11164; Thu, 14 Mar 96 08:56:29 EST Received: from PSTCC6.PSTCC.CC.TN.US by PSTCC6.PSTCC.CC.TN.US (PMDF V5.0-4 #11457) id <01I2BN49K2R8000STT@PSTCC6.PSTCC.CC.TN.US>; Thu, 14 Mar 1996 08:56:04 -0500 (EST) Date: Thu, 14 Mar 1996 08:56:03 -0500 (EST) From: Jerry Bryan Subject: Re: Shamir and M-Conjugacy To: der Mouse Cc: cube-lovers@ai.mit.edu Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 7BIT On Wed, 13 Mar 1996, der Mouse wrote: > > T*[7] contains 192153 elements. This is right on the bare edge > > (maybe past the bare edge) of what could be handled on most machines. > > Two hundred thousand elements is on the edge? Even assuming an > extremely noncompact representation of 20 bytes each (one per > non-center cubie), that's only four megabytes. The _smallest_ RAM load > I have at home (never mind the machines I have access to at work) is 8 > megs, and one machine has 28. Keeping such a list entirely in-core > would be no problem at all. Nowhere near the edge. > > But Jerry Bryan knows what he's talking about too well to make this > simple a blunder. Could some kind soul explain what I've obviously > missed? > Well, I would argue whether I know what I'm talking about when it comes to marrying Shamir with M-conjugacy. I'm just sort of thinking out loud right now, not implementing any code. But at one point, Bob Moews reported that his implementation of Shamir required 104 bytes per position. Of the 104 bytes, 48 bytes were the position itself. The rest of the bytes were queues, pointers, and various overhead of that sort. I've been guessing that to keep up with all the pointers and so forth required for M-conjugacy, it might take 200 bytes or so per position. But assume optimistically that it could be compressed down to 100 bytes per position. Then, we are up to about 20 meg for T*[7], and about 180 meg for T*[8]. I really think that's a bit too optimistic, but it's probably not too far off. But if this guess is off by even a factor of two, then you would need 40 meg for T*[7]. On the other hand, assume these memory estimates are approximately correct. At some point, the constraint will become time rather than memory. Even on a very fast machine, it might take dozens of years rather than hundreds of hours to calculate something like T[14] or T[16] as (T*[7] x T*[7]) or as (T*[8] x T*[8]). = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990 From DNewfield@virginia.edu Mon Mar 18 14:02:46 1996 Return-Path: Received: from virginia.edu (mars.itc.Virginia.EDU) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA08146; Mon, 18 Mar 96 14:02:46 EST Received: from archive.cs.virginia.edu by mail.virginia.edu id aa02619; 18 Mar 96 13:19 EST Received: from cobra.cs.Virginia.EDU (cobra-fo.cs.Virginia.EDU [128.143.136.17]) by archive.cs.Virginia.EDU (8.7.1/8.6.6) with SMTP id NAA07908 for ; Mon, 18 Mar 1996 13:19:27 -0500 (EST) Received: from localhost by cobra.cs.Virginia.EDU (5.x/SMI-2.0) id AA15001; Mon, 18 Mar 1996 13:19:22 -0500 Sender: din5w@virginia.edu Message-Id: <31487128.68F9@cs.virginia.edu> Date: Thu, 14 Mar 1996 14:19:04 -0500 From: Dale Newfield Organization: Computer Science Department X-Mailer: Mozilla 2.0 (Win95; I) Mime-Version: 1.0 To: cube-lovers@ai.mit.edu Subject: Orbix Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Status: RO X-Status: I just saw a commercial for a puzzle called "Orbix." It was a sphere covered with (I think) 12 colored reflector-like circles, each with a button in the center. They said that there are 4 levels. It seemed to be much like "luminations." I'm sure that I will buy the first one I find. :-) -Dale Newfield From isaacs@hpcc01.corp.hp.com Mon Mar 18 18:46:45 1996 Return-Path: Received: from paloalto.access.hp.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA22316; Mon, 18 Mar 96 18:46:45 EST Received: from hpcc01.corp.hp.com by paloalto.access.hp.com with ESMTP (1.37.109.16/15.5+ECS 3.3) id AA006382803; Mon, 18 Mar 1996 15:46:43 -0800 Received: by hpcc01.corp.hp.com (1.37.109.16/15.5+ECS 3.3) id AA121182802; Mon, 18 Mar 1996 15:46:43 -0800 From: Stan Isaacs Message-Id: <199603182346.AA121182802@hpcc01.corp.hp.com> Subject: Re: Orbix To: din5w@cs.virginia.edu (Dale Newfield) Date: Mon, 18 Mar 96 15:46:41 PST Cc: cube-lovers@ai.mit.edu In-Reply-To: <31487128.68F9@cs.virginia.edu>; from "Dale Newfield" at Mar 14, 96 2:19 pm Mailer: Elm [revision: 70.85.2.1] > > I just saw a commercial for a puzzle called "Orbix." It was a sphere > covered with (I think) 12 colored reflector-like circles, each with a > button in the center. They said that there are 4 levels. It seemed to > be much like "luminations." I'm sure that I will buy the first one I > find. :-) > -Dale Newfield No, its more like "Light's Out", on a sphere. It's a nice puzzle (although the first one I bought had a broken button, so I had to exchange it.) It cost about $20 at Toys-R-Us. The surface of the sphere has 12 lights/buttons, dodecahedrally arranged. When you push one, in the first puzzle, the 6 surrounding lights change their parity - if they're on, they go out and vice versa. The goal is to get all the lights on, after some random starting pattern. The other puzzles have a different combination of which lights go on when you press a light: I think the second turns out the 6 on the opposite side from the one pressed, and only do so if the pressed light was orignally off (or something like that). Obviously, I haven't had time to study the details much yet. The puzzle feels nice, looks good, and should be worth the $20. -- Stan Isaacs From rodrigo@lsi.usp.br Mon Mar 25 19:01:33 1996 Return-Path: Received: from psychodrome.lsi.usp.br ([200.246.166.193]) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA24113; Mon, 25 Mar 96 19:01:33 EST Received: (from rodrigo@localhost) by psychodrome.lsi.usp.br (8.6.12/8.6.9) id UAA00197; Mon, 25 Mar 1996 20:57:26 -0300 Date: Mon, 25 Mar 1996 20:57:25 -0300 (EST) From: Rodrigo de Almeida Siqueira To: Cube-Lovers@ai.mit.edu Subject: A handling system to fix the Cube Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII ------- Forwarded message -------- Date: Mon, 25 Mar 1996 19:29:21 From: jbyland@ln.active.ch Name = Byland John URL = http://www2.active.ch/~jbyland/ comments = My Name is Johnny Byland and study Computer-Sience at the Ingenierschule Zuerich. For a work for diploma, we build a Handling-System, who can fix the Rubik-Cube itself. This System can detect colors and make moves in all relevant axis. We control the system with a PC, programmed in Delphi. If you have good ideas, how we can solve the cube as simple as possible (alogorithm etc), we are recommend, you can send it. Thanks Johnny Byland Dorfstr. 12 CH-8330 Pfaeffikon ZH PS: Have a look at http://www2.active.ch/~jbyland/ E-mail: jbyland@ln.active.ch From JBRYAN@pstcc.cc.tn.us Tue Mar 26 08:32:56 1996 Return-Path: Received: from pstcc6.pstcc.cc.tn.us by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA11793; Tue, 26 Mar 96 08:32:56 EST Received: from PSTCC6.PSTCC.CC.TN.US by PSTCC6.PSTCC.CC.TN.US (PMDF V5.0-4 #11457) id <01I2SDSB87TS000GWT@PSTCC6.PSTCC.CC.TN.US> for cube-lovers@ai.mit.edu; Tue, 26 Mar 1996 08:32:33 -0500 (EST) Date: Tue, 26 Mar 1996 08:32:33 -0500 (EST) From: Jerry Bryan Subject: Electronic Citations To: Cube-Lovers Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 7BIT If I may be permitted a slightly off subject posting .... Much materal is now online (such as Cube-Lovers) that was never online before, and much of the online material is being cited in research and other papers. I just ran across the best source I have seen for how to cite such material -- http://www.taft.cc.ca.us/www/tc/tceng/mla.html. Since Cube-Lovers is E-mail and archives of E-mail, here is an excerpt that addresses citations for E-mail: E-mail, Listserv, and Newslist Citations Give the author's name (if known), the subject line from the posting in quotation marks, and the address of the listserv or newslist, along with the date. For personal e-mail listings, the address may be omitted. Bruckman, Amy S. "MOOSE Crossing Proposal." mediamoo@media. mit.edu (20 Dec. 1994). Seabrook, Richard H. C. "Community and Progress." cybermind @jefferson.village.virginia.edu (22 Jan. 1994)

Thomson, Barry. "Virtual Reality." Personal e-mail (25 Jan. 1995). = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990 From bagleyd@hertz.njit.edu Thu Mar 28 11:16:46 1996 Return-Path: Received: from hertz.njit.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07483; Thu, 28 Mar 96 11:16:46 EST Received: (from bagleyd@localhost) by hertz.njit.edu (8.7.3/8.6.9) id LAA21296 for cube-lovers@life.ai.mit.edu; Thu, 28 Mar 1996 11:15:55 -0500 Date: Thu, 28 Mar 1996 11:15:55 -0500 From: bagleyd Message-Id: <199603281615.LAA21296@hertz.njit.edu> To: cube-lovers@life.ai.mit.edu Subject: simple windows3.1 puzzles Hi I finally got around to making a web page http://hertz.njit.edu/~bagleyd/ In it you will find Simple Windows3.1 puzzles. The more complicated ones are still in development. The best of the bunch is wmlink, which is a Missing Link puzzle. Cheers, /X\ David A. Bagley // \\ bagleyd@hertz.njit.edu http://hertz.njit.edu/~bagleyd/ (( X xlockmore, new stuff for xlock @ ftp.x.org//contrib/applications \\ // altris, tetris games for x @ ftp.x.org//contrib/games/altris \X/ puzzles, magic cubes for x @ ftp.x.org//contrib/games/puzzles From idemoya@mednet.med.miami.edu Wed Apr 3 20:08:01 1996 Return-Path: Received: from miasun.med.miami.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA24596; Wed, 3 Apr 96 20:08:01 EST Received: from mednet.med.miami.edu by miasun.med.miami.edu (4.1/4.1-rrossie) id AA22773; Wed, 3 Apr 96 20:15:11 EST Received: from ccMail by mednet.med.miami.edu (SMTPLINK V2.11 PreRelease 4) id AA828590686; Wed, 03 Apr 96 20:05:22 EST Date: Wed, 03 Apr 96 20:05:22 EST From: idemoya@mednet.med.miami.edu Message-Id: <9603038285.AA828590686@mednet.med.miami.edu> To: cube-lovers@life.ai.mit.edu Return-Receipt-To: idemoya@mednet.med.miami.edu Subject: Help me find a RUBIK'S CUBE............. Hello fellow Rubik's Cube lover: I must quickly produce a Rubik's cube in the very near future. Please provide me with information that might help me obtain one brand-new unit (or as close to that as possible). Your copperation is greatly appreciated. Ivan From bernier@login.net Thu Apr 4 21:03:49 1996 Return-Path: Received: from comback.login.qc.ca by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA16433; Thu, 4 Apr 96 21:03:49 EST Received: from v34dialup-50.praline.net (v34dialup-50.praline.net [199.202.90.180]) by comback.login.qc.ca (8.6.12/8.6.5) with SMTP id UAA21525 for ; Thu, 4 Apr 1996 20:50:26 -0500 Date: Thu, 4 Apr 1996 20:50:26 -0500 Message-Id: <199604050150.UAA21525@comback.login.qc.ca> X-Sender: bernier@login.net (Unverified) X-Mailer: Windows Eudora Version 1.4.4 Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable To: cube-lovers@life.ai.mit.edu From: bernier@login.net (Denise Lemoine) Subject: list bonjour j'aimerais ces casse-tetes la!!! denise lemoine 15 cout coaticoof p.q. Madame, Je suis un peu m=E9lang=E9e. Votre mari m'a dit que vous ne vouliez plus le compte. En tout cas, j'attends votre cheque. L'adresse est dans ma= signature. Salutations, At 21:29 96/03/23 -0500, you wrote: > > je ne trouve lpus l'adresse. > > me faire parvenir s.v.p. > >denise lemoine >coaticook > > From aaweint@io.org Fri Apr 5 16:41:48 1996 Return-Path: Received: from io.org by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA19765; Fri, 5 Apr 96 16:41:48 EST Received: from fester07.slip.yorku.ca (fester07.slip.yorku.ca [130.63.219.78]) by io.org (8.6.12/8.6.12) with SMTP id QAA22733 for ; Fri, 5 Apr 1996 16:41:28 -0500 Message-Id: <2.2.16.19960405214133.47a74e6a@io.org> X-Sender: aaweint@io.org (Unverified) X-Mailer: Windows Eudora Pro Version 2.2 (16) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Fri, 05 Apr 1996 16:41:33 -0500 To: cube-lovers@ai.mit.edu From: Aaron Weintraub Subject: Square-1 question Hi... I recently got a hold of a Square-1 puzzle and have been trying to solve it. I can get to the point where it's done, but two edges on one side are swapped. How do I swap them back? Is this a parity problem? Every move I have that swaps edges does TWO pairs are a time, so I can't get there with what I have. Or can I? Any help would be appreciated. -Aaron From mouse@collatz.mcrcim.mcgill.edu Sun Apr 7 09:27:42 1996 Return-Path: Received: from Collatz.McRCIM.McGill.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA04677; Sun, 7 Apr 96 09:27:42 EDT Received: (root@localhost) by 1565 on Collatz.McRCIM.McGill.EDU (8.6.12 Mouse 1.0) id JAA01565 for cube-lovers@ai.mit.edu; Sun, 7 Apr 1996 09:27:39 -0400 Date: Sun, 7 Apr 1996 09:27:39 -0400 From: der Mouse Message-Id: <199604071327.JAA01565@Collatz.McRCIM.McGill.EDU> To: cube-lovers@ai.mit.edu Subject: Re: Square-1 question > I recently got a hold of a Square-1 puzzle and have been trying to > solve it. I can get to the point where it's done, but two edges on > one side are swapped. How do I swap them back? Is this a parity > problem? Every move I have that swaps edges does TWO pairs are a > time, so I can't get there with what I have. Or can I? I'm not familiar with Square-1...but if, as seems lkely, it's a square that you have to get into some arrangement, then consider turning the whole puzzle 90 or 180 degrees and trying again; that may introduce an odd permutation and thus make a solution possible. Or depending on the definition of "solved" - as I say, I don't know the puzzle - maybe go for a mirror-reflected state. der Mouse mouse@collatz.mcrcim.mcgill.edu From nichael@sover.net Sun Apr 7 15:36:20 1996 Return-Path: Received: from maple.sover.net by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10461; Sun, 7 Apr 96 15:36:20 EDT Received: from [204.71.18.82] (st32.bratt.sover.net [204.71.18.82]) by maple.sover.net (8.7.4/8.7.3) with SMTP id PAA09328; Sun, 7 Apr 1996 15:36:09 -0400 (EDT) Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Sat, 6 Apr 1996 15:36:52 -0400 To: Aaron Weintraub , cube-lovers@ai.mit.edu From: nichael@sover.net (Nichael Lynn Cramer) Subject: Re: Square-1 question At 4:41 PM 4/5/96, Aaron Weintraub wrote: >Hi... > >I recently got a hold of a Square-1 puzzle and have been trying to solve it. >I can get to the point where it's done, but two edges on one side are >swapped. How do I swap them back? Is this a parity problem? Every move I >have that swaps edges does TWO pairs are a time, so I can't get there with >what I have. Or can I? Any help would be appreciated. > >-Aaron The quick answer is, yes, in spite of appearances you are actually very far from finished. A quick hint is attached below. (This is only a hint in that it's been two or three years since I worked with a Square One. At that time I kept notes and was going to write up a complete solution but I don't think I ever got around to doing it [Alan? Do you remember?] If I can find those, or can remember more complete details --time to get the Sq1 back out-- I'll pass along more details.] --- --- -0-- --- --- --- -- -- --- --- --- --- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --- -- -- -- -- -- -- -- -- -- -- -- -- Hint: You're right that you need to swap two pairs together. The issue here is that you need to simultaneously swap a pair of edges (the triangular pieces) and a pair of corners (the quadrilaterals). And, yes, you can actually do this. ;-) In short, in this state the corners only _appear_ to be in the correct locations. An analoguous case can occur on the 4X cube where the cube appears to be _almost_ complete except that two edge peices are flipped. Again, it looks like you're close to done, but more accurately you're almost completely diametrically "across the space of solutions". Nichael nichael@sover.net __ http://www.sover.net/~nichael Be as passersby -- IC From nichael@sover.net Sun Apr 7 15:37:32 1996 Return-Path: Received: from maple.sover.net by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10480; Sun, 7 Apr 96 15:37:32 EDT Received: from [204.71.18.82] (st32.bratt.sover.net [204.71.18.82]) by maple.sover.net (8.7.4/8.7.3) with SMTP id PAA09418; Sun, 7 Apr 1996 15:37:23 -0400 (EDT) Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Sat, 6 Apr 1996 15:38:05 -0400 To: Aaron Weintraub , cube-lovers@ai.mit.edu From: nichael@sover.net (Nichael Lynn Cramer) Subject: Re: Square-1 question At 4:41 PM 4/5/96, Aaron Weintraub wrote: >Hi... > >I recently got a hold of a Square-1 puzzle and have been trying to solve it. >I can get to the point where it's done, but two edges on one side are >swapped. How do I swap them back? Is this a parity problem? Every move I >have that swaps edges does TWO pairs are a time, so I can't get there with >what I have. Or can I? Any help would be appreciated. > >-Aaron The quick answer is, yes, in spite of appearances you are actually very far from finished. A quick hint is attached below. (This is only a hint in that it's been two or three years since I worked with a Square One. At that time I kept notes and was going to write up a complete solution but I don't think I ever got around to doing it [Alan? Do you remember?] If I can find those, or can remember more complete details --time to get the Sq1 back out-- I'll pass along more details.] --- --- -0-- --- --- --- -- -- --- --- --- --- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --- -- -- -- -- -- -- -- -- -- -- -- -- Hint: You're right that you need to swap two pairs together. The issue here is that you need to simultaneously swap a pair of edges (the triangular pieces) and a pair of corners (the quadrilaterals). And, yes, you can actually do this. ;-) In short, in this state the corners only _appear_ to be in the correct locations. An analoguous case can occur on the 4X cube where the cube appears to be _almost_ complete except that two edge peices are flipped. Again, it looks like you're close to done, but more accurately you're almost completely diametrically "across the space of solutions". Nichael nichael@sover.net __ http://www.sover.net/~nichael Be as passersby -- IC From modestr@federal.unisys.com Mon Apr 8 12:03:25 1996 Received: from www.han.federal.unisys.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA08118; Mon, 8 Apr 96 12:03:25 EDT Received: from homer.MCLN.Federal.Unisys.COM by www.han.federal.unisys.com (8.6.12/mls/8.0) id MAA17345; Mon, 8 Apr 1996 12:03:19 -0400 Return-Path: Received: from h3-90.MCLN.Federal.Unisys.COM by homer.MCLN.Federal.Unisys.COM (8.6.12/mls/4.1) id MAA27608; Mon, 8 Apr 1996 12:06:35 -0400 Message-Id: <199604081606.MAA27608@homer.MCLN.Federal.Unisys.COM> Date: Mon, 08 Apr 96 12:03:28 -0700 From: Ron Modest X-Mailer: Mozilla 1.22 (Windows; I; 16bit) Mime-Version: 1.0 To: Cube-Lovers@ai.mit.edu Subject: square 1 help Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset=iso-8859-1 Regarding swapping two edges on Square-1. You prompt me to write about something I have been meaning to get around to for a long time. Long ago I found a way to swap two edges using a complicated sequence. After considerable unsuccessful effort to improve the solution, I bought Richard Snyders amazing book "Turn to 1" from Puzzletts. ( HTTP://WWW.PUZZLETTS.COM/ ) His solution is essentially the same as mine. His method of documentation obscures what is really going on and consequently it would be very hard to memorize. The principal is straight forward and follows these steps. Move all the edge pieces to the same side in an orderly sequence. Turn the side that has all corner pieces, one position. Retrace all the moves that brought the edge pieces to the same side. Fix any thing that got messed up in the process. (this is what I call collateral damage) Snyder's solution optimizes the process to minimize the collateral damage but any variation on the steps listed above will work. On a related subject.... How to get the puzzle into the shape of a cube after initial scrambling. Snyders book shows pictures of all possible scrambled shapes. Each has instructions for making a few turns and the next diagram to refer to. This process may be optimal for getting it into a cube shape but it is nearly impossible to memorize. I am sure everyone who works with the puzzle learns some shapes that are close to the cube shape but it may seem nearly impossible to generally solve in any orderly way. Well consider the following strategy: Collect all the edge pieces on the same side. They can all be side by side in what Snyder calls the Hoofprint pattern or in the Moon pattern that has two groups of four edges on the same side. Then move half of the edges to the opposite side. Then move half of the edges from the top to the bottom and half of the edges from the bottom to the top, but do so in a way that separates them into groups of two. You are then with a couple of twist of making a cube. The beauty of the strategy is that to obtain perfect final symmetry, you first take it to a position of maximum asymmetry. Every turn after that keeps it symmetric. This method will not generally be the optimum solution but it is straight forward and easily learned. I said this is related to the previous subject of swapping two edges because both require reaching a position will all the edge pieces on one side. I might not have ever found the method for swapping two edges if I had not first adopted this method for getting it into a cube shape first. While I am sending out a message let me recommend that everyone include their mail address when the send a message. Recently a couple of messages did not. I would have send the author a personal message answering a simple question but didnt want to bother everyone else. One such question was about obtaining 3x3x3 cubes. They are available in many chain toy stores including "The Game Keeper" and "LearningSmith". Most puzzles are available from Puzzletts also. I also notice that several local stores are carrying Rubiks Magic again. The colors are different than the originals. Cube Trivia.... In 1982 a Worlds Fair was held in Knoxville Tenn. USA.. At the enterance to the Hungarian pavalion was a Rubik's Cube about 4 feet on a side mounted on a pedistal. At that time a Rubik's Cube was a universially recognized symbol. Walter Smith near Washington D.C. WALTS@FEDERAL.UNISYS.COM From aaweint@io.org Mon Apr 8 21:22:55 1996 Return-Path: Received: from io.org by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA02184; Mon, 8 Apr 96 21:22:55 EDT Received: from newman03.slip.yorku.ca (newman03.slip.yorku.ca [130.63.219.193]) by io.org (8.6.12/8.6.12) with SMTP id VAA18848 for ; Mon, 8 Apr 1996 21:22:30 -0400 Message-Id: <2.2.16.19960409012207.5be77a10@io.org> X-Sender: aaweint@io.org X-Mailer: Windows Eudora Pro Version 2.2 (16) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Mon, 08 Apr 1996 21:22:07 -0400 To: cube-lovers@ai.mit.edu From: Aaron Weintraub Subject: Square-1 Question Hi, I just wanted to thank everyone who gave me some insight as to how to go about attacking the parity problem in Square-1. It was, indeed as I thought, a parity issue like the double flipped edges in the 4x4x4, and not just some oversight on my part. Ron, your tips were particularily helpful. I didn't have to buy any books or anything, and I can now solve it every time. I've got to go find a new puzzle now. Aaron aaweint@io.org From walts@federal.unisys.com Tue Apr 30 07:42:15 1996 Received: from www.han.federal.unisys.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA12966; Tue, 30 Apr 96 07:42:15 EDT Received: from homer.MCLN.Federal.Unisys.COM by www.han.federal.unisys.com (8.6.12/mls/8.0) id HAA14387; Tue, 30 Apr 1996 07:42:12 -0400 Return-Path: Received: from h3-105.MCLN.Federal.Unisys.COM by homer.MCLN.Federal.Unisys.COM (8.6.12/mls/4.1) id HAA22489; Tue, 30 Apr 1996 07:45:42 -0400 Message-Id: <318626DD.291E@federal.unisys.com> Date: Tue, 30 Apr 1996 07:42:38 -0700 From: Walt Smith X-Mailer: Mozilla 2.0 (Win16; I) Mime-Version: 1.0 To: cube-lovers@ai.mit.edu Subject: Rubiks Revenge X-Url: http://home.netscape.com/ Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Rubiks Revenge presents several difficult cases when the last few pieces are reached. There has been discussion on this over the years but it does not seem to have reached closure. Mark Longridges list of best known solutions, (http://admin.dis.on.ca:80/~cubeman/cmoves.txt) lists some of these but here are some improved solutions of my own and additional operators that are needed to solve it. If the center four are done on all sides and the edge pieces are paired up, it can be can be treated like a 3x3x3 Rubik Cube. Several cases come up at the end that can not occur on a 3x3x3. If the corners are done and the last few edges are left for last, four cases occur. Here are my methods that are shorter than any others I have seen. Case 1. The last three edges can be solved with 3x3x3 techniques. Case 2. Two edge pairs are swapped. (swaps RF and RB) d2 R2 d2 rR2 d2 r2 (7) This is based on combining the following two sequences: (d2 R2)2 d2 and (d2 r2)2 Each of these is useful in itself. This is shorter than Marks Longridges p4. (Marks p4 is mislabeled Opp. It should be Adj and p5 should be labeled Opp) Case 3. A single edge pair is flipped. (flips BL) L2 d1 R2 d1 R2 d3 L2 u3 B2 u2 B2 u3 B2 R2 B1 r3 B3 R2 B1 r1 B1 (21) This is shown in four groups because it proceeds in stages. The second move fixes the parity, the first along with 3rd through 12th fix the faces and the last group of moves fix the edges. This is shorter than Marks p3. Case 4. Both Case 2 and Case 3 exist. The flipped edge pair might be one of the swapped edge pairs or it might not be. Obviously this can be solved by using the techniques of Case 2 and 3 applied separately. I have always thought that it should be possible to find an operator that is shorter than the sum of these two and possibly shorter that Case 3. I have not done as much study on this case as the others. If you want to solve the corners last (avoids Case 3 and 4), you may still need to solve Case 2 but you may also need to swap two corner pieces. This can be done by applying Case 2 then fixing the edges then corners. This will take about 40 turns. The following does it quicker. (swaps LDB and LDF with the bottom cubie faces remaining bottom faces.) R3 D1 L1 D3 R1 D2 L3 D1 L1 D2 L1 U3 r2 F2 r2 fF2 r2 f2 U1 L2 (21) It is listed in three groups to make it easier to memorize as it proceed in three stages. This is shorter than the sequence in Mark Jeays on-line solution at http://qlink.queensu.ca/~4mj/rr.html ( or link from Mark Longridges home http://admin.dis.on.ca:80/~cubeman/ ) I do not have any books on Rubiks Revenge. If someone out there does, please see how these solutions compare. If anyone has shorter solutions, either that they have developed or found in books please submit them so Mark L. can improve his list (and so I can improve my technique). Also Marks p1 does not work. Can anyone fix it? Walter Smith near Washington D.C. walts@federal.unisys.com From a.southern@ic.ac.uk Tue Apr 30 08:58:46 1996 Return-Path: Received: from punch.ic.ac.uk by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AB15173; Tue, 30 Apr 96 08:58:46 EDT Received: from judy.ic.ac.uk by punch.ic.ac.uk with SMTP (PP); Tue, 30 Apr 1996 13:52:50 +0100 Received: from mecmdb.me.ic.ac.uk (mecmdb-gw.me.ic.ac.uk [155.198.64.90]) by judy.ic.ac.uk (8.7.5/8.7.5) with SMTP id NAA02708 for ; Tue, 30 Apr 1996 13:52:35 +0100 (BST) Received: from wh23.hr by mecmdb.me.ic.ac.uk (5.65/4.1) id AA02489; Tue, 30 Apr 1996 13:52:34 +0100 Date: Tue, 30 Apr 1996 13:52:34 +0100 Message-Id: <9604301252.AA02489@mecmdb.me.ic.ac.uk> X-Sender: ars2@mecmdb.me.ic.ac.uk (Unverified) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" X-Priority: 2 (High) To: cube-lovers@ai.mit.edu From: a.southern@ic.ac.uk (The Official Thermodynamics Fan Club of the UK.) Subject: Square-1, Super Cubix, Masterball and Rubik's Revenge. X-Mailer: Hi, I'm on the cube-lovers mailing list. Bloody Hell! If someone had told me what a square-1 was, I would have been able to help with that query. I know the puzzle as "Super Cubix" which was written on the side of the 'cube'. I solved this puzzle about six months ago and in the same way as Ron Modest did. Have you tried the Masterball? It is solved in a very similar way, but there again it does have very similar properties (having to rotate in one direction by pi, but any other multiple in the rest). The Masterball has a web site (http://wsd.com/masterball) in which it claims to be unique because there are no fixed segments. I once borrowed a 4x4x4 Rubik's Revenge from a friend, and it appeared to have no fixed segments. I believe the Masterball to be a different puzzle, but with similar internal workings. What do you lot think? p.s. I'm sure this is a common question, but I have many 3x3x3, and one 5x5x5, can I still get a 4x4x4 anywhere? would anyone consider selling one to me? p.p.s. I'm in London. From JBRYAN@pstcc.cc.tn.us Wed May 1 18:33:37 1996 Return-Path: Received: from pstcc6.pstcc.cc.tn.us by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17358; Wed, 1 May 96 18:33:37 EDT Received: from PSTCC6.PSTCC.CC.TN.US by PSTCC6.PSTCC.CC.TN.US (PMDF V5.0-4 #11457) id <01I4799SSU8G001E0M@PSTCC6.PSTCC.CC.TN.US> for cube-lovers@ai.mit.edu; Wed, 01 May 1996 18:33:30 -0500 (EST) Date: Wed, 01 May 1996 18:33:30 -0500 (EST) From: Jerry Bryan Subject: Shamir and M-Conjugacy Don't Mix To: Cube-Lovers Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Transfer-Encoding: 7BIT I have reluctantly concluded that encoding the nodes of a breadth first search tree as resentative elements of M-conjugacy classes cannot be combined with Shamir's method. The short version of the reason is that Shamir works only for post-multiplying, and we must both pre-multiply and post-multiply in order to calculate M-conjugates. It is possible, I think, to use a number of what might be called "clever hacks" involving M-conjugacy to reduce rather considerably the memory requirements of a program implementing Shamir's method, but the basic method cannot store just the representative elements. I will describe the clever hacks if and when I get a working program. How "clever" the clever hacks are may lie in the eye of the beholder. In all cases, they exchange reduced storage requirements for increased running time. It is always a question as to whether such trade-offs are advantageous or not. The longer explanation follows. I will be starting with some real basics. Almost any reasonable introductory or advanced math book will talk about functions. There are two basic views of what a function is. In one view, a function is a non-empty set X, a non-empty set Y, and some general rule or correspondence such that for every x in X, there is exactly one y in Y. In the other view, you start out with the set of all ordered pairs (x,y) with x in X and y in Y. This set is usually called X x Y (X cross Y). A function is then a non-empty subset of X x Y such that every x appears exactly one time as the left hand element of the ordered pair, so that again for every x in X there is exactly one y in Y. The second definition is probably more accurate, but it loses (on purpose, perhaps) the intuitive feel that there is some sort of "general" rule relating X and Y. Indeed, for a finite X and Y, there may be no shorter way to specify a particular function than simply to list the set of ordered pairs of which it is comprised. A function where X and Y are the same set is said to be a function "on X". A function may be one-to-one or onto or both. There are many (equivalent) definitions, but my favorites are that a function is onto if there is at least one x for every y, and a function is one-to-one if there is at most one x for every y. Hence, a function is both one-to-one and onto if there is exactly one x for every y. This condition is necessary if we wish to be able to run the function backwards, that is, if we wish to have an inverse function. Finally, a function that is on a set and which is one-to-one and onto is a permutation. We model the Rubik's cube as a set of permutations. Suppose F and G are functions. In algebra and calculus, we define the composition of two functions something like the following: FoG(x)=F(G(x)). Proper treatment of this definition would require some care in handling the domain and range of the respective functions. But we will dispose of this issue by simply stipulating that F and G are permutations on the same set. The algebra/calculus notation for function composition yields a right-to-left evaluation of the functions. This is especially visible if we compose more than two functions, e.g., FoGoH(x)=F(G(H(x))). In group theory, function composition is more typically written left-to-right such as HGF for the example at hand, with debates about where the argument goes. I prefer in front -- (x)HGF. In Cube Theory, we almost *always* write operators left-to-write, following group theory rather than algebra/calculus. This whole left-to-right vs. right-to-left issue is critical for for proper implementation of Shamir. It is especially critical to get it right because essentially all programming languages follow the algebra/calculus model, whereas Cube Theory follows group theory. Hence, everything is always backwards to some extent in a program. I'm an *old* programmer, so my first higher level programming language (after assembler) was FORTRAN. FORTRAN lets you have statements such as Y=X(I) or Y=SQRT(X). FORTRAN has rather obtuse semantics and is hard to compile. I can remember at the time I learned FORTRAN being puzzled by how the compiler could figure out whether parentheses meant function arguments or whether parentheses meant subscripts. More "modern" languages (say, those less than 20 years old) tend to use square brackets for subscripts, making the compiler's job a bit easier. But the vagaries of FORTRAN serve us well at this point. Suppose we want to define a permutation (which is after all, just a function) on 1..3. We define F as what old FORTRAN programmers called an array with three elements (more often called a vector these days). Then, we can assign values to the array elements, such as F(1)=2, F(2)=3, and F(3)=1. Finally, we can write statements such as Y=F(X), which look and act like functions, although FORTRAN thinks of them as arrays. (Well, F, X, and Y would have to be defined as INTEGERS, which is not very FORTRANish, but so be it). What about function composition, say G(F(X))? It works, but be careful what you mean. A very short snippit of code might look something like the following: X=1 Y=F(X) Z=G(F(X)) PRINT Y, Z Function composition works as advertized even though these things are really arrays. But the composition is calculated only for one particular value of X, namely X=1. If we want to calculate the full=blown composition H=GoF (group theory, H=FG), the code snippit would be H(1)=G(F(1)) H(2)=G(F(2)) H(3)=G(F(3)) As you can see, this programming way of implementing a permutation as an array is really the second way in which math books define a function, namely as a set of ordered pairs. For example, the function F from above is simply F={ (1,2), (2,3), 3,1) }. But the X values were never stored explicitly. Rather, they were the array indices. We would say that the F array stores the Y values as a vector. In this case, we would say that F=[2,3,1]. Notice that it is somewhat arbitrary whether X is represented by the indices and Y is represented by the vector, or vice versa. The way I have shown it seems more natural, but the vice versa is certainly tenable. Notice also that if we think of the vice versa where X is represented by the vector and Y is represented by the indices, then we have the inverse function F'. Hence, the same vector can represent both F and F'. As a practical matter, I really prefer to have indices represent X and to store the inverse as a separate vector. Let me switch to a more modern look and feel, using square brackets. The code to calculate an inverse would then look something like. F_inverse[F[1]] := 1; F_inverse[F[2]] := 2; F_inverse{F[3]] := 3; You would really do this with a loop, so it would be something like For i := 1 to 3 F_inverse[F[i]] := i; If you translate this loop back into group theory, it more or less states the identity FF'=I (the looping just makes sure that we touch all our X values -- the index i is our X value, and the order of F and F' is backwards between our program and group theory). The key component of Shamir's method involves multiplying a permutation t by each permutation s in a set S, where the set S is in lexicographic order. I want to show what happens with both pre-multiplying and post-multiplying. In order to deal with representative elements of M-conjugacy classes, we need both to pre-multiply by m' and to post-multiply by m, so the issue of pre-multiplying vs. post-multiplying is critical. I will use permutations on 1..4 in vector notation for my examples. t S tS [3,1,4,2] [1,2,3,4] = [3,1,4,2] [3,1,4,2] [1,2,4,3] = [4,1,3,2] [3,1,4,2] [1,3,4,2] = [4,1,2,3] [3,1,4,2] [2,1,3,4] = [3,2,4,1] [3,1,4,2] [3,1,2,4] = [2,3,4,1] [3,1,4,2] [4,3 2,1] = [2,4,1,3] S t St [1,2,3,4] [3,1,4,2] = [3,1,4,2] [1,2,4,3] [3,1,4,2] = [3,1,2,4] [1,3,4,2] [3,1,4,2] = [3,4,2,1] [2,1,3,4] [3,1,4,2] = [1,3,4,2] [3,1,2,4] [3,1,4,2] = [4,3,1,2] [4,3,2,1] [3,1,4,2] = [2,4,1,3] Let's take the case of St first. This is classic Shamir. S is in lexicographic order. Going from S to St, every 1 has been replaced by a 3, every 2 has been replaced by a 1, every 3 has been replaced by a 4, and every 4 has been replaced by a 2. We can get St into lexicographic order by sorting S in the order 2 first, 4 second, 1 third, and 3 fourth. The vector [2,4,1,3] which controls this alternative sorting order is simply t'. Hence, we don't really have to sort St if S is made into a tree. Rather, we traverse the S tree using t' as a template to define an alternative order of traversal, and St automagically pops out in lexicographic order. (By the way, there is a minor error in one of my previous posts. Allen Bawden used right-to-left notation in his original Shamir article. I copied what he wrote thinking he was using left-to-right notation. To properly "copy" what he wrote and also put it in left-to-write notation, I needed to reverse everything, but I failed to do so. Hopefully, everything will be consistent and correct in this article.) The tS case is much trickier. Think of S as a matrix. To get to tS, what you do is permute the columns. With the particular t we are using, column 3 becomes column 1, column 1 becomes column 2, column 4 becomes column 3, and column 2 becomes column 4. I really can't think of any Shamir-like tree traversal that would put tS into lexicographic order. To see the nature of the problem very clearly, look at the original S and think of sorting the rows using column 3 as the major sort. We can't really move the rows around of course, because we only have one S and we have to sort it differently for each t. Just look down column 3 and think about sorting without actually moving anything. Remember that in case of ties, you would then have to look at column 1, then column 4, etc. It's a mess, and I don't think you can do it without adding a data structure much larger than what we already have. And the original point of combining Shamir with M-conjugacy was to save memory. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990 From dlitwin@geoworks.com Wed May 1 20:27:22 1996 Return-Path: Received: from quark.geoworks.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA21793; Wed, 1 May 96 20:27:22 EDT Received: from rubik.geoworks.com.geoworks ([198.211.201.34]) by quark.geoworks.com (4.1/SMI-4.0) id AA17163; Wed, 1 May 96 17:27:07 PDT Date: Wed, 1 May 96 17:27:07 PDT From: dlitwin@geoworks.com (David Litwin) Message-Id: <9605020027.AA17163@quark.geoworks.com> To: cube-lovers@ai.mit.edu In-Reply-To: <9604301252.AA02489@mecmdb.me.ic.ac.uk> Subject: Where to get the Rubik's Revenge "The Official Thermodynamics Fan Club of the UK." writes: > p.s. I'm sure this is a common question, but I have many 3x3x3, and one > 5x5x5, can I still get a 4x4x4 anywhere? would anyone consider selling one > to me? The last time I bought one was in 1993 in Tokyo (at Tokyu Hands department store). I'll be visiting again soon and will check to see if they still have any. This is the only place I've been able to find them, outside of those who sell from their private collections. At this point I don't think anyone has any available for sale though. If I find any in Japan I'll certainly buy as many as possible and let the list know. The 5x5x5 is more widely available, try: Peter Beck pbeck@pica.army.mil or Dr. Christoph Bandelow An der Wabeck 37 58456 Witten Germany Good luck, Dave Litwin From din5w@dot.cs.virginia.edu Wed May 1 21:39:44 1996 Return-Path: Received: from virginia.edu (mars.itc.Virginia.EDU) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA24126; Wed, 1 May 96 21:39:44 EDT Received: from archive.cs.virginia.edu by mail.virginia.edu id aa13503; 1 May 96 21:39 EDT Received: from dot.cs.Virginia.EDU (din5w@dot.cs.Virginia.EDU [128.143.67.21]) by archive.cs.Virginia.EDU (8.7.1/8.6.6) with SMTP id VAA03673 for ; Wed, 1 May 1996 21:39:10 -0400 (EDT) Received: by dot.cs.Virginia.EDU (4.1/SMI-2.0) id AA07207; Wed, 1 May 96 21:39:08 EDT Date: Wed, 1 May 1996 21:39:07 -0400 (EDT) From: Dale Newfield X-Sender: din5w@dot.cs.Virginia.EDU Reply-To: DNewfield@virginia.edu To: cube-lovers@ai.mit.edu Subject: building a Rubik's Revenge In-Reply-To: <9605020027.AA17163@quark.geoworks.com> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII I know that I have at least some of the parts from at least one broken Rubik's Revenge lying around somewhere. I would suspect that I am not alone. I was w