From ccw@eql.caltech.edu Fri Nov 1 19:10:26 1991 Return-Path: Received: from EQL.Caltech.Edu by life.ai.mit.edu (4.1/AI-4.10) id AA16260; Fri, 1 Nov 91 19:10:26 EST Date: Fri, 1 Nov 91 15:49:59 PST From: ccw@eql.caltech.edu (Chris Worrell) Message-Id: <911101154959.23403c64@EQL.Caltech.Edu> Subject: What is the smallest cube which has all possible types of pieces? To: cube-lovers@ai.mit.edu Some cube discussion has started in rec.games.misc. I am trying to re-direct it to rec.puzzles, or hopefully cube-lovers. This is a copy of what I posted to rec.games.misc and rec.puzzles. Message follows: ------------------------------------ Newsgroups: rec.games.misc, rec.puzzles Subject: Re: Rubik's Wonderful Madness Followups-to: rec.puzzles johnf@apollo.hp.com (John Francis) writes... > >The 5x5x5 cube is the largest "interesting" cube from a solvers viewpoint. >The corner cubelets of cubes of all sizes can be solved the same way. >Similarly with the edge-centre cubelets of odd-sized cubes, etc., etc. >The 5x5x5 does not actually require any new solving techniques (if you can >solve a 3x3x3 and a 4x4x4 you can solve a 5x5x5), but it is the smallest >cube that contains cubelets of all possible types. Actually the 7x7x7 has a type of piece that the 5x5x5 does not have. This is a "face" piece which is not on a main diagonal of the face, nor on the main horizontal or vertical. These pieces come in 2 flavors, right-handed and left-handed (but I am not sure which should be called which). ---------------------- |A |B |C |D | | | | The 2x2x2 has types A ---------------------- The 3x3x3 has types A, D, K | |E |F |G | | | | The 4x4x4 has types A, B(C), E(I) ---------------------- The 5x5x5 has types A, B(C), D, E(I), G(J), K | |H |I |J | | | | The 6x6x6 has types A, B, C, E, F, H, I ---------------------- The 7x7x7 has types A-K | | | |K | | | | ---------------------- B and C are distinct at size 6+, but the same | | | | | | | | sorts of procedures work on both. ---------------------- Similarly for E & I. | | | | | | | | Similarly for G & J. For odd sizes 7+. ---------------------- Similarly for H & F. These are related | | | | | | | | by mirror imaging. Not by slice renumbering, ---------------------- like the above. Types F & H only start appearing at size 6. There are 24 of each of these pieces, and a type F can not be mixed with a type H. Discussions about the Rubik's cube and related puzzles should probably be directed to rec.puzzles rather than rec.games.misc. There is also a mailing list for theses topics. cube-lovers@ai.mit.edu Send mail to cube-lovers-request@ai.mit.edu to be added. Some sites may also see this as a newsgroup mlist.cube-lovers. But do not post to this group. From dik@cwi.nl Fri Nov 1 20:10:55 1991 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) id AA17885; Fri, 1 Nov 91 20:10:55 EST Received: by charon.cwi.nl with SMTP; Sat, 2 Nov 1991 02:10:52 +0100 Received: by paring.cwi.nl ; Sat, 2 Nov 91 02:10:47 +0100 Date: Sat, 2 Nov 91 02:10:47 +0100 From: dik@cwi.nl Message-Id: <9111020110.AA30522@paring.cwi.nl> To: ccw@eql.caltech.edu, cube-lovers@ai.mit.edu Subject: Re: What is the smallest cube which has all possible types of pieces? > Some cube discussion has started in rec.games.misc. I am trying to > re-direct it to rec.puzzles, or hopefully cube-lovers. I follow up in cube-lovers. > > Actually the 7x7x7 has a type of piece that the 5x5x5 does not have. Actually the 7x7x7 is also the first cube that can not be made. > > (Showing a pattern like: ABCD > EFG > HIJ > K. > Noting that B&C, E&I, G&J, H&F are similar and can be solved by the same > set of procedures.) But, all of E to J can be solved with the same set of procedures %. So although there appear to be 7 essentially different cubelets, actually there are only 5. And the 5x5x5 cube has them all. Solving these involves rotating the three slices they are in originally. So if we rename cubelet types we get: 1: A 2: B&C 3: D 4: E-J 5: K and we find for the different cubes: 2x2x2: Type 1 3x3x3: Type 1, 3 and 5 4x4x4: Type 1, 2 and 4 5x5x5: All types. -- % All of E to J occur 4 times on each face, so for each type there are 24 cubelets. B and C also occur 24 times, procedures working for these two also work for E to J (although I use different procedures both on 4x4x4 and 5x5x5); but there are procedures for E to J that do not work for B to C (these two have more constraints on position). This would be different if the cube was patterned such that all cubelets of type B, C and E to J had a unique position, in that case we would have only four essentially different types. From ronnie@cisco.com Fri Nov 1 21:24:02 1991 Return-Path: Received: from lager.cisco.com by life.ai.mit.edu (4.1/AI-4.10) id AA19529; Fri, 1 Nov 91 21:24:02 EST Received: by lager.cisco.com; Fri, 1 Nov 91 17:36:38 -0800 Date: Fri, 1 Nov 91 17:36:38 -0800 From: Ronnie Kon Message-Id: <9111020136.AA16266@lager.cisco.com> To: ccw@eql.caltech.edu, cube-lovers@ai.mit.edu Subject: Re: What is the smallest cube which has all possible types of pieces? I made essentially the same assertion some months back (about the 5x5x5 being the last "interesting" cube), and someone pointed out that there is a position in even order cubes which has no parallel in odd order cubes-- that where all the corner cubies are correct, but all the edge cubies on the top layer are wrong. The presence of the fixed center cubie makes it clear that the edge cubies are really all wrong. Boy it's great to get cube mail again. Ronnie From tjj@lemma.helsinki.fi Mon Nov 4 12:00:58 1991 Return-Path: Received: from funet.fi by life.ai.mit.edu (4.1/AI-4.10) id AA19455; Mon, 4 Nov 91 12:00:58 EST Received: from lemma.Helsinki.fi by funet.fi with SMTP (PP) id <25881-0@funet.fi>; Mon, 4 Nov 1991 19:00:44 +0200 Received: by lemma.helsinki.fi (5.57/Ultrix3.0-C) id AA02272; Mon, 4 Nov 91 19:00:41 +0200 Date: Mon, 4 Nov 91 19:00:41 +0200 From: tjj@lemma.helsinki.fi (Timo Jokitalo) Message-Id: <9111041700.AA02272@lemma.helsinki.fi> To: cube-lovers@ai.mit.edu Subject: Square One Hi everyone! Well, now I finally had time to try and solve my Square One. After hours and hours of pondering it is now finally done. (For the first time ever - I noticed the leaflet with instructions on how to get it to square one only after I'd done a few rotations.) Now what needs to be done is to polish the 'method' a bit (a lot), and find out if I was just lucky this time... Altogether, it seems to be quite a nice puzzle, although at first I thought that it was _very_ ugly and unpleasant. (But not half as ugly and unpleasant as 'Rubik's Dice'. Perhaps I'm clumsy, but It's awful: whenever I get somewhere with it, I touch it a bit too hard, all the plates fall to the bottom and I throw the thing back to the corner in disgustment. Opinions?) But: does anyone have the number of configurations for it? I tried to count them, and got something like 2.8 E 13, but very probably there are a few factors of two or something missing. It's also a bit tricky to decide on when two configurations are different. (I mean, should one count as different a configuration reached by rotating, say, the top layer by 30 degrees? Sometimes, yes, but sometimes it seems a bit funny to do so.) Timo (tjj@rolf.helsinki.fi) From SCHMIDTG@astro.pc.ab.com Wed Nov 6 14:09:10 1991 Return-Path: Received: from abvax.icd.ab.com by life.ai.mit.edu (4.1/AI-4.10) id AA04452; Wed, 6 Nov 91 14:09:10 EST Received: from odin.icd.ab.com by abvax.icd.ab.com (5.64/1.39) id AA01449; Wed, 6 Nov 91 14:09:04 -0500 Received: from astro.pc.ab.com by odin.icd.ab.com (4.1/CIS-2.7) id AA15688; Wed, 6 Nov 91 14:09:02 EST Message-Id: <9111061909.AA15688@odin.icd.ab.com> Date: 6 Nov 91 14:04:00 EST From: "24305, SCHMIDT, GREG" To: "cube-lovers@ai.mit.edu" Please add me to the mailing list Thanks. -- Greg Schmidt --> schmidtg@iccgcc.decnet.ab.com <-- From diamond@jit081.enet.dec.com Thu Nov 7 06:49:22 1991 Return-Path: Received: from enet-gw.pa.dec.com by life.ai.mit.edu (4.1/AI-4.10) id AA05762; Thu, 7 Nov 91 06:49:22 EST Received: by enet-gw.pa.dec.com; id AA15547; Thu, 7 Nov 91 03:49:20 -0800 Message-Id: <9111071149.AA15547@enet-gw.pa.dec.com> Received: from jit081.enet; by decwrl.enet; Thu, 7 Nov 91 03:49:21 PST Date: Thu, 7 Nov 91 03:49:21 PST From: 07-Nov-1991 2050 To: cube-lovers@ai.mit.edu Apparently-To: cube-lovers@ai.mit.edu Subject: subscribe Please subscribe diamond@jit081.enet.dec.com to the cube-lovers mailing list. From hoey@aic.nrl.navy.mil Mon Nov 11 17:45:47 1991 Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) id AA05032; Mon, 11 Nov 91 17:45:47 EST Received: from sun1.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA12227; Mon, 11 Nov 91 17:45:36 EST Return-Path: Received: by sun1.aic.nrl.navy.mil; Mon, 11 Nov 91 17:45:36 EST Date: Mon, 11 Nov 91 17:45:36 EST From: hoey@aic.nrl.navy.mil Message-Id: <9111112245.AA03752@sun1.aic.nrl.navy.mil> To: baggett@mssun7.msi.cornell.edu (Jeffrey Baggett) Cc: Cube-Lovers@life.ai.mit.edu Subject: Rubik's Cube question Organization: Naval Research Laboratory, Washington, DC Jeff Baggett (baggett@mssun7.msi.cornell.edu) asks on the sci.math newsgroup: > 1. I am seeking a description of the group of symmetries associated > with Rubiks cube. I have some ideas but they aren't particularly > elegant. Can someone suggest a paper? Jeff, I have looked into this somewhat. As far as I know, the symmetries of the 3^3 cube are just the symmetries of the cube, but in larger sizes we can do better. The best way of looking at this is to imagine that there is a (N-2)^3 cube sitting inside your N^3 cube, and smaller cubes within, and you are trying to solve them all together. Suppose we address each cubelet of the N^3 cube using cartesian coordinates (x,y,z), where (0,0,0) is the center of the cube (for N odd) and no cubelets have any coordinate zero if N is even. The maximum absolute value of the coordinates is [N/2]. Then for 1<=I<=[N/2], there is a symmetry F[I]:(x,y,z)->(f(x),f(y),f(z)), where f(I)=-I, f(-I)=I, and f(x)=x otherwise. Then for 1<=I(e(x),e(y),e(z)), where e(I)=J, e(J)=I, e(-I)=-J, e(-J)=-I, and e(x)=x otherwise. These are symmetries of the cube group, and they map elementary moves to elementary moves (provided we take an elementary move to be a rotation of the slab of N^2 cubelets that have a particular nonzero value of a particular coordinate). Symmetries of the cube group that preserve elementary moves are useful in the study of local minima in the cube group. It turns out that if you only want to consider the outside of the cube (ignoring the (N-2)^3 cube inside) all of these symmetries are still present except F[[N/2]] and E[I,[N/2]]. I mentioned these symmetries in a note to the Cube-Lovers mailing list in 1983. I called E[I,J] evisceration, F[1] inflection, and F[[N/2]] exflection in that note (where I was dealing explicitly with only the 4^3). The discussion of the relation to local minima took place in 1980. Let me know if you'd like a copy of these messages. I ran into these symmetries earlier, though. They are symmetries of the N^3 tic-tac-toe board! I would not be surprised if they arise in some other connection in mathematics, but I have never run into them. They generalize into larger dimensions, as well. I've also taken the liberty of Cc'ing the Cube-Lovers list with this note. If you'd like to be on that list, you may ask of "Cube-Lovers-Request@AI.AI.MIT.Edu". Dan Hoey Hoey@AIC.NRL.Navy.Mil From sjfc!ggww@cci632.cci.com Tue Nov 12 07:16:07 1991 Return-Path: Received: from uu.psi.com by life.ai.mit.edu (4.1/AI-4.10) id AA21658; Tue, 12 Nov 91 07:16:07 EST Received: from sjfc.UUCP by uu.psi.com (5.65b/4.1.110791-PSI/PSINet) id AA05547; Tue, 12 Nov 91 07:11:47 -0500 Received: by cci632.cci.com (5.54/5.17) id AA19314; Mon, 11 Nov 91 10:51:18 EST Received: by sjfc.UUCP (5.51/4.7) id AA08293; Mon, 11 Nov 91 09:18:57 EST Date: Mon, 11 Nov 91 09:18:57 EST From: sjfc!ggww@cci632.cci.com (Gerry Wildenberg) Message-Id: <9111111418.AA08293@sjfc.UUCP> To: cube-lovers@ai.mit.edu Subject: mailing list Please put me on the mailing list. If there is a FAQ for this group, lease mail me a copy. Gerry Wildenberg ggww@sjfc.uucp St. John Fisher College sjfc!ggww@cci.com Rochester, NY 14618 ...!uunet!uupsi!cci632!sjfc!ggww From pbeck@pica.army.mil Fri Nov 15 13:00:10 1991 Return-Path: Received: from FSAC1.PICA.ARMY.MIL by life.ai.mit.edu (4.1/AI-4.10) id AA16064; Fri, 15 Nov 91 13:00:10 EST Date: Fri, 15 Nov 91 10:36:45 EST From: Peter Beck (BATDD) To: cube-lovers@ai.mit.edu Subject: puzzle shows Message-Id: <9111151037.aa18151@FSAC1.PICA.ARMY.MIL> Mark Your Calendars and take advantage of the airfare wars CUBING/PUZZLING EVENTS rev 11/15/91, transcribe by p beck ............................................................... <--> The 11th DUTCH CUBE DAY <--> ............................................................... WHEN ---- Saturday, 14 Dec 1991 WHERE ---- Office building of ABT, Arnhemsestraatweg 358, Velp, THE NETHERLANDS TIME ---- 10:00 AM ENTRANCE FEE: Dfl 5.00; includes lunch and drinks INVITITATIONS: cut-off date 11/20/91 Anton Hanegraaf, Heemskerkstraat 9, NL-6662 Al EST (08819 - 72402), or FAX -- ABT Velp, 085 - 635326 AGENDA: .. LECTURES - Lee Sallows: Serila Sided Isogons - Oskar van Deventer: A Mirror Problem - Koos Verhoeff: Design of Spatial Strucutres - Willem van der POel: Survey of Mechanical Puzzles .. EXHIBITIONS - Wim Zwaan: Puzzles in Wood - Theo Bense: Dodecahedral Compositions Popke Bakker/Koos Verhoeff: Sculptures in Wood ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ............................................................... <--> 12th International puzzle collector's party and fair <--> ............................................................... WHEN ---- 7/31/92 WHERE ---- TBD target is $70 per night INVITATIONS *** Admission by invitation only!!! Contact Mr. Nob Yoshigahara, 4-10-1-408 Iidabashi, Tokyo 102 Japan AGENDA: 7/31 welcoming party in the evening 8/1 collectors and dealers details will be available in early feb 92 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ From pbeck@pica.army.mil Fri Nov 15 14:59:13 1991 Return-Path: Received: from FSAC1.PICA.ARMY.MIL by life.ai.mit.edu (4.1/AI-4.10) id AA19757; Fri, 15 Nov 91 14:59:13 EST Received: by FSAC1.PICA.ARMY.MIL id aa20060; 15 Nov 91 10:46 EST Date: Fri, 15 Nov 91 10:39:21 EST From: Peter Beck (BATDD) To: cube-lovers@ai.mit.edu Subject: book review Message-Id: <9111151039.aa18635@FSAC1.PICA.ARMY.MIL> SHAPING SPACE; A POLYHEDRAL APPROACH M Senechal, G Fleck eds. 284 pp, Birkhauser, 1988 $49.95, ISBN 0-8176-3351-0 REVIEW BY: Peter Beck; Rubik's Cube Collector Other reviews: SCITECH BOOK NEWS, V12, APR 88, P3 AMERICAN SCIENTIST, V77, JAN 89, P72 Shaping Space, the book, was inspired by the Shaping Space Conference held at Smith College in April 1984. The content of the book addresses itself to an interdisciplinary readership and should be considered as a cornerstone book in guiding any level of reader on an exploration of the Polyhedron Kingdom. It encourages readers to experience polyhedra directly, by including recipes for construction as well as numerous illustrations (188 line and 174 halftone illustrations). The book is organized in five parts with parts 1,2 &5 of greater interest to the beginning explorer. Part 1 is an introduction to polyhedra which includes a chapter on making polyhedra ,ie, Chapter 2 "Five Recipes for Making Polyhedra." Part 2 is an interdisciplinary overview of polyhedra which includes a chapter on "Milestones in the History of Polyhedra" (chapter 4), a chapter on "Polyhedra and Crystal Structures" (chapter 5),and a chapter on "Spatial Perception and Creativity" (chapter 7), and concludes with a chapter on "Why Study Polyhedra?" (chapter 8). Part 3 is about the roles of polyhedra in science. Part 4 is the theory of polyhedra. Part 5 is a discussion on incorporating the teaching of polyhedra in the curriculum. Included in part 5 is a resource guide that is organized in the following categories: A. Architecture B. Art C. Geometry D. Instructional and Recreational Materials E. Science F. Symmetry In addition to the resource guide each chapter has its own list of references. The book has a comprehensive index of 10 pages and it also has a list of the conference contributors addresses. From pbeck@pica.army.mil Tue Dec 3 11:52:11 1991 Return-Path: Received: from FSAC1.PICA.ARMY.MIL by life.ai.mit.edu (4.1/AI-4.10) id AA10810; Tue, 3 Dec 91 11:52:11 EST Received: by FSAC1.PICA.ARMY.MIL id aa11374; 3 Dec 91 11:33 EST Date: Tue, 3 Dec 91 11:26:50 EST From: Peter Beck (BATDD) To: cube-lovers@life.ai.mit.edu Cc: pbeck@pica.army.mil Subject: rubik's tangle, etc Message-Id: <9112031126.aa10408@FSAC1.PICA.ARMY.MIL> looking for nyc source of rubik's tangle, xv, dice, triamid any suggestions?? thanks in advance From @bullet.ecf.toronto.edu:tee@ecf.toronto.edu Tue Dec 10 18:03:38 1991 Return-Path: <@bullet.ecf.toronto.edu:tee@ecf.toronto.edu> Received: from bullet.ecf.toronto.edu by life.ai.mit.edu (4.1/AI-4.10) id AA20590; Tue, 10 Dec 91 18:03:38 EST Received: by bullet.ecf.toronto.edu id <8345>; Tue, 10 Dec 1991 18:03:28 -0500 From: TEE LUNS To: Cube-Lovers@ai.mit.edu Subject: 7x7x7 Message-Id: <91Dec10.180328est.8345@bullet.ecf.toronto.edu> Date: Tue, 10 Dec 1991 18:03:14 -0500 I was reading through the archives the other night (just signed onto the mailing list) and one of the last posts in cube-mail-7 triggered something in me head. The suggestion was to use a fresnel saw to cut all the cubelets out of a single chunk of material, with the cut such that the pieces all interlock. The interlocking however doesn't need to be quite as intricate as the diagram given - why not a simple dovetail? That's actually to some extent what the 3x3x3 cube is - the center cubelets dovetail into the edge cubelets, and the edges dovetail into the corners. It just happens that there's enough reduncancy that the outside half of the dovetail joints can be disposed of, and the edges made straight while still allowing the cube to stay in one piece. If we have a complete (both sides) locked dovetail, we can actually assemble almost all of the cube out of the cubelets. Since the cubelets will always require an entry point for their dovetail grooves, there will be a few cubelets that have to be attached differently. The simplest solution I can think of is to have the dovetail/cublet pair seperate, with a countersink on the dovetail, and holes through the other cubelets so that we can screw the dovetails (which are already in their grooves) onto the last couple of cubelets. One drawback with this approach is that the boundaries between layers of cubelets will be quite jagged. If the dovetails go right to the surface, one has to be *VERY* careful when turning the cube to make sure that all layers are lined up in the axes that aren't being turned (this problem plagues the magic truncated octahedron I have - pieces pop out all the time). The solution is to make the dovetail taper off at its ends so that if it's out of line with the groove its going into, it can still correct itself. This will lead to holes at the surface though, so the cube won't be too pretty. A novelty with this approach though is that no centre is required. We could build a hollow 3x3x3 cube with face centres hollow, and see right through the cube. This should be possible with larger odd-sized cubes too, but there comes a point (probably 7x7x7 again) where mechanical play would let middle layers shear enough to pop out cubelets. But, if we had the smaller odd-sized cubes trapped inside, not only would they help hold the outer layers together, if we made the cubelets mostly transparent, we'd be able to see what we've had to imagine in the past. Now that'd be one heck of a puzzle. From pbeck@pica.army.mil Wed Dec 11 09:20:29 1991 Return-Path: Received: from FSAC1.PICA.ARMY.MIL by life.ai.mit.edu (4.1/AI-4.10) id AA08205; Wed, 11 Dec 91 09:20:29 EST Date: Wed, 11 Dec 91 9:09:07 EST From: Peter Beck (BATDD) To: cube-lovers@life.ai.mit.edu Subject: collectors directory Message-Id: <9112110909.aa13900@FSAC1.PICA.ARMY.MIL> The world of MECHANICAL PUZZLE collecting is getting organized. Jerry Slocum is compiling a directory of collectors, also designers, buyers, sellers. If you want to be included there is a form to fill out (hardcopy). The form has to be to Jerry by 1/15/92 to be included. This is a non-commercial venture and I am unaware of any extended plans. To get a form contact Jerry: JERRY SLOCUM 257 SOUTH PALM DRIVE BEVERLY HILLS, CA 90212 USA PHONE & FAX 310/273-2270 I assume form can be FAXed. I have copies so if need be I can mail you one. PS: There is classification for computer puzzles but not one for computer solutions/helper programs, eg, cube simulations & non physically realizable cubes, like 10x10x10. From ronnie@cisco.com Wed Dec 11 18:04:35 1991 Return-Path: Received: from wolf.cisco.com by life.ai.mit.edu (4.1/AI-4.10) id AA06760; Wed, 11 Dec 91 18:04:35 EST Received: from lager.cisco.com by wolf.cisco.com with TCP; Wed, 11 Dec 91 14:56:01 -0800 Message-Id: <9112112256.AA20600@wolf.cisco.com> From: ronnie@cisco.com To: Cube-Lovers@life.ai.mit.edu Subject: A Sam Loyd Rubik puzzle unearthed!!! Date: Wed, 11 Dec 91 14:57:25 PST Sender: ronnie@cisco.com An original Sam Loyd puzzle involving the Rubik's cube has come into my hands; somewhat surprising, in that Sam Loyd died in the early years of this century, but no more so than the truly astounding circumstances by which the puzzle came to me, which I would detail if I believe that anyone were interested. However, as this list consists only of people interesting in things Cubic, I will limit this posting to the puzzle itself. Crooked Gambling in Puzzleland by Sam Loyd Tommy Riddles has challenged King Puzzlepate to a game of dice, using Rubik's Cubes as dice. However, Tommy is planning to cheat by changing the ordinary Rubik's Cube into tops [ tops are dice which are misspotted, by having only three different numbers on them, each appearing opposite to itself, such that it is indetectable without turning the die around -ed ] spotted 1-2-3, which he is able to make from a standard cube in 14 moves. King Puzzlepate, however, has learned from the General of his plans, and has figured out to convert Tommy's tops into 2-3-4 tops, which are favorable to His Majesty, in only 3 moves. Can you duplicate both these feats? [ Note that Loyd appears to consider a move as moving any of the nine slices any number of degrees. Thus the move we would designate as L2R2 and count as four, Loyd would count as one move of the center slice by 180 degrees. ] From hoey@aic.nrl.navy.mil Thu Dec 12 10:29:25 1991 Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) id AA05785; Thu, 12 Dec 91 10:29:25 EST Received: from sun13.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA28868; Thu, 12 Dec 91 10:29:05 EST Return-Path: Received: by sun13.aic.nrl.navy.mil; Thu, 12 Dec 91 10:29:04 EST Date: Thu, 12 Dec 91 10:29:04 EST From: hoey@aic.nrl.navy.mil Message-Id: <9112121529.AA02722@sun13.aic.nrl.navy.mil> To: ronnie@cisco.com (Ronnie Kon) Subject: Rubik's cube dice tops Cc: Cube-Lovers@ai.mit.edu ronnie@cisco.com (Ronnie Kon) writes: > An original Sam Loyd puzzle involving the Rubik's cube has come into > my hands; somewhat surprising, in that Sam Loyd died in the early > years of this century, but no more so than the truly astounding > circumstances by which the puzzle came to me, which I would detail > if I believe that anyone were interested. Hmm. A likely story. We are challenged to find ``tops'', > ... dice which are misspotted, by having only three different > numbers on them, each appearing opposite to itself ... spotted > 1-2-3, ... from a standard cube in 14 moves. Where he counts a half turn, a slice, and and a half-slices as one move each. I have found how this can be done in 13 such moves. I have some suspicion that it can be done in 12; I'll let you know. We are then challenged to convert this > ... into 2-3-4 tops ... in only 3 moves. The second part can be solved by any person who achieves mastery of the cube. Dan Hoey Hoey@AIC.NRL.Navy.Mil From hoey@aic.nrl.navy.mil Fri Dec 13 14:50:15 1991 Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) id AA17846; Fri, 13 Dec 91 14:50:15 EST Received: from sun13.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA01668; Fri, 13 Dec 91 14:50:04 EST Return-Path: Received: by sun13.aic.nrl.navy.mil; Fri, 13 Dec 91 14:50:03 EST Date: Fri, 13 Dec 91 14:50:03 EST From: hoey@aic.nrl.navy.mil Message-Id: <9112131950.AA06512@sun13.aic.nrl.navy.mil> To: TEE LUNS Cc: Cube-Lovers@life.ai.mit.edu Subject: Big groovy cubes, revisited Tee Luns writes: > ... one of the last posts in cube-mail-7 triggered something in me > head. The suggestion was to use a fresnel saw to cut all the > cubelets out of a single chunk of material.... Well, I'm glad that my silly ideas triggered something. Sometimes I wonder if they are as amusing to read as they were to write. > ... why not a simple dovetail? Certainly a dovetail would do it. I guess when I got to sharpening the fresnel saw I didn't know when to quit. > ... have the dovetail/cubelet pair separate, ... screw the dovetails > (which are already in their grooves) onto the last couple of > cubelets. Surprisingly enough, this is just how Rubik's Revenge is put together. One of the center cubelets (perhaps always on the blue side) has a screw that joins the outside of the cubelet to its dovetail. You can usually find locate it by the dimple in the colored sticker. > If the dovetails go right to the surface, one has to be *VERY* > careful.... The solution is to make the dovetail taper off at its > ends.... This will lead to holes at the surface though, so the cube > won't be too pretty. In the 7^3 and larger, they have to go through the surface, and even if they were squared-off dovetails they wouldn't match the color of the adjacent square except in the solved position. Unless of course we make the outer layers thicker, as Dale Newfield mentioned when we were discussing this back in May. > A novelty with this approach though is that no centre is > required. We could build a hollow 3x3x3 cube with face centres > hollow, and see right through the cube.... > But, if we had the smaller odd-sized cubes trapped inside, not > only would they help hold the outer layers together, if we made the > cubelets mostly transparent, we'd be able to see what we've had to > imagine in the past. Now that'd be one heck of a puzzle. Wow, I want one! But I don't think the material really needs to be transparent, as long as the face center pieces are hollow. It would help let light in, though. Dan Hoey Hoey@AIC.NRL.Navy.Mil From ACW@yukon.scrc.symbolics.com Fri Dec 13 18:29:48 1991 Return-Path: Received: from YUKON.SCRC.Symbolics.COM by life.ai.mit.edu (4.1/AI-4.10) id AA22741; Fri, 13 Dec 91 18:29:48 EST Received: from PALLANDO.SCRC.Symbolics.COM by YUKON.SCRC.Symbolics.COM via INTERNET with SMTP id 754668; 13 Dec 1991 18:17:15-0500 Date: Fri, 13 Dec 1991 18:16-0500 From: Allan C. Wechsler Subject: Big groovy cubes, revisited To: hoey@aic.nrl.navy.mil, tee@ecf.toronto.edu Cc: Cube-Lovers@life.ai.mit.edu In-Reply-To: <9112131950.AA06512@sun13.aic.nrl.navy.mil> Message-Id: <19911213231647.9.ACW@PALLANDO.SCRC.Symbolics.COM> I want to know whether it is feasible, with modern electronics and electro-mechanicals, to make a 3x3x3 cube that solves itself at the touch of a button. How much would a prototype cost? $10,000? $100,000? From hoey@aic.nrl.navy.mil Tue Dec 17 16:38:10 1991 Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) id AA18437; Tue, 17 Dec 91 16:38:10 EST Received: from sun13.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA12139; Tue, 17 Dec 91 16:18:17 EST Return-Path: Received: by sun13.aic.nrl.navy.mil; Tue, 17 Dec 91 16:18:16 EST Date: Tue, 17 Dec 91 16:18:16 EST From: hoey@aic.nrl.navy.mil Message-Id: <9112172118.AA14791@sun13.aic.nrl.navy.mil> To: Cube-Lovers@life.ai.mit.edu, ronnie@cisco.com (Ronnie Kon) Subject: Re: Rubik's cube dice tops (Spoiler) Last week ronnie@cisco.com (Ronnie Kon) challenged us to find Rubik's cube patterns with dice pips for 1, 2, and 3 on the three pairs of opposite sides. He claimed it could be done in fourteen HST, where one HST is a turn of a face or center slice by 90 or 180 degrees. I responded that it could be done in thirteen HST. Here is how. I will use this opportunity to practice the enhanced Varga Rubiksong I described (unfortunately with many typos) on 22 Feb 90. The (only such) pattern is the composition of Four-Spot and Laughter. We have long known the processes ris-fos tis-fos, or (RL)^2 FB' (TD)^2 FB', for Four-Spot and fon-ron fon-ron fon-ron, or (FBRL)^3, for Laughter. When we compose them, the F and B moves combine and cancel to produce ris-fos tis-fi ron-fon ron-fon ron, or (RL)^2 FB' (TD)^2 F^2 (RLFB)^2 RL. This 14 HST process is presumably something like what Ronnie had in mind. But since this pattern commutes with ris, or (RL)^2, we can get the same pattern with the conjugate process fos tis-fi ron-fon ron-fon ran, or FB' (TD)^2 F^2 (RLFB)^2 R'L'. This uses only 13 HST. This is also the shortest process I know of in the normal metric: 18 QT, which is not so bad for the combination of two 12 QT processes. I suggested that perhaps 12 HST would be sufficient, but I have not found such an improvement. Nor do I know whether 13 HST is the best that can be done: it seems that proving 13 HST optimal would require examining about 160 million positions, almost as many as the 200 million it would take to prove 18 QT optimal. Dan Hoey Hoey@AIC.NRL.Navy.Mil From raymond@cps.msu.edu Sun Jan 5 12:54:44 1992 Return-Path: Received: from galaxy.cps.msu.edu by life.ai.mit.edu (4.1/AI-4.10) id AA00849; Sun, 5 Jan 92 12:54:44 EST Received: by galaxy.cps.msu.edu (4.1/rpj-5.0); id AA12647; Sun, 5 Jan 92 12:54:43 EST Date: Sun, 5 Jan 92 12:54:43 EST From: raymond@cps.msu.edu (Carl J Raymond) Message-Id: <9201051754.AA12647@galaxy.cps.msu.edu> To: cube-lovers@life.ai.mit.edu Subject: Subscribe I would like to join the cube lover's mailing list. My email address is raymond@cpsin3.cps.msu.edu. Also, I am trying to find an email address for Peter Beck. Thanks, Carl Raymond From cosell@bbn.com Tue Jan 7 09:49:04 1992 Return-Path: Received: from WILMA.BBN.COM by life.ai.mit.edu (4.1/AI-4.10) id AA25601; Tue, 7 Jan 92 09:49:04 EST Message-Id: <9201071449.AA25601@life.ai.mit.edu> Date: Tue, 7 Jan 92 7:23:29 EST From: Bernie Cosell To: cube-lovers@life.ai.mit.edu Subject: Hungarian Rings solution? Does anyone have an algorithm for solving the "Hungarian Rings" they'd be willing to share. I found one in a drawer that had been long misplaced, and I've been fiddling with it some. It seems easy enough to find lots of 'commutators' for the thing, but all the ones I've run into have the annoying property that they produce symmetric perumtations [given a 180 degree rotation of the puzzle]. But of course, my puzzle is no where near symmetrically messed up. Any advice, hints, full-blown algorithm, etc, would be appreciated... Thanks! /Bernie\ ps, For those that don't remember it, the "Hungarian Rings" is a puzzle with beads arranged in two intersecting circles: * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * [Imagine these both round...:-)] and you can slide the beads around either cicle. The beads come in four colors andthe object is to get the colors all sorted out. /b\ From dik@cwi.nl Tue Jan 7 10:14:17 1992 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) id AA26150; Tue, 7 Jan 92 10:14:17 EST Received: by charon.cwi.nl with SMTP; Tue, 7 Jan 1992 16:14:05 +0100 Received: by boring.cwi.nl ; Tue, 7 Jan 1992 16:14:01 +0100 Date: Tue, 7 Jan 1992 16:14:01 +0100 From: Dik.Winter@cwi.nl Message-Id: <9201071514.AA05644@boring.cwi.nl> To: cosell@bbn.com, cube-lovers@life.ai.mit.edu Subject: Re: Hungarian Rings solution? You don't nood commutators for it, cycles are sufficient (because there are so many similar colored beads). If I remember right one useful move is: turn right ring clockwise two beads, turn left clockwise two beads, turn right anti-clockwise two beads, turn left anti-clockwise two beads. Using them properly will solve the rings. dik -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland dik@cwi.nl From johnf@apollo.com Tue Jan 7 14:20:49 1992 Return-Path: Received: from amway.ch.apollo.hp.com by life.ai.mit.edu (4.1/AI-4.10) id AA03714; Tue, 7 Jan 92 14:20:49 EST Received: from xuucp.ch.apollo.hp.com by amway.ch.apollo.hp.com id Tue, 7 Jan 92 13:11:49 EST Received: by xuucp.ch.apollo.hp.com id ; Tue, 7 Jan 92 13:03:11 EST Message-Id: <9201071803.AA19854@xuucp.ch.apollo.hp.com> Received: by daphne.ch.apollo.hp.com id AA02034; Tue, 7 Jan 92 13:02:30 EST From: johnf@apollo.com Date: Tue, 7 Jan 92 11:45:34 EST Subject: Square One To: cube-lovers@life.ai.mit.edu I got given one of these things for Christmas (well, actually I gave it to myself). I was wondering if anyone has any good basic operators that they would like to share. I would imagine that the puzzle must be less complex than a true cube, but the restricted set of moves make solving it more complicated than you might think! [I currently have six corners correct, but I still have two (diagonally opposite) corners interchanged. The cube-solving technique that I used for a real cube doesn't work here - I need something different]. From cosell@bbn.com Tue Jan 7 15:48:19 1992 Return-Path: Received: from WILMA.BBN.COM by life.ai.mit.edu (4.1/AI-4.10) id AA06487; Tue, 7 Jan 92 15:48:19 EST Message-Id: <9201072048.AA06487@life.ai.mit.edu> Date: Tue, 7 Jan 92 15:02:18 EST From: Bernie Cosell To: cube-lovers@life.ai.mit.edu Subject: Re: Hungarian Rings solution? In rsponse to my request for info about the Hungarian Rings, Dik.Winter@cwi.nl writes: } You don't nood commutators for it, cycles are sufficient (because there Dik.Winter@cwi.nl writes: } You don't nood commutators for it, cycles are sufficient (because there } are so many similar colored beads).... My apologies --- I meant to say "cycles" when I said I had found lots of them... And I hate to seem dense, but but I'm still stuck... } ... If I remember right one useful move } is: turn right ring clockwise two beads, turn left clockwise two beads, } turn right anti-clockwise two beads, turn left anti-clockwise two beads. } Using them properly will solve the rings. The 'properly' is the part I'm finding hard. There seem to be LOTS of cycles, but even with that big choice I can't see, quite, how to solve the thing. As far as I can tell, basically ANY set of ring-turns that has a total movement of zero seems to define a pretty small cycle. For example, the sequence LnA RnA LnC RnC, for n not a multiple of 5[*], does a three-bead cycle: if you look at the upper intersection: A C Intersection ---> C ======> B B A Where 'A' and 'B' are each n beads away from the intersection [and by changing theorder of L/R you reverse the cycle, and by interchanging A and C you move the cycle to the other side of the intersection. BUT: the problem is that this isn't really a 3-cycle, but rahter _two_ 3-cycles: you also make a central-symmetric move of the beads at the bottom intersection. [*] since five is the distance between the intersections, if the rotate is a muiltiple of 5 the intersections interact, things get a little different: it makes a *two* cycle! In the diagram above [with A five away from C], the move just _swaps_ A & C [and the A' and C' at the lower intersection, too, of course]. Given that my rings are totally non-symmetrically messed up, I can't figure out a plan for making forward progress. I can do lots of diffent cycles, but I can't manage to get the rings set up so that the cycle at both intersections is useful: if I try to fix something at the top intersection I invariably mess up something at the bottom one. Thanks again for you patience with my rantings. I feel like I'm overlooking something simple [since this wasn't supposed to be all that hard a puzzle], but I don't see what it is ... /Bernie\ From dik@cwi.nl Tue Jan 7 16:13:50 1992 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) id AA07462; Tue, 7 Jan 92 16:13:50 EST Received: by charon.cwi.nl with SMTP; Tue, 7 Jan 1992 22:13:46 +0100 Received: by boring.cwi.nl ; Tue, 7 Jan 1992 22:13:43 +0100 Date: Tue, 7 Jan 1992 22:13:43 +0100 From: Dik.Winter@cwi.nl Message-Id: <9201072113.AA06247@boring.cwi.nl> To: cosell@bbn.com, cube-lovers@life.ai.mit.edu Subject: Re: Hungarian Rings solution? > Dik.Winter@cwi.nl writes: > } You don't nood commutators for it, cycles are sufficient (because there > } are so many similar colored beads).... I have already been chastised that what I described are commutators. Of course they are. Not only is my thinking bad late at night, but apparently my spelling is atrocious :-). > As far as I can tell, basically ANY set of ring-turns that has a total > movement of zero seems to define a pretty small cycle. For example, > the sequence LnA RnA LnC RnC, for n not a multiple of 5[*], does a > three-bead cycle: if you look at the upper intersection: > A C > Intersection ---> C ======> B > B A > Where 'A' and 'B' are each n beads away from the intersection [and by > changing theorder of L/R you reverse the cycle, and by interchanging A > and C you move the cycle to the other side of the intersection. > BUT: the problem is that this isn't really a 3-cycle, but rahter _two_ > 3-cycles: you also make a central-symmetric move of the beads at the > bottom intersection. True. But if you prefix the move by a (series of moves) that makes the upper three of an identical color (and postfix by its inverse), you will not see the difference between a true cycle. At least that is how I always did the final part. (Correctly coloring the two lobes is in fact easy; you better start with that.) From Hoffman.El_Segundo@xerox.com Wed Jan 8 12:07:08 1992 Return-Path: Received: from alpha.xerox.com by life.ai.mit.edu (4.1/AI-4.10) id AA06419; Wed, 8 Jan 92 12:07:08 EST Received: from AE_Mail_Service_6.ES_AE.Xerox.xns by alpha.xerox.com via XNS id <12287>; Wed, 8 Jan 1992 09:06:44 PST X-Ns-Transport-Id: 0000AA00A9AD94E12D0C Date: Wed, 8 Jan 1992 09:06:16 PST From: Hoffman.El_Segundo@xerox.com Subject: Re: Square One In-Reply-To: "johnf%apollo:com's message of 7 Jan 92 08:45:34 PST (Tuesday)" To: johnf@apollo.com Cc: cube-lovers@life.ai.mit.edu Message-Id: <" 8-Jan-92 9:06:16 PST".*.Hoffman.El_Segundo@Xerox.com> I, too, gave myself Square One for Christmas, and I, too, would love to exchange some useful moves. Here are three that I use. I need some more! -- Rodney Hoffman Hoffman.El_Segundo@Xerox.com or rodney@oxy.edu ------------------------------------------------------ Conventions used in these descriptions: * These moves start and end in a cube shape. I always hold the logo to my left, with the two faces which can rotate in front and back. That means the plane of the 180-degree twist is perpendicular to my face, angling from upper right to lower left. The "front" face is the one I'm looking directly at. * "the smallest increment" as in "Turn the front face cw the smallest increment". This means the smallest amount that permits the big 180-degree twist that must follow. Note that the angle of turn is not always the same! Sometimes "the smallest increment" turn is truly the smallest possible increment, that is, the width of an edge piece. At other times, it may be the width of a corner piece (much larger), or even two or three piece's widths combined. * "to match" as in "Turn the back face to match". This means the front and back faces remain aligned with one another. * "Now do the 180-degree twist." I move the right half 180 degrees, holding the left half fixed. The logo stays fixed in position and orientation, never moving. * To help in describing the effects of these moves, I will refer to the pieces by number, as follows. Here I have numbered the pieces clockwise from the upper left corner piece on the front face. I have numbered the back face similarly, ** as if looking straight through to it **, that is, piece 9 is directly beneath piece 1, piece 10 is directly beneath piece 2, etc.: Front Face Back Face 1 2 3 9 10 11 8 4 16 12 7 6 5 15 14 13 ------------------------------------------------------ (1) Swaps all 8 corner pieces diagonally directly across in pairs, staying on the same faces (front and back). In my numbering scheme, this move swaps 1 with 5, 3 with 7, 9 with 13, and 11 with 15. (a) Turn the front face cw the smallest increment. Turn the back face to match. Now do the 180-degree twist. (b) Turn the front face ccw the smallest increment. Turn the back face to match. Now do the 180-degree twist. (c) Repeat the (a)(b) combination three times. Note: This entire move, repeated twice, is, of course, an identity. ------------------------------------------------------ (2) Swaps all 8 edge pieces directly across in pairs, staying on the same faces (front and back). In my numbering scheme, this move swaps 2 with 6, 4 with 8, 10 with 14, and 12 with 16. (a) Turn the front face cw the smallest increment. Turn the back face to match. Now do the 180-degree twist. (b) Repeat (a) six times. (c) Turn the front and back faces 180 degrees. Note: This entire move, repeated twice, is, of course, an identity. ------------------------------------------------------ (3) Although this move itself is simple to describe, its effect is not. It moves four pieces (two large and two small) from the front to the back, and vice-versa. It's easiest to just give a map of the changes: BEFORE: Front Face Back Face 1 2 3 9 10 11 8 4 16 12 7 6 5 15 14 13 AFTER: Front Face Back Face 11 6 13 9 10 3 8 12 16 2 7 14 1 15 4 5 (Because the back face is never turned in this move, its pieces 9, 10, 15, and 16 always stay fixed. They are on the immobile half of the back face, the half not moved during the 180-degree twists.) (a) Turn the front face cw the smallest increment. Do not turn the back face at all. Now do the 180-degree twist. (b) Turn the front face ccw the smallest increment. Do not turn the back face at all. Now do the 180-degree twist. (c) Repeat the (a)(b) combination three times. Note: This entire move, repeated five times, is an identity. ------------------------------------------------------ From GOFFJEFFREYM@bvc.edu Wed Jan 8 16:51:55 1992 Return-Path: Received: from snoopy.bvc.edu ([147.92.2.2]) by life.ai.mit.edu (4.1/AI-4.10) id AA15544; Wed, 8 Jan 92 16:51:55 EST Received: from bvc.edu by bvc.edu (PMDF #12446) id <01GF2UNCTVTC94DUAR@bvc.edu>; Wed, 8 Jan 1992 15:51 CST Date: Wed, 8 Jan 1992 15:51 CST From: The Phantom To: cube-lovers@life.ai.mit.edu Message-Id: <01GF2UNCTVTC94DUAR@bvc.edu> X-Vms-To: IN%"cube-lovers@life.ai.mit.edu" Another miscellaneous thought on the dovetail topic. The way I understand it is that each piece is dovetailed into the surrounding pieces. I.E. on the 3x3x3 the face-centers are dovetailed into the edges which are dovetailed into the corners. Now, the maximum radius of the dovetailing circle permits this all the way out to 5x5x5, but at 6x6x6, a piece hangs outside the dovetail radius. The master design could work still. First of all, keep those cubes nested together. Second of all, dovetail the inner cubes outward, so the whole damn thing holds. Last, and certainly not least, in the case of the 6x6x6, I think that we can add in another circle of dovetails at the radius which would support a 7x7x7 cube. This is really hard to explain without graphics, but try to imagine this. Each dovetail ring will be a simple circle. Draw a 3x3 grid, and superimpose a circle with a radius of 1.5 grids. Now, that will be the inside of the dovetail, 1/3 of the way into the face. For a 5x5 grid, repeat the 3x3 procedure and do the same for the 5x5, except at 2.5 grids radius. That represents the next layer of the cube. Keeping the original Rubik concept of faces-edges-corners nesting in mind, we keep building out this way. It probably will be damn inconvenient to build the 7x7x7 cube this way, but I am reasonably sure that it will hold together and still retain all the necessary movements from the original cube. In the case of the 5x5x5 cube, it will look like this: abcba bdedb cefec bdedb abcba a is held by 2 b's. b is held by c and d. c is held by e. d is held by 2 e's. e is held by f. The only real weak spot is c, but it is surrounded by b's and an e. The 7x7x7 cube will look like this: abcdcba befgfeb cfhihfc dgijijd cfhihfc befgfeb abcdcba a is held by 2 b's. b is held by c and e. c is held by d and f. d is held by g. e is held by 2 f's. f is held by h and g. g is held by i. h is held by 2 i's. i is held by j. j is the center. Again, the problem shows up in d, g, and i. I think that this is unavoidable, but since the 3x3x3 cube holds together in much the same way, I think that it should be about as a 5x5x5 cube is compared to the 3x3x3 cube. Not much difference. The only problem that I have had with my 5x5x5 cube is the edge cubies, and as I have noted, the middle and third edges should be the problems, since everything else is buried within a face. I haven't built a prototype yet, but once I get finished with this semester of college (my last one), I intend to start working on this in between job-hunting and paying off loans. If anyone is interested in this idea, I would like to start correspondence on this topic. I have some diagrams available, but they don't come over too well in ASCII. If you would like a copy of my preliminaries, please E-Mail me at the following addresses. Thank you for your consideration. ************************************************************************* * * * * Internet: goffjeffreym@bvc.edu * Hailing From: * * * * * * Storm Lake, IA 50588 * * Snail: Box 260 BVC * Home of Happiness * * * * ************************************************************************* * * * 'Dr. Floyd, you are not a very practical man.' * * 'Look out there. Tell me what's practical.' * * * * -2010 * * * ********************************************************* From hoey@aic.nrl.navy.mil Wed Jan 8 21:20:58 1992 Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) id AA23181; Wed, 8 Jan 92 21:20:58 EST Received: from sun1.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA01964; Wed, 8 Jan 92 21:20:01 EST Return-Path: Received: by sun1.aic.nrl.navy.mil; Wed, 8 Jan 92 21:20:01 EST Date: Wed, 8 Jan 92 21:20:01 EST From: hoey@aic.nrl.navy.mil To: Post-NetNews@ucbvax.berkeley.edu, Cube-Lovers@life.ai.mit.edu Cc: mkt@vax5.cit.cornell.edu (Gregory E. Dionne), tlg@uknet.ac.uk (Tim.Goodwin) Subject: Rubik's Cube, the minimax number of moves Summary: 2x2x2=11(9), 3x3x3=21(18)-97(50), 4x4x4=37/41(??)-??(??) References: <1992Jan3.213615.9689@vax5.cit.cornell.edu> <564@uknet.ac.uk> Message-Id: <920108.Hoey@AIC.NRL.Navy.Mil> Keywords: Bounds, Metrics, Thistlethwaite, RCC Organization: Naval Research Laboratory, Washington, DC mkt@vax5.cit.cornell.edu (Gregory E. Dionne) asks: > Does anybody know what the minimum number of moves are required to > solve the 3x3 and/or 4x4 cubes in the worst-case scenario? and receives some answers, some of them accurate. The following is my understanding of the best answers now known, which I am sending both to rec.puzzles and the Cube-Lovers mailing list. The latter will, I hope, excuse some information repeated from the archives. First, you have to decide what you mean by a move. On grounds of symmetry and parsimony I prefer to count each quarter-turn of a face as a (QT) move. However, most of the literature counts either a quarter-turn or a half-turn of a face as a single (HT) move, and there has been more work done on the problem by the HT contingent. Second, you have to be careful to define what constitutes solved! While most people are content to make each face a solid color, some cubes have markings that display whether the face centers are twisted with respect to the rest of the cube. [This has recently been done commercially in an spectacularly braindamaged way, in a product known as ``Rubik's cube--the fourth dimension'' or some such nonsense. The mfrs have marked only four face centers, breaking symmetry while they fail to show the surprising invariant of the Supergroup. What bagbiters!] But that is a topic for other messages; I will not further discuss the invisible features of cubes here, save to note that there are more invisible features in larger cubes, and that if you take them into account, the cube will be harder to solve and require more moves than if you don't. Third, you have to understand that in either case, nobody knows the exact answer except for the tiny cubes. It boils down to knowing lower bounds L and upper bounds U, such that there must be some positions requiring at least L moves, while any position can be solved in at most U moves. I will discuss these in turn, below. For lower bounds, it is easy to calculate how many positions of Rubik's cube are achievable, and we may reason that only a few positions are within a few moves of start. Counting them, we can determine that at least 21 QT (or 18 HT) are needed to solve some positions of the cube. In fact, at least half of the positions of the cube require at least 18 HT, and at least 90% of the positions require at least 20 QT. The calculations are elementary, and have been known for over a decade. Nobody knows any other very good way of finding lower bounds. In Rubik's_Cubic_Compendium (1987), Tamas Varga writes Experts believe that even in the worst cases--the patterns furthest away from start--it should be possible to restore the cube in 20-odd [HT] moves, maybe 25, not more. However, such beliefs are clearly conjectural, based on the behavior of much simpler puzzles. The known upper bounds are constructive, consisting of a solution procedure guaranteed to solve any cube within U moves. The best known bound is embodied in a procedure invented by Morwen B. Thistlethwaite, and improved by students of Donald E. Knuth (The students are not identified in R_C_C). The improved procedure requires at most 50 HT in the worst case. Thistlethwaite was hoping (in 1980) to improve this to 41 HT, but (rumors to the contrary) he apparently did not succeed. A 1989 article by Hans Kloosterman entitled ``Rubik's Cube in 44 moves'' refers to an attempt to refine Thistlethwaite's method. I have not heard of any success there, either. Since any HT is at most 2QT, any Rubik's cube position can be solved in at most 100 QT using Thistlethwaite's method. According to my understanding of the method, this can actually be reduced to 97 QT, but this is still poor. A method tailored to minimizing QT would almost certainly guarantee a much shorter solution. Unfortunately, Thistlethwaite's method requires enormous tables of partial solution methods. Gerszon Keri describes a simpler method in R_C_C that requires at most 97 HT and which humans can memorize. The method is attributed to ``a Cambridge group,'' which I think must refer to England. According to Keri the Cambridge method has been refined to use only 79 HT, but I do not know if the refined version is still humanly comprehensible. For the 2x2x2 cube, the worst-case number of moves is known to be exactly 14 QT (11 HT). Only 276 (2644) positions require all 14 QT (11 HT). Half of the positions can be solved in 11 QT (9 HT) or fewer. For the 4x4x4 and larger cubes, the problem of defining a move is more complicated. Besides the QT/HT dichotomy, there is the question of whether a move consists of a slice (turning one part of the cube with respect to the other) or a slab (turning a 1x4x4 section of the cube with respect to the rest). We might expect that, as we do not count the center-slab moves of the 3x3x3 as a single move, we should not count the inner-slab moves of the 4x4x4 as a single move. However, I have discovered excellent reasons of symmetry (send email if you want to know) for us to consider all slabs alike, whether internal or face, with the exception of the center slab of an odd-sized cube. This is known as the Eccentric Slabist metric. According to my calculations of some years ago, some 4x4x4 positions require at least 37 slab QT or 41 slice QT to solve. The Eccentric Slabist also calculates at least 59, 81, 111, 138, 175, and 208 QT for the 5x5x5 through 10x10x10 cubes. (And yes, I've heard the widespread misinformation that Rubik's cubes larger than six cubies on an edge are impossible). I seem to recall calculating HT lower bounds, but I can't seem to find them. I do not recall whether upper bounds have been calculated for the large cubes, other than that they are O(N^2)--see J. A. Eidswick's article in the March 1986 Math Monthly. Dan Hoey Hoey@AIC.NRL.Navy.Mil From tjj@lemma.helsinki.fi Thu Jan 9 03:07:28 1992 Return-Path: Received: from funet.fi by life.ai.mit.edu (4.1/AI-4.10) id AA28910; Thu, 9 Jan 92 03:07:28 EST Received: from lemma.Helsinki.fi by funet.fi with SMTP (PP) id <17796-0@funet.fi>; Thu, 9 Jan 1992 08:46:06 +0200 Received: by lemma.helsinki.fi (5.57/Ultrix3.0-C) id AA24202; Thu, 9 Jan 92 08:46:20 +0200 Date: Thu, 9 Jan 92 08:46:20 +0200 From: tjj@lemma.helsinki.fi (Timo Jokitalo) Message-Id: <9201090646.AA24202@lemma.helsinki.fi> To: Cube-Lovers@life.ai.mit.edu Subject: Re: Rubik's Cube, the minimax number of moves I wonder how large the necessary tables for Thistlethwaite's method for the cube are? I seem to recall reading that there were a few hundred entries, but is this anywhere near? And, more important, have they been published, or does anyone have them in an electronic format? Thanks, Timo Jokitalo (tjj@rolf.helsinki.fi) From hoey@aic.nrl.navy.mil Fri Jan 10 18:35:28 1992 Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) id AA29653; Fri, 10 Jan 92 18:35:28 EST Received: from sun13.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA00290; Fri, 10 Jan 92 18:32:36 EST Return-Path: Received: by sun13.aic.nrl.navy.mil; Fri, 10 Jan 92 18:32:35 EST Date: Fri, 10 Jan 92 18:32:35 EST From: hoey@aic.nrl.navy.mil Message-Id: <9201102332.AA13941@sun13.aic.nrl.navy.mil> To: tjj@lemma.helsinki.fi (Timo Jokitalo), Cube-Lovers@life.ai.mit.edu Subject: Re: Rubik's Cube, the minimax number of moves Keywords: Upper-Bounds, Thistlethwaite, RCC, NoRMC tjj@lemma.helsinki.fi (Timo Jokitalo) asks > I wonder how large the necessary tables for Thistlethwaite's method > for the cube are? I seem to recall reading that there were a few > hundred entries.... Well, this is the information from Singmaster's _Notes_on_Rubik's_ _Magic_Cube_ (1980). Thistlethwaite's method is to work from group to subgroup as follows: G0: G1: G2: G3: G4: The following table shows the number of cosets (the index of each subgroup in the next larger group). Then I include the number of HT moves proven, anticipated, and best possible, from the 1980 N_o_R_M_C. Finally, I include the number of HT claimed in the 1987 R_C_C. It is interesting to note that the improvement did not occur where Thistlethwaite anticipated it. Step | Number of Cosets | Number of HT, 1980 | #HT, 1987 | | Proven Anticipated Best | Proven | | | 1 | G0:G1 = 2,048 | 7 7 7 | 7 2 | G1:G2 = 1,082,565 | 13 12 10 | 13 3 | G2:G3 = 663,552 | 15 14 ? 13 ? | 15 4 | G3:G4 = 29,400 | 17 17 15 ? | 15 -----+-------------------+-----------------------------+----------- Total HT | 52 50 ? 45 ? | 50 Total QT | 101 97 ? 87 ? | 97 I had thought the tables contained one entry for each coset, and so there would be over a million entries for step 2. However, I was surprised just now to notice in N_o_R_M_C that tables were only needed in step 4, and then only 172 entries, so there must be some abbreviation or algorithmic approach. Of course, when Knuth's students improved step 4, they may have changed it to use a huge lookup table; I don't know. Still, this is much better than the situation I expected in my note two days ago. In listing QT I assume that in we can require steps 1, 2, and 3 to each end with a quarter-turn. So the number of QT is at most three less than twice the number of HT. > And, more important, have they been published, or does anyone have > them in an electronic format? The bibliography in N_o_R_M_C mentions Thistlethwaite's algorithms as being in typescript, but I don't know if they were available by request, and I don't know anyone who has them. I don't know anything about the improvements by Knuth's students, and there's nothing in the R_C_C bibliography that looks like a Stanford tech report. Dan From ACW@yukon.scrc.symbolics.com Mon Jan 13 22:03:15 1992 Return-Path: Received: from YUKON.SCRC.Symbolics.COM by life.ai.mit.edu (4.1/AI-4.10) id AA21059; Mon, 13 Jan 92 22:03:15 EST Received: from PALLANDO.SCRC.Symbolics.COM by YUKON.SCRC.Symbolics.COM via INTERNET with SMTP id 761285; 13 Jan 1992 14:40:58-0500 Date: Mon, 13 Jan 1992 14:38-0500 From: Allan C. Wechsler Subject: Re: Rubik's Cube, the minimax number of moves To: hoey@aic.nrl.navy.mil, tjj@lemma.helsinki.fi, Cube-Lovers@life.ai.mit.edu In-Reply-To: <9201102332.AA13941@sun13.aic.nrl.navy.mil> Message-Id: <19920113193832.8.ACW@PALLANDO.SCRC.Symbolics.COM> I would like to see us develop a programming language for expressing cube-solving algorithms in. Then we could cooperate in trying to find an algorithm with smaller and smaller numbers of moves in the worst case. I just completed an exercise I have wanted to try for a while, a rough worst-case analysis of my own technique. It's pretty scary. It turns out that my worst case is 236 qtw. My algorithm is "bottom-heavy" -- it starts with "intuitive" moves for fixing the first few corners. These were the hardest to analyze, but they take the fewest moves. It finishes up with great big macros for the last few fiddles and fixes. For example, flipping two edges in place takes 22 qtw. Obviously a lot could be gained from tweaking the earlier part of the algorithm to guarantee that I don't need to do this at the end. From hoey@aic.nrl.navy.mil Tue Jan 14 12:49:25 1992 Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) id AA13585; Tue, 14 Jan 92 12:49:25 EST Received: from sun13.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA27636; Tue, 14 Jan 92 12:49:17 EST Return-Path: Received: by sun13.aic.nrl.navy.mil; Tue, 14 Jan 92 12:49:16 EST Date: Tue, 14 Jan 92 12:49:16 EST From: hoey@aic.nrl.navy.mil Message-Id: <9201141749.AA27091@sun13.aic.nrl.navy.mil> To: Cube-Lovers@life.ai.mit.edu Cc: "Allan C. Wechsler" Subject: A new upper bound: 91 QT Keywords: Upper-Bounds, Thistlethwaite I just wrote a quick program to count the number of QT to move from the full cube group to the subgroup generated by . Thistlethwaite computed that this takes at least 7 HT in the worst case. The surprisingly good result is that it also takes only 7 *QT* in the worst case. This reduces the upper bound I posted Friday to 91 QT. I had wondered if the worst cases could be reduced by choosing a different pair of faces to restrict to half-twists. Unfortunately, the all-edges-flipped position is one of those that requires at least 7 HT (and so 7 QT), and by symmetry it cannot be improved. Allan C. Wechsler analyzed his own cube-solving method, finding that: > For example, flipping two edges in place takes 22 qtw. This can be done in 16 QT, though I don't know if that is the best known. Any pair can be flipped with a conjugate of the 14 QT slice mono-op FOTAROFATO-RAM TAFORATOFA-ROM (FT'RF'T L'R B'TR'BT' LR'). Adjacent and antipodal pairs require the introduction of a non-cancelling QT in the conjugator. > Obviously a lot could be gained from tweaking the earlier part of > the algorithm to guarantee that I don't need to do this at the end. Probably, but it's hard to make that guarantee. The problem is that unless you flip edges in place with no other action (the very problem you're trying to avoid) you may affect the later choices in the algorithm, making the earlier tweaks wrong for that branch of the algorithm. For instance, the 7-QT method my program found solves the orientation of all the edges (using a particular non-standard labeling of the orientation that, when solved, is invariant under F^2, B^2, L, R, T, and D). But it may permute edges, and permute and twist corners, so it may not form a useful part of an arbitrary cube-solving algorithm. It works in Thistlethwaite's only because he is careful in all branches of the rest of the algorithm never to mix up the orientation of those edges. Dan Hoey Hoey@AIC.NRL.Navy.Mil From raymond@cps.msu.edu Tue Jan 14 13:22:14 1992 Return-Path: Received: from galaxy.cps.msu.edu by life.ai.mit.edu (4.1/AI-4.10) id AA14497; Tue, 14 Jan 92 13:22:14 EST Received: from cpss16.cps.msu.edu by galaxy.cps.msu.edu (4.1/rpj-5.0); id AA22563; Tue, 14 Jan 92 13:22:08 EST Received: by cpss16.cps.msu.edu (4.1/4.1) id AA01898; Tue, 14 Jan 92 13:22:06 EST Date: Tue, 14 Jan 92 13:22:06 EST From: raymond@cps.msu.edu Message-Id: <9201141822.AA01898@cpss16.cps.msu.edu> To: cube-lovers@ai.mit.edu Subject: Cube software If anyone is interested, I wrote a program for examining the cycle structure of various move sequences on Rubik's cube. It's got a lex and yacc front end, which let you enter moves using the UDLRFB notation. You give it a move sequence, and it will give you the permutation in cycle notation, taking edge flips and corner twists into account. For example, you can say (R'D2R B'U2B)2 which is a corner twister, and it will tell you that the urf corner is twisted clockwise, and the dlb corner is twisted clockwise. YOu can also give names to sequences, and refer to the sequence by its name. You can save and load named sequences from a file. The code is pretty quick-and-dirty, but I'll email the source to anyone who is interested. I wrote it on a PC with Microsoft C 5.1, and flex and bison, but it should work fine under Unix. Carl Raymond From ACW@yukon.scrc.symbolics.com Tue Jan 14 19:20:46 1992 Return-Path: Received: from YUKON.SCRC.Symbolics.COM by life.ai.mit.edu (4.1/AI-4.10) id AA26037; Tue, 14 Jan 92 19:20:46 EST Received: from PALLANDO.SCRC.Symbolics.COM by YUKON.SCRC.Symbolics.COM via INTERNET with SMTP id 761636; 14 Jan 1992 13:46:59-0500 Date: Tue, 14 Jan 1992 13:44-0500 From: Allan C. Wechsler Subject: A new upper bound: 91 QT To: hoey@aic.nrl.navy.mil, Cube-Lovers@life.ai.mit.edu Cc: ACW@yukon.scrc.symbolics.com In-Reply-To: <9201141749.AA27091@sun13.aic.nrl.navy.mil> Message-Id: <19920114184432.1.ACW@PALLANDO.SCRC.Symbolics.COM> Regarding the meta-approach of descending through a series of subgroups, how much leverage does properly selecting the chain give you? It seems like the jump from to is pretty large. There are probably other paths through the subgroup lattice. Does anyone have a table of subgroups? From @mitvma.mit.edu:rb%uk.ac.ic.cc@sunss1cc-gw.cc.ic.ac.uk Wed Jan 15 10:38:59 1992 Return-Path: <@mitvma.mit.edu:rb%uk.ac.ic.cc@sunss1cc-gw.cc.ic.ac.uk> Received: from mitvma.mit.edu by life.ai.mit.edu (4.1/AI-4.10) id AA16719; Wed, 15 Jan 92 10:38:59 EST Received: from MITVMA.MIT.EDU by mitvma.mit.edu (IBM VM SMTP V2R2) with BSMTP id 7594; Wed, 15 Jan 92 10:39:15 EST Received: from UKACRL.BITNET by MITVMA.MIT.EDU (Mailer R2.08 R208004) with BSMTP id 9520; Wed, 15 Jan 92 10:39:14 EST Received: from RL.IB by UKACRL.BITNET (Mailer R2.07) with BSMTP id 6307; Wed, 15 Jan 92 15:37:45 GMT Received: from RL.IB by UK.AC.RL.IB (Mailer R2.07) with BSMTP id 6650; Wed, 15 Jan 92 15:37:43 GMT Via: UK.AC.IC.CC; 15 JAN 92 15:37:41 GMT X-Received: from sunss1cc-gw.cc.ic.ac.uk by mvax.cc.ic.ac.uk with SMTP id aa23202; 15 Jan 92 15:36 WE Received: from suns1cc.cc.ic.ac.uk by sunss1cc.cc.ic.ac.uk (4.1/3.0) id AA14635; Wed, 15 Jan 92 15:36:40 GM From: rb@cc.ic.ac.uk Date: Wed, 15 Jan 92 15:36:39 GMT Message-Id: <243.9201151536@suns1cc.cc.ic.ac.uk> To: cube-lovers Subject: Minimove Solution Sender: rb%uk.ac.ic.cc@sunss1cc-gw.cc.ic.ac.uk I have recently read a book entitled "Learning To Solve Problems By Searching For Macro Operators" by Richard E. Korf (exact spelling not in my head). In a nutshell the book discusses an algorithmic method of problem soving by discovering useful operators. The method was applied to the 3D Rubik cube and as I remember managed on average to solve the problem in about 37 - 38 QTW. Apparently it was slightly better than human experts. The tables discovered by the program weren't terribly large :-)! Also either in that book or another I remember an approach to the minimove problem based on measuring the disorderedness of the cube after n random moves. The measure of disorder was based on the number of correct colours on each face or something like that. From a graph of this measure averaged over (I suppose) some number of trials it seems as though the cube can be maximally disordered in around 18 moves. It would seem that this means that on average the cube should be restorable in about the same number of moves. Of course this doesn't help giving tight bounds, but I guess it gives some hope to the clever guys. As an aside I have something called a Supernova which is dodekahedral (i.e. has 12 5 sided faces each of which can rotate) which is alledged to be 10power 43 more complicated than the 3cube. I can solve it using fairly standard cube methods (only the last face is slightly difficult) in about 20 times my 3-bube time. Has anyone else seen this and or is there any standard notation + information on this thing. Robin (not batperson) Becker From raymond@cps.msu.edu Wed Jan 15 11:07:35 1992 Return-Path: Received: from galaxy.cps.msu.edu by life.ai.mit.edu (4.1/AI-4.10) id AA17950; Wed, 15 Jan 92 11:07:35 EST Received: from cpss11.cps.msu.edu by galaxy.cps.msu.edu (4.1/rpj-5.0); id AA07139; Wed, 15 Jan 92 11:07:33 EST Received: by cpss11.cps.msu.edu (4.1/4.1) id AA01817; Wed, 15 Jan 92 11:07:32 EST Date: Wed, 15 Jan 92 11:07:32 EST From: raymond@cps.msu.edu Message-Id: <9201151607.AA01817@cpss11.cps.msu.edu> To: cube-lovers@ai.mit.edu Subject: Cube software I received 8 requests for my cube cycle program. They are: berson@cs.pitt.edu bosch@mips.com DEVO@GDLVM7.VNET.IBM.COM keng@zcar.asd.sgi.com tout@cps.msu.edu palmerp@MATH.ORST.EDU schmidtg@iccgcc.decnet.ab.com tjj@rolf.helsinki.fi If I omitted anyone, please send your request again. Carl From gkomatsu@uhunix.uhcc.hawaii.edu Thu Jan 16 04:08:17 1992 Return-Path: Received: from uhunix.uhcc.Hawaii.Edu by life.ai.mit.edu (4.1/AI-4.10) id AA01167; Thu, 16 Jan 92 04:08:17 EST Received: by uhunix.uhcc.Hawaii.Edu (4.1/Sun490) id AA04197; Wed, 15 Jan 92 23:08:13 HST Date: Wed, 15 Jan 1992 23:08:12 HST From: Galen Tatsuo Komatsu To: cube-lovers@life.ai.mit.edu Subject: Rubik's Magic Clock & Triamid Message-Id: ...hmm new to this list, been reading some of the postings and things just seem to go *FOOM*, right over my head. But it didn't stop me from asking these..... Rubik's Magic Clock. Sister is Japan sent me this for Christmas (Have still yet to translate the instructions...as if I need it!) and solved it in a day... Well, more like "stumbled" upon the solution after a day of fiddling with it. But I continued to play with it, and came upon this..... Sometimes when I give one of the wheels a good quick "flick", one of the gears inside slips. Result is one (or maybe two) of the clock faces affected is an hour "behind" (or ahead) of the others. Deep in my mind I concluded that this rendered the puzzle unsolveable. And I ended up pulling out a screwdriver and readjusting the face (or I just "zeroed" all of them.) Was I correct in this conclusion? (...oh yea, she sent this for Christmas '88, not this past year. I'm not THAT behind the times! THIS Christmas I recieved.....) Rubik's Triamid. In the instructions it says, "It is physically possible to dismember Triamid into it's 10 constituent elements and reassemble it into a complete Triamid. A word of warning however--as there are 2 possible ways of doing this (a right and a left one) solving the puzzle after such a ressembly has an additional sting in the tail." What exactly is this "sting"? And what did it mean by "right and left"? (if there's some joke here, I missed it...) I was wondering, if I took it apart and reassembled it to a completed form, the puzzle is still solvable, I just scramble it and get back to the form I reassembled it to. So this can't be the "sting" mentioned. Unless it meant reassemble it to some unfinished form. Next question... Sometimes when I play around with it, one of the corner pieces pops off and lands on the floor. I pick it up and put it back on wondering, how was it originally oriented? And considering the 11/12 chance that I'll have put it back on wrong way. Have I just rendered the Triamid (once again) "unsolveable"? Final question, for fun... Anyone bought more than one Triamid, and put 'em together to make a "Monster(a)mid"? =^) ...also for a Square-1 for x-mas too, still fiddling around with it too. And have yet to lay my hands on Rubik's Tangle, Dice, and Fifteen. But NOT the Cube^4 (was that it?) Couls never solve the original, why should I touch this one? =^/ Galen Komatsu gkomatsu@uhunix.uhcc.hawaii.edu ! From tjj@lemma.helsinki.fi Thu Jan 16 07:15:27 1992 Return-Path: Received: from figbox.funet.fi by life.ai.mit.edu (4.1/AI-4.10) id AA05025; Thu, 16 Jan 92 07:15:27 EST Received: from lemma.Helsinki.FI by FIGBOX.FUNET.FI (PMDF #12388) id <01GFDTEK1W4000543M@FIGBOX.FUNET.FI>; Thu, 16 Jan 1992 12:15 GMT Received: by lemma.helsinki.fi (5.57/Ultrix3.0-C) id AA28342; Thu, 16 Jan 92 14:14:15 +0200 Date: Thu, 16 Jan 92 14:14:15 +0200 From: tjj@lemma.helsinki.fi (Timo Jokitalo) Subject: Re: Rubik's Magic Clock & Triamid To: cube-lovers@life.ai.mit.edu, gkomatsu@uhunix.uhcc.hawaii.edu Message-Id: <9201161214.AA28342@lemma.helsinki.fi> I haven't tried the Triamid or Tangle, but I bought the Fifteen and the Dice. I'm still thinking of attacking the Fifteen, but I really hate the Dice after I twice had gotten four of the faces in their right places, knocked the thing a bit too much, which caused the plates to fall to the bottom. I hate that **** thing and won't touch it again for a long time! Timo From pbeck@pica.army.mil Wed Jan 22 00:26:53 1992 Return-Path: Received: from FSAC1.PICA.ARMY.MIL by life.ai.mit.edu (4.1/AI-4.10) id AA22844; Wed, 22 Jan 92 00:26:53 EST Received: by FSAC1.PICA.ARMY.MIL id aa23162; 21 Jan 92 15:23 EST Date: Tue, 21 Jan 92 15:18:15 EST From: Peter Beck (BATDD) To: reid@math.berkeley.edu Cc: cube-lovers@life.ai.mit.edu Subject: cff Message-Id: <9201211518.aa19961@FSAC1.PICA.ARMY.MIL> CUBISM FOR FUN is the newsletter of the DUtch Cubist Club. It is in english. The club is alive and well and is planning to host the 1993 International Puzzle party. To subscribe send US$11 (in cash or international money order) to LUCIEN MATTHIJSSE LOENAPAD 12 3402 EP IJSSELSTEIN NETHERLANDS I will be happy to answer any questions you may have. THE FUTURE IS PUZZLING, BUT CUBING IS FOREVER !! From reid@math.berkeley.edu Wed Jan 22 02:29:03 1992 Return-Path: Received: from math.berkeley.edu ([128.32.183.94]) by life.ai.mit.edu (4.1/AI-4.10) id AA24953; Wed, 22 Jan 92 02:29:03 EST Received: from skippy.berkeley.edu.berkeley.edu by math.berkeley.edu (4.1/1.33(math)) id AA03361; Tue, 21 Jan 92 23:27:28 PST Date: Tue, 21 Jan 92 23:27:28 PST From: reid@math.berkeley.edu (michael reid) Message-Id: <9201220727.AA03361@math.berkeley.edu> To: cube-lovers@ai.mit.edu Subject: Re: Rubik's cube dice tops (Spoiler) Cc: ronnie@cisco.com a while ago (last month), Dan (hoey@aic.nrl.navy.mil) writes: > Last week ronnie@cisco.com (Ronnie Kon) challenged us to find Rubik's > cube patterns with dice pips for 1, 2, and 3 on the three pairs of > opposite sides. He claimed it could be done in fourteen HST, where > one HST is a turn of a face or center slice by 90 or 180 degrees. I > responded that it could be done in thirteen HST. Here is how. I will > use this opportunity to practice the enhanced Varga Rubiksong I > described (unfortunately with many typos) on 22 Feb 90. > The (only such) pattern is the composition of Four-Spot and Laughter. > We have long known the processes [ description deleted ] > This uses only 13 HST. This is also the shortest process I know of in > the normal metric: 18 QT, which is not so bad for the combination of here's a shorter way. in the "flubrd" notation, use: D' F^2 R U^2 F^2 B^2 D^2 R^2 L' F^2 U' D^2 which is 11 "HST" (which i call "slice turns"). this is also 12 "face" turns, but 20 quarter turns. this can also be done in only 14 quarter turns as follows: F^2 U D F B U D F B U D F B' (*) note that this can easily be obtained from the well-known manuever for "laughter": ( F B C_U )^6 (**) where C_ means "turn the whole cube" (as in Bandelow's book). note that this manuever reorients the cube. then manuever (*) is just the "flubrd" translation of the manuever M_F (**) M_F' (without the cube reorientation), where M_ means "turn the middle slice," again, as in Bandelow's book. here's a question for those out there with 5x5x5 cubes: have you noticed that the stickers seem to be more happy on the floor than on the facelets of the cube? the more i use my cube, the more restless they seem to become. does anyone know of a good cure for this? i'm thinking of taking them all off, cleaning off the glue (or gum or whatnot) and gluing them back on, using a stronger glue. anyone have any suggestions for what kind of glue? i'll let you know how my experiment works. mike From wft@math.canterbury.ac.nz Wed Jan 29 04:27:21 1992 Return-Path: Received: from CANTVA.CANTERBURY.AC.NZ by life.ai.mit.edu (4.1/AI-4.10) id AA11553; Wed, 29 Jan 92 04:27:21 EST Received: from math.canterbury.ac.nz by csc.canterbury.ac.nz (PMDF #12052) id <01GFW95D1YZK9IB0HC@csc.canterbury.ac.nz>; Wed, 29 Jan 1992 17:00 +1300 Received: by math.canterbury.ac.nz (4.1/SMI-4.1) id AA29423; Wed, 29 Jan 92 17:00:01 NZD Date: Wed, 29 Jan 92 17:00:01 NZD From: wft@math.canterbury.ac.nz (Bill Taylor) Subject: subgroups To: Cube-Lovers@ai.mit.edu Cc: wft@cantva.canterbury.ac.nz Message-Id: <9201290400.AA29423@math.canterbury.ac.nz> X-Envelope-To: Cube-Lovers@AI.MIT.EDU On 14 Jan 1992, Allan C. Wechsler posted >Regarding the meta-approach of descending through a series of subgroups, >how much leverage does properly selecting the chain give you? It seems >like the jump from to is pretty large. >There are probably other paths through the subgroup lattice. > >Does anyone have a table of subgroups? There hasn't been any response to this, seemingly, which is a pity. In any event, I would like to know of any other well-known subgroups. There are the slice group; double-slice group; U group; square group; anti-slice group. How many others are there not mentioned here, that people know of ? From pbeck@pica.army.mil Wed Feb 26 07:50:17 1992 Return-Path: Received: from FSAC1.PICA.ARMY.MIL ([129.139.68.8]) by life.ai.mit.edu (4.1/AI-4.10) id AA24169; Wed, 26 Feb 92 07:50:17 EST Date: Wed, 26 Feb 92 7:42:09 EST From: Peter Beck (BATDD) To: cube-lovers@ai.mit.edu Subject: news Message-Id: <9202260742.aa03535@FSAC1.PICA.ARMY.MIL> What's UP - GAMES magazine is sponsoring "WORLD PUZZLE TEAM CHAMPIONSHIPS" in NYC June 24-28; registration forms in April issue of GAMES, on newsstands march 1 - NEW PUZZLE It is called "PYRIX" (retails for $10, I do not have a retail source) and is from: Enpros Novelty Products, Lorentzstraat 2, 2912 AH Niewerkerk aan den IJssel, The Netherlands - tel 31 (0)1803-19133 DESCRIPTION: The puzzle is an assembly folding puzzle based on a size 3 tetrahedron. The tetrahedron is dissected into 3 regular octahedrons and 11 tetrahedrons (1/3 the size of the original). These pieces are strung on a thread like a necklace; an octahedron, 3 tetras, an octahedron, etc except for one position that has only 2 tetras. The octahedrons are threaded on the diagonal of their square cross section. OBJECT: The faces are colored and the object is to not only assemble a tetra but of course to do it with solid colored faces, the enclosure says that there are 2 solutions as they have colored and strung the pieces. PRELIMINARY REVIEW: It took about 1 hour. The puzzle is awkward to manipulate since it falls apart easily. Doing it on a flat surface and using tape to hold it together seems to be the trick. From pbeck@pica.army.mil Fri Mar 13 19:31:17 1992 Return-Path: Received: from FSAC1.PICA.ARMY.MIL by life.ai.mit.edu (4.1/AI-4.10) id AA12037; Fri, 13 Mar 92 19:31:17 EST Received: by FSAC1.PICA.ARMY.MIL id aa13294; 13 Mar 92 14:45 EST Date: Fri, 13 Mar 92 13:57:41 EST From: Peter Beck (BATDD) To: cube-lovers@ai.mit.edu Subject: 12 th puzzle party Message-Id: <9203131357.aa04103@FSAC1.PICA.ARMY.MIL> ............................................................... <--> 12th International puzzle collector's party and fair " UPDATE" <--> transcribed by pbeck, 3/13/92 ............................................................... WHEN ---- 7/31/92 - 8/2 WHERE ---- Korakuen Kaikan LODGING ---- about $70 per night at either 1) Satellite Hotel Korakuen 2) Koraku Garden Hotel ---- about $20 per night at Tokyo International Youth Hostel, 10 minute walk away but next to Nob's Studio *** INVITATIONS *** Admission by invitation only!!! Contact: Mr. Nob Yoshigahara, 4-10-1-408 Iidabashi, Tokyo 102 Japan before APRIL 15, 1992 AGENDA: (final details,ie, cost, food service & entertainment will be sent to registrants) 7/31 18:00 - 20:00 welcoming party 8/1 10:00 - 20:00 collectors and dealers 8/2 unfinished business ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ From pbeck@pica.army.mil Tue Apr 14 12:15:09 1992 Return-Path: Received: from COR4.PICA.ARMY.MIL by life.ai.mit.edu (4.1/AI-4.10) id AA03146; Tue, 14 Apr 92 12:15:09 EDT Date: Tue, 14 Apr 92 7:48:14 EDT From: Peter Beck (BATDD) To: cube-lovers@ai.mit.edu Subject: puzzle rings Message-Id: <9204140748.aa18790@COR4.PICA.ARMY.MIL> Jewelry quality puzzle rings are available from: as of 4/91, JOSE GRANT 3000 SUMMER STREET STANFORD, CT 06905 203-327-4055 800-426-1947 I am posting this to correct mis-information I may have sent out. If this is incorrect please let me know and I will track down the corrrect info. THE FUTURE IS PUZZLING, but CUBING is FOREVER!! pete beck From wft@math.canterbury.ac.nz Wed Apr 15 01:19:50 1992 Return-Path: Received: from CANTVA.CANTERBURY.AC.NZ by life.ai.mit.edu (4.1/AI-4.10) id AA22905; Wed, 15 Apr 92 01:19:50 EDT Received: from math.canterbury.ac.nz by csc.canterbury.ac.nz (PMDF #12052) id <01GIVU9X7N1CD7PYTP@csc.canterbury.ac.nz>; Wed, 15 Apr 1992 17:19 +1200 Received: by math.canterbury.ac.nz (4.1/SMI-4.1) id AA13903; Wed, 15 Apr 92 17:19:18 NZS Date: Wed, 15 Apr 92 17:19:18 NZS From: wft@math.canterbury.ac.nz (Bill Taylor) Subject: God's algorithm To: Cube-Lovers@ai.mit.edu Message-Id: <9204150519.AA13903@math.canterbury.ac.nz> X-Envelope-To: Cube-Lovers@AI.MIT.EDU In rec.puzzles, sijben@cs.utwente.nl (Paul Sijben) writes: > As far a I know is the maximum number of moves requierd to solve The > Cube is just over 30 (35 by the last count a year ago, and decending). > Someone in the NKC (Nederlandse Kubus Club= dutch cube club) was busy > working on a system hoping to reach god's algorythm. I can dig in my > archives if anyone want more precice infomation. Has anyone else heard anything of this business ? From reid@math.berkeley.edu Wed Apr 15 01:54:00 1992 Return-Path: Received: from math.berkeley.edu by life.ai.mit.edu (4.1/AI-4.10) id AA23176; Wed, 15 Apr 92 01:54:00 EDT Received: from phnom-penh.berkeley.edu.berkeley.edu by math.berkeley.edu (4.1/1.33(math)) id AA29772; Tue, 14 Apr 92 22:53:57 PDT Date: Tue, 14 Apr 92 22:53:57 PDT From: reid@math.berkeley.edu (michael reid) Message-Id: <9204150553.AA29772@math.berkeley.edu> To: Cube-Lovers@ai.mit.edu, wft@math.canterbury.ac.nz Subject: Re: God's algorithm > From: wft@math.canterbury.ac.nz (Bill Taylor) > Subject: God's algorithm > In rec.puzzles, sijben@cs.utwente.nl (Paul Sijben) writes: > > > As far a I know is the maximum number of moves requierd to solve The > > Cube is just over 30 (35 by the last count a year ago, and decending). > > Someone in the NKC (Nederlandse Kubus Club= dutch cube club) was busy > > working on a system hoping to reach god's algorythm. I can dig in my > > archives if anyone want more precice infomation. > > Has anyone else heard anything of this business ? well, it's been kicking around in both rec.puzzles and sci.math lately. maybe you should ask if anyone has heard any follow-up to the above. i've sent away to the dutch cubists' club for membership and info, but they want payments in the form of international money orders (which probably means a good month or two delay). if/when i have some more info on this, i'll gladly share it with cube-lovers. mike From ccw@eql.caltech.edu Sat Apr 18 23:17:20 1992 Return-Path: Received: from EQL.Caltech.Edu by life.ai.mit.edu (4.1/AI-4.10) id AA27330; Sat, 18 Apr 92 23:17:20 EDT Date: Sat, 18 Apr 92 20:17:11 PDT From: ccw@eql.caltech.edu (Chris Worrell) Message-Id: <920418201450.2b6009a5@EQL.Caltech.Edu> Subject: Some solutions to Rubik's Tangle have been found. To: Cube-Lovers@ai.mit.edu (No spoilers are included) I now know two distinct solutions to Rubik's Tangle. Each of these solutions can be done with each 5x5 set, 1-4. I have not yet found any solutions to the 10x10 puzzle. I do know that if the 10 by 10 is composed of four 5x5 solutions, than my solutions of the 5x5 do not lead to a solution of the 10x10. I am now seeking a solution where all 100 pieces can be used anywhere in the 10x10, not just in a corner of the 10x10 for its own 5x5 set. Unfortunately, these solutions were found by brute force, not by any real calculation. I have not been able to discover any "Science" about the puzzle which contributes to any discovery of a solution. These solutions were found by hand, not by a computer search. So there may be other solutions to the basic puzzle which are still unknown. My search path has approximately 750 cases in it, of which I have tested about 300. One solution was found by 'accident' in that I have not yet looked at the case which actually yields that solution, but one of the test cases had been 'close' to a solution, so I looked outside my search path. The other solution was found in my search path, so it was not found by accident. (except by luck that it was at case 300 not 750) GENERAL THOUGHTS ON RUBIK'S TANGLE AS A PUZZLE In short, it is not a good puzzle. It will never be popular. Solutions might only be findable by Computer, by Luck, and by Stubborness (brute-force). As far as I can tell the only real method of solution is by using a computer. I did it by hand because I am stubborn, and I did get lucky. My search path contained 750 cases, but I had already considered search paths with an estimated 4000 and 8000 cases. These are so large that I had never even completed the basic enumeration of cases. A hand search of this magnitude is almost impossible. There are too many places for errors, and no real ways of checking. The amount of time is also absurd. I worked on between 1 and 8 of my test cases at a time, with about 250 of these groups in my search path. (later in the search I would have, on ocassion, looked at 16 at once). Sometimes a group could be disposed of within 20 minutes, but sometimes it took several hours. Has anybody discovered more mathematical content than I have? ---Chris Worrell (ccw@eql.caltech.edu) From pl1x+@andrew.cmu.edu Sat Apr 18 23:43:08 1992 Return-Path: Received: from po5.andrew.cmu.edu by life.ai.mit.edu (4.1/AI-4.10) id AA27728; Sat, 18 Apr 92 23:43:08 EDT Received: by po5.andrew.cmu.edu (5.54/3.15) id for cube-lovers@ai.mit.edu; Sat, 18 Apr 92 23:43:00 EDT Received: via switchmail; Sat, 18 Apr 1992 23:42:59 -0400 (EDT) Received: from pcs6.andrew.cmu.edu via qmail ID ; Sat, 18 Apr 1992 23:41:47 -0400 (EDT) Received: from pcs6.andrew.cmu.edu via qmail ID ; Sat, 18 Apr 1992 23:41:45 -0400 (EDT) Received: from mms.0.1.873.MacMail.0.9.CUILIB.3.45.SNAP.NOT.LINKED.pcs6.andrew.cmu.edu.pmax.ul4 via MS.5.6.pcs6.andrew.cmu.edu.pmax_ul4; Sat, 18 Apr 1992 23:41:45 -0400 (EDT) Message-Id: Date: Sat, 18 Apr 1992 23:41:45 -0400 (EDT) From: Peter Andrew Lopez To: cube-lovers@ai.mit.edu, ccw@eql.caltech.edu (Chris Worrell) Subject: Re: Some solutions to Rubik's Tangle have been found. Cc: In-Reply-To: <920418201450.2b6009a5@EQL.Caltech.Edu> References: <920418201450.2b6009a5@EQL.Caltech.Edu> I love cubes But i'll never admit it! cube-annonymous From Don.Woods@eng.sun.com Sun Apr 19 02:58:44 1992 Return-Path: Received: from Sun.COM by life.ai.mit.edu (4.1/AI-4.10) id AA28800; Sun, 19 Apr 92 02:58:44 EDT Received: from Eng.Sun.COM (zigzag-bb.Corp.Sun.COM) by Sun.COM (4.1/SMI-4.1) id AA25155; Sat, 18 Apr 92 23:58:35 PDT Received: from colossal.Eng.Sun.COM by Eng.Sun.COM (4.1/SMI-4.1) id AA23499; Sat, 18 Apr 92 23:58:43 PDT Received: by colossal.Eng.Sun.COM (4.1/SMI-4.1) id AA04381; Sat, 18 Apr 92 23:58:42 PDT Date: Sat, 18 Apr 92 23:58:42 PDT From: Don.Woods@eng.sun.com (Don Woods) Message-Id: <9204190658.AA04381@colossal.Eng.Sun.COM> To: ccw@eql.caltech.edu, cube-lovers@ai.mit.edu, pl1x+@andrew.cmu.edu Subject: Re: Some solutions to Rubik's Tangle have been found. > From: Peter Andrew Lopez > I love cubes > But i'll never admit it! > cube-annonymous In addition to being self-contradicting (and misspelled), the above seems to have nothing to do with the subject of Rubik's Tangle. Lest this message suffer the same flaw, I'll add that I too was unable to come up with any mathematical or intuitive method for solving the Tangle. I solved mine by computer. (I've always been fairly good at finding ways to prune a bushy search tree down to manageable size.) I have Tangle #1 and can confirm it has exactly two solutions (ignoring overall rotations of the 5x5 array, of course). I haven't had a chance to examine closely the other Tangles. How do they differ from #1? Do they use a different pattern of connectivity on the tiles? Do they have a different mix of the permutations? (#1 has each 4-color permutation exactly once, except for one permutation which appears twice.) I hope they do not simply permute the colors relative to #1; that would be dull since they would then be identical puzzles, and collecting more than one would be silly except for the purpose of building the 10x10 combined puzzle. -- Don. From ACW@riverside.scrc.symbolics.com Fri Apr 24 14:34:12 1992 Return-Path: Received: from RIVERSIDE.SCRC.Symbolics.COM by life.ai.mit.edu (4.1/AI-4.10) id AA20016; Fri, 24 Apr 92 14:34:12 EDT Received: from TRANTOR.SCRC.Symbolics.COM by RIVERSIDE.SCRC.Symbolics.COM via INTERNET with SMTP id 797732; 24 Apr 1992 14:33:30-0400 Date: Fri, 24 Apr 1992 14:33-0400 From: Allan C. Wechsler Subject: Some solutions to Rubik's Tangle have been found. To: ccw@eql.caltech.edu, Cube-Lovers@ai.mit.edu In-Reply-To: <920418201450.2b6009a5@EQL.Caltech.Edu> Message-Id: <19920424183328.2.ACW@TRANTOR.SCRC.Symbolics.COM> I hope I'm not wasting too many people's time, but... can you describe the Rubik's Tangle puzzle for those of us who haven't seen it? Your description was interesting, but I wonder about your statement that it can't be solved without a computer. Perhaps you just didn't have the right insight. From Don.Woods@eng.sun.com Fri Apr 24 17:56:26 1992 Return-Path: Received: from Sun.COM by life.ai.mit.edu (4.1/AI-4.10) id AA27121; Fri, 24 Apr 92 17:56:26 EDT Received: from Eng.Sun.COM (zigzag-bb.Corp.Sun.COM) by Sun.COM (4.1/SMI-4.1) id AA27750; Fri, 24 Apr 92 14:56:15 PDT Received: from colossal.Eng.Sun.COM by Eng.Sun.COM (4.1/SMI-4.1) id AA24248; Fri, 24 Apr 92 14:56:17 PDT Received: by colossal.Eng.Sun.COM (4.1/SMI-4.1) id AA22010; Fri, 24 Apr 92 14:56:22 PDT Date: Fri, 24 Apr 92 14:56:22 PDT From: Don.Woods@eng.sun.com (Don Woods) Message-Id: <9204242156.AA22010@colossal.Eng.Sun.COM> To: ACW@riverside.scrc.symbolics.com Subject: Description of Rubik's Tangle Cc: Cube-Lovers@ai.mit.edu > From: Allan C. Wechsler > I hope I'm not wasting too many people's time, but... can you describe > the Rubik's Tangle puzzle for those of us who haven't seen it? Your > description was interesting, but I wonder about your statement that it > can't be solved without a computer. Perhaps you just didn't have the > right insight. I would love to hear an insight that makes this puzzle tractible in real time (hours rather than days) by hand. Here's a brief description of Tangle #1; as I said in my earlier posting, I don't know how the other 3 differ, though I'm pretty sure they each have the same number of tiles. Tangle #1 consists of 25 square tiles, each of which has four colored ropes crossing it in the following pattern. (Note: This may be mirror imaged, since I'm working from memory.) --------------------- | @ # | | @ # | |$$ @ # %%%%| | $ @ %#% | | $ @ %% # | | $ %@ # | | $ %% @@# | | %%% #@@ | |%%%% $ # @@@| | $ # | | $ # | --------------------- The connection marked with $ actually wanders around the tile a bit more, but the connectivity is as shown. The object is to place the tiles in a 5x5 array such that wherever two tiles touch the colors of the ropes match. In Tangle #1 each permutation of colors occurs once, with one permutation occurring twice. The box says that if you get all four Tangles, you can put them together to make a 10x10 array under the same color-matching constraints. -- Don. From ccw@eql.caltech.edu Tue Apr 28 01:59:05 1992 Return-Path: Received: from EQL.Caltech.Edu by life.ai.mit.edu (4.1/AI-4.10) id AA25804; Tue, 28 Apr 92 01:59:05 EDT Date: Sat, 25 Apr 92 08:47:55 PDT From: ccw@eql.caltech.edu (Chris Worrell) Message-Id: <920425084746.2bc000e4@EQL.Caltech.Edu> Subject: Description of Tangle, Part 2 To: cube-lovers@ai.mit.edu Cc: don.woods@eng.sun.com, acw@riverside.scrc.symbolics.com Annotating Don.Woods diagram (which is in the correct orientation) 2 3 --------------------- | @ # | | @ # | 1 |$$ @ # %%%%| 4 | $ @ %#% | | $ @ %% # | | $ %@ # | | $ %% @@# | | %%% #@@ | 4 |%%%% $ # @@@| 2 | $ # | | $ # | --------------------- 1 3 The duplicate piece in each tangle is: 1 2 3 4 Tangle 1 Blue Red Yellow Green Tangle 2 Yellow Blue Green Red Tangle 3 Green Yellow Blue Red Tangle 4 Red Green Yellow Blue All 4 Tangles are the same puzzle, just colored differently. Each has all 24 color permutations, plus a duplicate. Each Tile also has a letter (A-Y) on the back, and a reference to the Tangle that it occurs in. These letters appear to be for reference only. I have found no corresponddence between the letterings in one puzzle, and the letterings in another. I just use them as a convenience for recording configurations, and sorting through the tiles. ------ ccw@eql.caltech.edu (Chris Worrell) From reid@math.berkeley.edu Wed Apr 29 04:37:32 1992 Return-Path: Received: from math.berkeley.edu by life.ai.mit.edu (4.1/AI-4.10) id AA07345; Wed, 29 Apr 92 04:37:32 EDT Received: from beirut.berkeley.edu.berkeley.edu by math.berkeley.edu (4.1/1.33(math)) id AA13934; Wed, 29 Apr 92 01:37:26 PDT Date: Wed, 29 Apr 92 01:37:26 PDT From: reid@math.berkeley.edu (michael reid) Message-Id: <9204290837.AA13934@math.berkeley.edu> To: cube-lovers@ai.mit.edu Subject: an upper bound on god's number in an earlier message, i promised to pass along any information i obtained about progress on the upper bound for the length of god's algorithm. i've received a copy of the article "rubik's cube in 42 moves" by hans kloosterman, which i summarize below. first here are some caveats: * i haven't verified this algorithm. * throughout, `move' refers to any turn of a single face. i don't know what bound is achieved in the quarter-turn metric. * it may be the case that this algorithm has been improved. please let me (and cube-lovers) know if you have more information. "rubik's cube in 42 moves" by hans kloosterman the algorithm used here is a slight variant of thistlethwaite's algorithm. we work through a chain of subgroups: G_0 = < F, B, L, R, U, D > ( full group ) G_1 = < F2, B2, L, R, U, D > G_2 = < F2, B2, L2, R2, U, D > G_3 = subgroup of G_2 in which all U-cubies are in the U face (thus all D-cubies are in the D face and all U-D slice cubies are in the U-D slice) G_4 = { 1 }. there are four stages: stage i reduces our pattern from G_{i-1} to G_i. the indices of the subgroups are: ( G_0 : G_1 ) = 2048 = 2^11 ( G_1 : G_2 ) = 1082565 = 3^9 * 5 * 11 ( G_2 : G_3 ) = 4900 = 2^2 * 5^2 * 7^2 ( G_3 : G_4 ) = 3981310 = 2^14 * 3^5 the maximum number of moves in the stages are 7, 10, 8 and 18 respectively, for a maximum total of 43 moves. however, in the worst-case scenario of stages 3 and 4, it was checked that no position actually required 26 moves; i.e. we can arrange a cancellation between the two stages. thus stages 3 and 4 together require 25 moves at most, which gives the final figure of 42 moves. it seems to me that a lot of work was done on an algorithm for restoring the "magic domino" (the 2x3x3 puzzle), and these results were applied to stages 3 and 4. mike From tjj@lemma.helsinki.fi Wed Apr 29 05:39:47 1992 Return-Path: Received: from funet.fi by life.ai.mit.edu (4.1/AI-4.10) id AA08033; Wed, 29 Apr 92 05:39:47 EDT Received: from lemma.Helsinki.FI by funet.fi with SMTP (PP) id <07580-0@funet.fi>; Wed, 29 Apr 1992 12:38:37 +0300 Received: by lemma.helsinki.fi (5.57/Ultrix3.0-C) id AA20924; Wed, 29 Apr 92 12:38:45 +0300 Date: Wed, 29 Apr 92 12:38:45 +0300 From: tjj@lemma.helsinki.fi (Timo Jokitalo) Message-Id: <9204290938.AA20924@lemma.helsinki.fi> To: cube-lovers@ai.mit.edu, reid@math.berkeley.edu Subject: Re: an upper bound on god's number Do you have the article by Hans Kloosterman in emailable form? If not, where could I obtain a copy? Timo tjj@rolf.helsinki.fi From dik@cwi.nl Sun May 3 21:43:51 1992 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) id AA13983; Sun, 3 May 92 21:43:51 EDT Received: from boring.cwi.nl by charon.cwi.nl with SMTP id AA25853 (5.65b/2.10/CWI-Amsterdam); Mon, 4 May 1992 03:43:48 +0200 Received: by boring.cwi.nl id AA00557 (5.65b/2.10/CWI-Amsterdam); Mon, 4 May 1992 03:43:47 +0200 Date: Mon, 4 May 1992 03:43:47 +0200 From: Dik.Winter@cwi.nl Message-Id: <9205040143.AA00557.dik@boring.cwi.nl> To: cube-lovers@life.ai.mit.edu Subject: Are we approaching God's algorithm? Because it might interest the readers and to be ahead of Peter Beck: Saturday I received CFF (Cubism For Fun) # 28. It has an interesting article by Herbert Kociemba from Darmstadt, who describes his program to solve Rubik's Cube. He states that he has not yet encountered a configuration that required more than 21 moves. A short description follows: Basicly the program consists of two stages, based on the groups: G0: [U,D,R,L,F,B] G1: [U,D,R^2,L^2,F^2,B^2] G2: I The stages are from G0 to G1 and next from G1 to G2. Note that the first stage is the combination of the first two stages of Thistlethwaite, and the last stages combine his last two stages. His first stage can loosely be described as working in a three dimensional coordinate system where the coordinates are resp. twist, flip and permutation. He searches his way until the coordinate [0,0,0] is reached. Most important here is that he is able to find multiple ways. The second stage is similar, although he is not very clear here. He uses lookup tables, but does not tell us how large his lookup tables are. But his program runs on 1 MByte Atari ST. The heart is coded in a few lines of 68k assembly, the remainder in GFA Basic. As far as I know GFA Basic it can be interpreted, but also compiled. He does also use tree pruning. What he does is find successive solutions in stage 1 and fit solutions from stage 2. Letting the system run longer generally finds shorter solutions. His claims are on average less than 14 turns in stage 1, on average less than 10 turns in stage 2. But according to his article this is not completely deterministic, so there is no proven upperbound. Perhaps a proof can be found; I do not know. In practice he finds an upperbound of 21 moves, which is indeed far better than other algorithms do obtain. To take this in perspective here Thistlethwaites results from Singmaster's book: Stage 1 2 3 4 Proven 7 13 15 17 Anticipated 7 12 14? 17 Best Possible 7 10? 13? 15? (Are there configurations that require the maxima proven for Thistlethwaites algorithm?) Apparently the combination of stages largely reduces the number of turns required. In CFF 25 there was an article by Hans Kloosterman which did already improve on the number of moves. His stages 1 and 2 are identical to Thistlethwaites, he has a third stage that combines the 3rd and 4th stages of Thistlethwaite. He reports a proven maximum for his three stages of 7, 10 and 25 moves, so slightly better than Thistlethwaites conjectured best figures. Kociemba's algorithm appears however to be a big leap forward, although there are no proofs yet. One example: In 1981 Christoph Bandelow wrote a book where he offered a prize for the shortest sequence of moves that would flip every edge cuby and twists every corner cuby. The deadline was September 1, 1982; at that time the prize was offered for a 23 move manoeuvre. As Christoph writes: All solutions presented after the main deadline and shorter than all solutions submitted before were also proised a prize. Using his very ingeneous new search program Herbert Kociemba, Darmstadt, Germany now found: DF^2U'(B^2R^2)^2LB'D'FD^2FB^2UF'LRU^2F' for 20 moves. Kociemba himself writes about this: Our first solution had 12 moves in stage 1 and 14 moves in stage 2. In progress solutions 12+13, 12+12 and 12+11 were found. However, as soon as we introduced manoeuvres of 13 moves in stage 1, we found successively 9, 8 and at last 7 moves for stage 2. The program was stopped after treating about 3000 solutions. He further states that the first solution in general takes 95 seconds, but successive solutions take much shorter, and in general he finds one of less than 22 moves in a few hours on his 8 MHz Atari. What is clear is that one does not need the minimal solution in one stage to get the minimal overall total. dik -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland dik@cwi.nl From reid@math.berkeley.edu Mon May 4 23:38:05 1992 Return-Path: Received: from math.berkeley.edu by life.ai.mit.edu (4.1/AI-4.10) id AA16784; Mon, 4 May 92 23:38:05 EDT Received: from phnom-penh.berkeley.edu.berkeley.edu by math.berkeley.edu (4.1/1.33(math)) id AA06009; Mon, 4 May 92 20:37:54 PDT Date: Mon, 4 May 92 20:37:54 PDT From: reid@math.berkeley.edu (michael reid) Message-Id: <9205050337.AA06009@math.berkeley.edu> To: Dik.Winter@cwi.nl, cube-lovers@life.ai.mit.edu Subject: Re: Are we approaching God's algorithm? Cc: dseal@armltd.co.uk writes: > Because it might interest the readers and to be ahead of Peter Beck: > Saturday I received CFF (Cubism For Fun) # 28. > It has an interesting article by Herbert Kociemba from Darmstadt, who > describes his program to solve Rubik's Cube. He states that he has not > yet encountered a configuration that required more than 21 moves. A short > description follows: it would be nice to know how many patterns he has tested. > Basicly the program consists of two stages, based on the groups: > G0: [U,D,R,L,F,B] > G1: [U,D,R^2,L^2,F^2,B^2] > G2: I > The stages are from G0 to G1 and next from G1 to G2. Note that the first > stage is the combination of the first two stages of Thistlethwaite, and > the last stages combine his last two stages. > > His first stage can loosely be described as working in a three dimensional > coordinate system where the coordinates are resp. twist, flip and permutation. > He searches his way until the coordinate [0,0,0] is reached. Most important > here is that he is able to find multiple ways. The second stage is similar, > although he is not very clear here. > > He uses lookup tables, but does not tell us how large his lookup tables > are. But his program runs on 1 MByte Atari ST. The heart is coded in > a few lines of 68k assembly, the remainder in GFA Basic. As far as I > know GFA Basic it can be interpreted, but also compiled. He does also > use tree pruning. does he describe his method of "tree pruning"? this would seem to be the "intelligent" part of the program, i.e. recognizing when to abandon a given approach. if anyone has any insight on the tree pruning, please let me know. > What he does is find successive solutions in stage 1 and fit solutions > from stage 2. Letting the system run longer generally finds shorter > solutions. > > His claims are on average less than 14 turns in stage 1, on average less > than 10 turns in stage 2. But according to his article this is not completely > deterministic, so there is no proven upperbound. Perhaps a proof can be > found; I do not know. In practice he finds an upperbound of 21 moves, which > is indeed far better than other algorithms do obtain. it's not likely that this will lead to a proof of an effective upper bound. perhaps he can shave a few moves off the 42 obtained by kloosterman, but i wouldn't expect him to prove an upper bound anywhere near 21. probably the best bet for this would be to exhaustively calculate the diameter of the group G_1 (with the given generators) and the diameter of the coset space G_0 / G_1. their respective sizes are: 19508428800 and 2217093120, both of which are out of my league. i'm not belittling kociemba's program; it's a very impressive feat! > To take this in perspective here Thistlethwaites results from Singmaster's book: > Stage 1 2 3 4 > Proven 7 13 15 17 > Anticipated 7 12 14? 17 > Best Possible 7 10? 13? 15? > (Are there configurations that require the maxima proven for Thistlethwaites > algorithm?) now look what happens when people use TABs! :-} (the "Proven" line should be shifted to the left.) i believe that the diameters of the respective coset spaces are exactly those numbers listed in the "Best Possible" line. can anyone confirm this? i've finally written a few programs, and those are the diameters i get. i'm surprised that thistlethwaite didn't just do an exhaustive search on these coset spaces. perhaps it's just a matter of not having the technology when he did his work (~12 years ago). > Kociemba's algorithm appears however to be a big leap forward, although there > are no proofs yet. One example: > > In 1981 Christoph Bandelow wrote a book where he offered a prize for the > shortest sequence of moves that would flip every edge cuby and twists > every corner cuby. The deadline was September 1, 1982; at that time the > prize was offered for a 23 move manoeuvre. As Christoph writes: > All solutions presented after the main deadline and shorter than > all solutions submitted before were also proised a prize. Using > his very ingeneous new search program Herbert Kociemba, Darmstadt, > Germany now found: > DF^2U'(B^2R^2)^2LB'D'FD^2FB^2UF'LRU^2F' > for 20 moves. very nice. now how about "superflip," and also "supertwist?" these are also reasonable candidates for antipodes of "START." i know the following manuever for "supertwist" (22 face / 30 quarter turns): U F' U' (L R2 F2 B')^4 U F U' (obtained by conjugating a manuever singmaster attributes to thistlethwaite) > Kociemba himself writes about this: > Our first solution had 12 moves in stage 1 and 14 moves in stage 2. > In progress solutions 12+13, 12+12 and 12+11 were found. However, > as soon as we introduced manoeuvres of 13 moves in stage 1, we found > successively 9, 8 and at last 7 moves for stage 2. The program was > stopped after treating about 3000 solutions. > He further states that the first solution in general takes 95 seconds, but > successive solutions take much shorter, and in general he finds one of less > than 22 moves in a few hours on his 8 MHz Atari. it would also be nice to know how long this first solution usually is. from the figures i have (111207592 "different" sequences of 7 or fewer twists and 167024 "different" sequences of 6 or fewer twists WITHIN G_1) it's clear that exhaustive search is too cumbersome. thus i reiterate both my statement that the "tree pruning" algorithm is the essential part of this program, and my desire to know more about it (i.e. for implementation purposes.) > dik > -- > dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland > dik@cwi.nl thanks for the info! mike reid@math.berkeley.edu From dik@cwi.nl Tue May 5 03:58:28 1992 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) id AA19673; Tue, 5 May 92 03:58:28 EDT Received: from boring.cwi.nl by charon.cwi.nl with SMTP id AA01995 (5.65b/2.10/CWI-Amsterdam); Tue, 5 May 1992 09:57:54 +0200 Received: by boring.cwi.nl id AA01813 (5.65b/2.10/CWI-Amsterdam); Tue, 5 May 1992 09:57:53 +0200 Date: Tue, 5 May 1992 09:57:53 +0200 From: Dik.Winter@cwi.nl Message-Id: <9205050757.AA01813.dik@boring.cwi.nl> To: cube-lovers@life.ai.mit.edu, reid@math.berkeley.edu Subject: Re: Are we approaching God's algorithm? Cc: dseal@armltd.co.uk > > It has an interesting article by Herbert Kociemba from Darmstadt, who > > describes his program to solve Rubik's Cube. He states that he has not > > yet encountered a configuration that required more than 21 moves. A short > > description follows: > it would be nice to know how many patterns he has tested. He does not say how many, but his article gives nine patterns that have been published earlier in CFF for which he finds shorter answers. Also more are promised for future issues. > > His first stage can loosely be described as working in a three dimensional > > coordinate system where the coordinates are resp. twist, flip and permutation. > > He searches his way until the coordinate [0,0,0] is reached. ... > > He does also > > use tree pruning. > does he describe his method of "tree pruning"? this would seem to > be the "intelligent" part of the program, i.e. recognizing when to > abandon a given approach. if anyone has any insight on the tree > pruning, please let me know. I can give some information. What he does do is calculate in advance through the three axis of his space the minimal number of moves needed to get at [0,0,0]. This is used for tree pruning. It obviously will not prune everything (e.g. if you are at point [x,y,z] it may very well be that [x,?,?] for other points requires less moves, and similar across the y and z direction), but he tells that his pruning is very effective. I do not know how he prunes in the second case, because he does not completely describes the coordinates of his second space, but I presume pruning is done in a similar way. > it's not likely that this will lead to a proof of an effective upper > bound. perhaps he can shave a few moves off the 42 obtained by > kloosterman, but i wouldn't expect him to prove an upper bound > anywhere near 21. I think so too. Moreover, it is difficult to take in account what he found, namely that a minimal solution in the first stage does not guarantee a minimal overall solution. > i believe that the diameters of the respective coset spaces are exactly > those numbers listed in the "Best Possible" line. can anyone confirm > this? i've finally written a few programs, and those are the diameters > i get. i'm surprised that thistlethwaite didn't just do an exhaustive > search on these coset spaces. perhaps it's just a matter of not having > the technology when he did his work (~12 years ago). Well, apparently Thistlethwaite did not know that those were the diameters, otherwise I have no explanation for the question marks as they appear in Singmaster. > now how about "superflip," and also "supertwist?" I will try to contact him to see what he has to say about those. From reid@math.berkeley.edu Fri May 8 17:58:59 1992 Return-Path: Received: from math.berkeley.edu by life.ai.mit.edu (4.1/AI-4.10) id AA26323; Fri, 8 May 92 17:58:59 EDT Received: from digel.berkeley.edu.berkeley.edu by math.berkeley.edu (4.1/1.33(math)) id AA21236; Fri, 8 May 92 14:58:49 PDT Date: Fri, 8 May 92 14:58:49 PDT From: reid@math.berkeley.edu (michael reid) Message-Id: <9205082158.AA21236@math.berkeley.edu> To: Dik.Winter@cwi.nl, cube-lovers@life.ai.mit.edu Subject: Re: Are we approaching God's algorithm? Cc: dseal@armltd.co.uk > > now how about "superflip," and also "supertwist?" > I will try to contact him to see what he has to say about those. of course, these aren't exactly the patterns to test. apply your favorite quarter turn to either of these patterns, and you're one move closer to START. how do i know that we're one move closer to start? the patterns "superflip," "supertwist" and "superfliptwist" each have the following three properties: 1. the group of symmetries of the pattern acts transitively on the set of "oriented" faces of the cube. 2. the pattern commutes with the square of each face turn. 3. the pattern is NOT in the subgroup generated by the squares of face turns. now suppose that a pattern with the above properties requires N face turns to return to START. let A B C be a minimal sequence of face turns to solve this pattern, where A, B, and C are subsequences such that: A consists only of squares of face turns, B is a quarter turn of some face and C is the rest of the sequence. we can dissect the sequence into these three parts from hypothesis 3. from hypothesis 2, the sequences A B C and B C A have the same effect. finally, from hypothesis 1, the quarter twist B may as well be our favorite quarter twist. see the hoey-saxe message on "symmetry and local maxima," for a good discussion of this idea. (in the archives, cube-mail-1, 14 dec 1980) my apologies if this is obvious to everyone. on the other hand, the kociemba algorithm isn't completely symmetric. thus it may be wise for him to test 2 patterns: "super----" followed by U, and "super----" followed by R. the tradeoff is testing 2 patterns for being 1 move closer. i'd say this is probably a good trade. now to correct something misleading i posted earlier: ) i believe that the diameters of the respective coset spaces are exactly ) those numbers listed in the "Best Possible" line. can anyone confirm ) this? i've finally written a few programs, and those are the diameters ) i get. i'm surprised that thistlethwaite didn't just do an exhaustive ) search on these coset spaces. perhaps it's just a matter of not having ) the technology when he did his work (~12 years ago). oops! i don't mean to say "diameter" here! these are coset spaces, so there's no reason to suppose that (the group of automorphisms of the) graph is vertex transitive. what my programs calculated was the maximal distance from the identity coset in each of these spaces. (i am told that the graph theory term is the "eccentricity" of the given vertex.) mike From dik@cwi.nl Sat May 9 20:43:35 1992 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) id AA27274; Sat, 9 May 92 20:43:35 EDT Received: from boring.cwi.nl by charon.cwi.nl with SMTP id AA15515 (5.65b/2.10/CWI-Amsterdam); Sun, 10 May 1992 02:43:33 +0200 Received: by boring.cwi.nl id AA00802 (5.65b/2.10/CWI-Amsterdam); Sun, 10 May 1992 02:43:31 +0200 Date: Sun, 10 May 1992 02:43:31 +0200 From: Dik.Winter@cwi.nl Message-Id: <9205100043.AA00802.dik@boring.cwi.nl> To: cube-lovers@life.ai.mit.edu Subject: More on the Cube (2x2x2 in this case). Singmaster states that the diameter of the group for the 2x2x2 cube is not known. I do not know whether it has been calculated in the mean time, so I just did calculate it. The number of elements in the group is 3,674,160. (Fix one corner, the others allow every permutation and one third of all possible twists.) The diameter is 11 if we do allow half-turns, it is 14 if we do not allow half-turns. The distribution is: If we allow half-turns: 1 with 0 moves 9 with 1 moves 54 with 2 moves 321 with 3 moves 1847 with 4 moves 9992 with 5 moves 50136 with 6 moves 227536 with 7 moves 870072 with 8 moves 1887748 with 9 moves 623800 with 10 moves 2644 with 11 moves If we do not allow half-turns: 1 with 0 moves 6 with 1 moves 27 with 2 moves 120 with 3 moves 534 with 4 moves 2256 with 5 moves 8969 with 6 moves 33058 with 7 moves 114149 with 8 moves 360508 with 9 moves 930588 with 10 moves 1350852 with 11 moves 782536 with 12 moves 90280 with 13 moves 276 with 14 moves In the first case heuristics give a diameter of at least 9. We see that the majority of the configuration is within distance 9 from start. So it appears that heuristics get close to the real value. We see also that in both cases there is more than one diametrally opposite configuration. Next I will find out which those are (and if they have something in common). BTW, calculation did not take very long, only a few (<3) minutes on an FPS (i.e. an extremely fast SPARC). But as the calculations are memory bound rather than compute bound, the speed of the processor is not so very important. From reid@math.berkeley.edu Mon May 11 20:31:30 1992 Return-Path: Received: from math.berkeley.edu by life.ai.mit.edu (4.1/AI-4.10) id AA17723; Mon, 11 May 92 20:31:30 EDT Received: from jacobi.berkeley.edu.berkeley.edu by math.berkeley.edu (4.1/1.33(math)) id AA22739; Mon, 11 May 92 17:31:10 PDT Date: Mon, 11 May 92 17:31:10 PDT From: reid@math.berkeley.edu (michael reid) Message-Id: <9205120031.AA22739@math.berkeley.edu> To: Dik.Winter@cwi.nl, cube-lovers@life.ai.mit.edu Subject: Re: More on the Cube (2x2x2 in this case). > Singmaster states that the diameter of the group for the 2x2x2 cube is not > known. in his "cubic circular," issue(s) 5/6 (pages 26, 27) he gives some info about this, although it is (at least) third hand information, and therefore not necessarily reliable. > I just did calculate it. ... > If we allow half-turns: > 1 with 0 moves > 9 with 1 moves > 54 with 2 moves > 321 with 3 moves > 1847 with 4 moves > 9992 with 5 moves > 50136 with 6 moves > 227536 with 7 moves > 870072 with 8 moves > 1887748 with 9 moves > 623800 with 10 moves > 2644 with 11 moves he gives the same figures, so they are probably correct. > If we do not allow half-turns: > 1 with 0 moves > 6 with 1 moves > 27 with 2 moves > 120 with 3 moves > 534 with 4 moves > 2256 with 5 moves > 8969 with 6 moves > 33058 with 7 moves > 114149 with 8 moves > 360508 with 9 moves > 930588 with 10 moves > 1350852 with 11 moves > 782536 with 12 moves > 90280 with 13 moves > 276 with 14 moves he does not give these, but he does mention that the diameter is 14. > BTW, calculation did not take very long, only a few (<3) minutes on an FPS singmaster says that the calculation took "over 51 hours of computer time"! ouch! this was 10 years ago, though. (what's 51 hours / 3 minutes ?) the "unix news item" from which singmaster apparently got his info was included in a cube-lovers message. it's in the archives, cube-mail-3, sept 15, 1981 in a message from "ISAACS at SRI-KL". dik's results show that the corners of the 3x3x3 can be "solved" (i.e. positioned correctly with respect to one another) in 11 face (respectively 14 quarter) turns. it would be nice to know if they can be solved with respect to the centers within 11 face (respectively 14 quarter) turns. this seems likely. mike From hoey@aic.nrl.navy.mil Tue May 12 11:03:38 1992 Return-Path: Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) id AA05297; Tue, 12 May 92 11:03:38 EDT Received: by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA04073; Tue, 12 May 92 11:03:34 EDT Date: Tue, 12 May 92 11:03:34 EDT From: hoey@aic.nrl.navy.mil (Dan Hoey) Message-Id: <9205121503.AA04073@Sun0.AIC.NRL.Navy.Mil> To: Cube-Lovers@life.ai.mit.edu Cc: Dik.Winter@cwi.nl, reid@math.berkeley.edu (michael reid) Subject: Diameter of the 2^3 cube and the 3^3 corners I sent the results of a quarter-turn analysis of these puzzles to Cube-Lovers in several messages during August, 1984. I modified a program written by Karl Dahlke to get these results. I counted both positions and local maxima at every distance up to the diameter of 14 quarter-turns. In case you don't have the archives handy, here are the results: Quarter 2^3 Puzzle Corners of 3^3 Puzzle Turns Positions Local Maxima Positions Local Maxima ____________________________________________________________ 0 1 0 1 0 1 6 0 12 0 _____2___________27________0______________114___________0___ 3 120 0 924 0 4 534 0 6539 0 _____5_________2256________0____________39528___________0___ 6 8969 0 199926 114 7 33058 16 806136 600 _____8_______114149_______53__________2761740_______17916___ 9 360508 260 8656152 10200 10 930588 1460 22334112 35040 ____11______1350852____34088_________32420448______818112___ 12 782536 402260 18780864 9654240 13 90280 88636 2166720 2127264 ____14__________276______276_____________6624________6624___ The first column agrees with Dik Winter's findings. As Michael Reid surmised, the diameters of the two groups are the same. My hazy recollection is that the 2^3 program ran for a few minutes on a Vax 750, while the corners program took a couple of hours. Dan Hoey Hoey@AIC.NRL.Navy.Mil From dik@cwi.nl Tue May 12 17:47:25 1992 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) id AA21137; Tue, 12 May 92 17:47:25 EDT Received: from boring.cwi.nl by charon.cwi.nl with SMTP id AA19167 (5.65b/2.10/CWI-Amsterdam); Tue, 12 May 1992 23:46:12 +0200 Received: by boring.cwi.nl id AA06553 (5.65b/2.10/CWI-Amsterdam); Tue, 12 May 1992 23:46:11 +0200 Date: Tue, 12 May 1992 23:46:11 +0200 From: Dik.Winter@cwi.nl Message-Id: <9205122146.AA06553.dik@boring.cwi.nl> To: Cube-Lovers@life.ai.mit.edu, hoey@aic.nrl.navy.mil Subject: Re: Diameter of the 2^3 cube and the 3^3 corners Cc: reid@math.berkeley.edu > I sent the results of a quarter-turn analysis of these puzzles to > Cube-Lovers in several messages during August, 1984. I must have somewhere a printed stack of cube-lovers mailings, but I never came around to read them all. Also, my reference to Singmaster was his notes. The latest page of the latest printing states that the 2x2x2 case was still unsolved, I never have seen his additional notes. > I counted both > positions and local maxima at every distance up to the diameter of 14 > quarter-turns. After Mike Reid's question I modified my program to do the counting on the corners of the 3^3. The biggest change was that it is now able to handle that case in memory on this 32 MByte machine. I did not count local maxima (although that could be done). The quarter turn case is identical to Dan Hoey's results. If we count half turns as a single move I get the following results: 1 with 0 moves 18 with 1 moves 243 with 2 moves 2874 with 3 moves 28000 with 4 moves 205416 with 5 moves 1168516 with 6 moves 5402628 with 7 moves 20776176 with 8 moves 45391616 with 9 moves 15139616 with 10 moves 64736 with 11 moves > The first column agrees with Dik Winter's findings. As Michael Reid > surmised, the diameters of the two groups are the same. Also here the diameter is the same. > My hazy recollection is that the 2^3 program ran for a few minutes on > a Vax 750, while the corners program took a couple of hours. My calculation took slightly less than half an hour. The differences in timings we see are (I think) mostly due to memory constraints on older machines. So we see a difference between Memory bound and I/O bound. I could go to disk for storage of (intermediate) results, but even than the edges can not be handled. (980*10^9 configurations so my program would require 245 GBytes of storage. I think methods can be found to reduce this by a factor of 30-40, but it is still much too large to handle, and in that case you probably get the diameter only.) dik -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland dik@cwi.nl From dik@cwi.nl Thu May 14 19:44:27 1992 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) id AA00837; Thu, 14 May 92 19:44:27 EDT Received: from boring.cwi.nl by charon.cwi.nl with SMTP id AA08254 (5.65b/2.10/CWI-Amsterdam); Fri, 15 May 1992 01:44:25 +0200 Received: by boring.cwi.nl id AA13499 (5.65b/2.10/CWI-Amsterdam); Fri, 15 May 1992 01:44:24 +0200 Date: Fri, 15 May 1992 01:44:24 +0200 From: Dik.Winter@cwi.nl Message-Id: <9205142344.AA13499.dik@boring.cwi.nl> To: cube-lovers@life.ai.mit.edu Subject: Kociemba's algorithm I am now trying to implement Kociemba's algorithm. The initialization parts are done. To recap, it is a two stage algorithm. The first stage tries to get to the subgroup generated by [R^2,L^2,F^2,B^2,U,D], the second stages comes back to start. The first stage uses a three dimensional coordinate system: twistyness, flippancy and choosyness (where are the 4 middle slice edge cubies?). The second stage uses (I think) also a three dimensional coordinate system, all permutations: corner cubies, edge cubies not on the middle slice, slice cubies. I found the maximal distance along each coordinate as follows: stage 1: twistyness: 6 flippancy: 7 choosyness: 4 This seems not in contradiction with his 10 moves or less on average. stage 2: corners: 13 edges: 8 slice edges: 4 I think this contradicts his 14 moves or less, there are configurations that require at least 13 moves to get the corners correct. I would be surprised if only one more move is needed to get everything correct. *But* some of his best moves use a sub-optimal solution for stage 1! Now if that could be quantified... Next step is implementing the searching algorithms. dik -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland dik@cwi.nl From dik@cwi.nl Sat May 16 21:14:18 1992 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) id AA03345; Sat, 16 May 92 21:14:18 EDT Received: from boring.cwi.nl by charon.cwi.nl with SMTP id AA14373 (5.65b/2.10/CWI-Amsterdam); Sun, 17 May 1992 03:14:15 +0200 Received: by boring.cwi.nl id AA20529 (5.65b/2.10/CWI-Amsterdam); Sun, 17 May 1992 03:14:14 +0200 Date: Sun, 17 May 1992 03:14:14 +0200 From: Dik.Winter@cwi.nl Message-Id: <9205170114.AA20529.dik@boring.cwi.nl> To: cube-lovers@life.ai.mit.edu Subject: Kociemba's algorithm I have implemented it based on his description. I am not yet completely satisfied, but can give some results. Both are the best I found after a run of about 30 minutes. (The numbers are first the number of moves to get at [F^2,R^2,B^2,L^2,U,D], second the numbr of moves to complete.) Superflip: (11+10=21): F B R U^2 B^2 U' D' R^2 B' R L U F^2 L^2 D^2 B^2 D' F^2 D L^2 D Supertwist: (7+9=16): F R^2 L^2 U^2 D^2 F^2 B' R^2 U F^2 B^2 R^2 L^2 U^2 D' L^2 So clearly the supertwist is not even close to the opposite of start! Currently the program needs still a bit of hand-tuning. I am looking how I can improve that. dik -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederla