, it is also the case that there are just as many positions an even distance from Start as an odd distance from Start because the parity of the distance from Start is the same as the parity of the permutation if we restrict ourselves to quarter turns. But in the computer search for God's Algorithm for edges only cubes, there were not equal numbers of positions an even distance from Start as an odd distance from Start. The computer search used the coset model G[E]/C[E], where this notation means the set of cosets of C, *not* the factor group. In and of itself, the mismatch between the number of positions at an even distance from Start and at an odd distance from Start should not pose a problem. It is not clear to me what it means to speak of the "parity" of a coset of C, and half of each coset will be even and the other half will be odd. Hence, it is not clear that a particular coset must *a priori* be an odd or even distance from Start. But if we map each coset to an element of G[E], it is meaningful to speak of the parity of the element of G[E]. And if the elements of G[E] to which we map the cosets form a subgroup, then there must be an equal number of odd and even elements in the subgroup (unless they are all even?!). If the mapping respects costs in the sense of maintaining the same distance from Start, then I don't understand how we can avoid a conflict between the equal number of even and odd permutations in the subgroup of G[E] and the unequal number of even and odd distances from Start in the coset model G[E]/C[E]. Perhaps you could clarify your generating system and its respecting of costs a bit further? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From @mail.uunet.ca:mark.longridge@canrem.com Thu Jan 19 01:02:38 1995 Return-Path: <@mail.uunet.ca:mark.longridge@canrem.com> Received: from seraph.uunet.ca (uunet.ca) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10634; Thu, 19 Jan 95 01:02:38 EST Received: from portnoy.canrem.com ([198.133.42.17]) by mail.uunet.ca with SMTP id <159428-2>; Thu, 19 Jan 1995 00:35:27 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA00872; Thu, 19 Jan 95 00:21:59 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1CA56D; Thu, 19 Jan 95 00:11:23 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Shift Invariance Recap From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.1003.5834.0C1CA56D@canrem.com> Date: Thu, 19 Jan 1995 00:08:00 -0500 Organization: CRS Online (Toronto, Ontario) Shift Invariance the Final Chapter?? ------------------------------------ 2 x Order 2 (the diagonal square element) Subgroup, order = 2 D2 F2 T2 F2 B2 T2 F2 T2 2 Swap (the single square element) Subgroup , order = 2 D2 R2 D2 R2 D2 R2 2 H (the edge square element) Subgroup , order = 2 L2 R2 B2 L2 R2 F2 12 flip (the central element) Subgroup, order = 2 R1 L1 D2 B3 L2 F2 R2 U3 D1 R3 D2 F3 B3 D3 F2 D3 R2 U3 F2 D3 Special Property: Effects all edges the same 6 Counterclockwise twist (the odd element) Subgroup, order = 3 U2 R1 U1 R1 U1 R3 U1 R3 U1 R3 U2 R1 U1 R1 U1 R3 U1 R3 U1 R3 Special Property: Effects all corners the same Martin's message about the SuperSkewb having a non-trivial centre reminded me that the SuperCube should have 3 more positions which are also shift invariant: 3x3x3 cube with 6 centre pieces rotated 90, 180 and 270 degrees, with orders 4, 2 and 4 respectively. This time all the centres are effected the same! Naturally there are 3 more positions in SG'sas well. A pity there is no "Centre All-Twist" process in any of the cube literature. -> Mark <- I'll leave a superflip process for the Magic Dodecahedron as a 'exercise for the reader' ;-) From @mail.uunet.ca:mark.longridge@canrem.com Thu Jan 19 01:33:07 1995 Return-Path: <@mail.uunet.ca:mark.longridge@canrem.com> Received: from seraph.uunet.ca (uunet.ca) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA11196; Thu, 19 Jan 95 01:33:07 EST Received: from portnoy.canrem.com ([198.133.42.17]) by mail.uunet.ca with SMTP id <159426-5>; Thu, 19 Jan 1995 00:35:26 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA00868; Thu, 19 Jan 95 00:21:57 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1CA56C; Thu, 19 Jan 95 00:11:23 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Superflip 24q From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.1002.5834.0C1CA56C@canrem.com> Date: Thu, 19 Jan 1995 00:06:00 -0500 Organization: CRS Online (Toronto, Ontario) > this just appeared today, after a lot of searching: > > R3 U2 B1 L3 F1 U3 B1 D1 F1 U1 D3, L1 D2 F3 R1 B3 D1 F3 U3 B3 U1 D3 > 24q > > mike Sm = Central Reflection i.e. for operators F1 = B3, F2 = B2, F3 = B1 L1 = R3, L2 = R2, L3 = R1 U1 = D3, U2 = D2, U3 = D1 p = R3 U2 B1 L3 F1 U3 B1 D1 F1 U1 D3 (12 q) Then p + (p * Sm) = Superflip This is Mike's process slightly patched, with the last two (commuting) cube turns swapped in position. -> Mark <- From acoles@mnsinc.com Thu Jan 19 12:55:11 1995 Return-Path:Received: from news1.mnsinc.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA18201; Thu, 19 Jan 95 12:55:11 EST Received: from localhost (mail@localhost) by news1.mnsinc.com (8.6.5/8.6.5) id MAA07610 for ; Thu, 19 Jan 1995 12:57:14 -0500 Received: from mnsnet.mnsinc.com(199.164.210.10) by news1.mnsinc.com via smap (V1.3) id sma007608; Thu Jan 19 12:57:07 1995 Received: by mnsinc.com (5.65/1.35) id AA10459; Thu, 19 Jan 95 12:54:10 -0500 Date: Thu, 19 Jan 1995 12:54:09 -0500 (EST) From: Aaron Coles To: cube-lovers@life.ai.mit.edu Subject: Masterball Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Have anyone had any experience or even heard of "Masterball". I picked this "Mind Boggling 3-D puzzle with over 350 Quadrillion possible combinations" from a store out here is Washington, DC. From dlitwin@fusion.geoworks.com Thu Jan 19 13:41:25 1995 Return-Path: Received: from quark.geoworks.com ([198.211.201.100]) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA21484; Thu, 19 Jan 95 13:41:25 EST Received: from radium.geoworks.com by quark.geoworks.com (4.1/SMI-4.0) id AA25914; Thu, 19 Jan 95 10:36:51 PST Date: Thu, 19 Jan 95 10:36:51 PST From: dlitwin@fusion.geoworks.com Message-Id: <9501191836.AA25914@quark.geoworks.com> To: Aaron Coles Cc: cube-lovers@life.ai.mit.edu In-Reply-To: Subject: Masterball Aaron Coles writes: > Have anyone had any experience or even heard of "Masterball". I picked this > "Mind Boggling 3-D puzzle with over 350 Quadrillion possible > combinations" from a store out here is Washington, DC. I've seen a bunch of them around, in all sorts of different color patterns. The two standard ones (that I bought) are black and white stripes and a rainbow colored striped one. I like the way they color the plastic instead of using stickers. Dave Litwin From mreid@ptc.com Thu Jan 19 18:30:05 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA09088; Thu, 19 Jan 95 18:30:05 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA15016; Thu, 19 Jan 95 18:28:35 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA09110; Thu, 19 Jan 1995 18:41:47 -0500 Date: Thu, 19 Jan 1995 18:41:47 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501192341.AA09110@ducie.ptc.com> To: cube-lovers@ai.mit.edu Subject: symmetric maneuvers Content-Length: 1504 mark writes > p = R3 U2 B1 L3 F1 U3 B1 D1 F1 U1 D3 (12 q) > > Then p + (p * Sm) = Superflip > > This is Mike's process slightly patched, with the last two (commuting) > cube turns swapped in position. i'm surprised this hasn't been pointed out previously. however, i would write the above as (R3 U2 B1 L3 F1 U3 B1 D1 F1 U1 D3 C_X)^2 where i use C_X for central reflection. this fits in with mark's idea of "cyclic decomposition". i've noticed that a number of minimal (or presumed to be minimal) maneuvers for pretty patterns have some symmetry. here i'll use commutator notation: [ A , B ] refers to A B A' B' also i'll use bandelow's notation for rotations of the whole cube: C_U , C_RF , C_URF , denote rotation about a face-face axis, edge-edge axis, corner-corner axis, respectively. now some patterns: anaconda: B1 R1 D3 R3 F1 B3 D1 F3 U1 D3 L1 F1 L3 U3 = [ B1 R1 D3 R3 F1 B3 D1 , C_UB ] python: D2 F3 U3 L1 F3 B1 D3 B1 U1 D3 R3 F1 U1 B2 = [ D2 F3 U3 L1 F3 B1 D3 , C_UF ] 6 x's (order 3): R2 L3 D1 F2 R3 D3 F1 B3 U1 D3 F1 L1 D2 F3 R1 L2 = [ R2 L3 D1 F2 R3 D3 F1 B3 , C_UB ] my favorite example is four twisted peaks: U3 D1 B1 R3 F1 R1 B3 L3 F3 B1 L1 F1 R3 B3 R1 F3 U3 D1 = [ U3 D1 B1 R3 F1 R1 B3 L3 F3 , C_R2 ] i'd hoped to find maneuvers for "cube within a cube" and "cube within a cube within a cube", but no such luck. mike From mreid@ptc.com Fri Jan 20 15:46:17 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA12414; Fri, 20 Jan 95 15:46:17 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA19444; Fri, 20 Jan 95 15:44:52 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA10072; Fri, 20 Jan 1995 15:58:08 -0500 Date: Fri, 20 Jan 1995 15:58:08 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501202058.AA10072@ducie.ptc.com> To: cube-lovers@ai.mit.edu Subject: superflip in quarter turn metric Content-Length: 3456 i've finished searching for superflip in 20q , and no solutions were found. thus superflip requires at least 22q , which gives a new lower bound for the diameter of the cube group in the quarter turn metric. total cpu spent on the search was 29 cpu hours. based on this, i would make a rough estimate of 2.5 to 3 months cpu time for an exhaustive search through depth 22q. this time i collected some statistics the way dik did. this should be helpful for troubleshooting. it's not foolproof, but it's a reasonable start. i will rerun the face turn search and collect the same data along the way. mike statistics follow: depth in number of times solutions stage 1 stage 2 is reached found superflip R1 L1 U1: 9q 64 33q, 31q, 29q 10q 272 11q 3728 27q 12q 26440 13q 164664 25q 14q 911112 15q 5516208 superflip R1 L1 U3: 9q 64 31q, 29q, 27q 10q 272 11q 3728 12q 26440 13q 164664 14q 911112 25q 15q 5516208 superflip R1 L1 F1: 9q 288 31q, 29q, 27q 10q 2192 11q 13496 12q 65280 13q 352056 25q, 23q 14q 1810744 15q 9753608 superflip R1 L1 F3: 9q 288 31q, 29q, 27q 10q 2192 11q 13496 12q 65280 25q 13q 352056 14q 1810744 15q 9753608 superflip R1 L3 U1: 9q 64 33q, 31q, 29q, 27q 10q 272 11q 3728 12q 26440 25q 13q 164664 14q 911112 23q 15q 5516208 superflip R1 L3 F1: 9q 288 33q, 31q, 29q 10q 2192 27q 11q 13496 25q 12q 65280 13q 352056 14q 1810744 15q 9753608 superflip R1 U1: 10q 6 32q 11q 106 28q 12q 4216 26q 13q 30318 14q 212208 15q 1414882 16q 9807890 superflip R1 U3: 10q 6 32q 11q 106 30q, 28q 12q 4216 26q 13q 30318 14q 212208 24q 15q 1414882 16q 9807890 superflip R1 F1: 10q 78 32q, 30q, 28q 11q 352 12q 5338 26q, 24q 13q 35996 14q 241230 15q 1549382 16q 10531798 17q 71358512 superflip R1 F3: 10q 78 28q 11q 352 12q 5338 26q, 24q 13q 35996 14q 241230 15q 1549382 16q 10531798 17q 71358512 From BRYAN@wvnvm.wvnet.edu Fri Jan 20 20:41:10 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA27138; Fri, 20 Jan 95 20:41:10 EST Message-Id: <9501210141.AA27138@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 0675; Fri, 20 Jan 95 17:07:06 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 0198; Fri, 20 Jan 1995 17:07:06 -0500 X-Acknowledge-To: Date: Fri, 20 Jan 1995 17:07:05 EST From: "Jerry Bryan" To: , "Cube Lovers List" Subject: Re: superflip in quarter turn metric In-Reply-To: Message of 01/20/95 at 15:58:08 from mreid@ptc.com On 01/20/95 at 15:58:08 mreid@ptc.com said: >i've finished searching for superflip in 20q , and no solutions were >found. thus superflip requires at least 22q , which gives a new lower >bound for the diameter of the cube group in the quarter turn metric. >total cpu spent on the search was 29 cpu hours. based on this, i would >make a rough estimate of 2.5 to 3 months cpu time for an exhaustive >search through depth 22q. Rats. You beat me by about a half hour. I just finished comparing Level 10 of my data base with the same Level 10 superflipped. There were no matches. I just about have Level 11 completed. This will provide interesting new information in and of itself, because previously there has only been an exhaustive search through level 10. Once I complete Level 11, I will superflip it and see what happens. The superflip is especially amenable to a "two half depth search". Normally, you would have to build one tree with Start at the root, and a second tree with X at the root, where X is the position you were testing. But a search tree with superflip at the root is identical to a search tree with Start at the root except that the superflip tree has each element superflipped as compared to the respective element of the tree with Start at the root. Hence, building the tree with Superflip at the root is quite easy once the tree with Start at the root is in hand. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From BRYAN@wvnvm.wvnet.edu Sat Jan 21 17:03:15 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA05451; Sat, 21 Jan 95 17:03:15 EST Message-Id: <9501212203.AA05451@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 3609; Sat, 21 Jan 95 12:46:20 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 3611; Sat, 21 Jan 1995 12:46:20 -0500 X-Acknowledge-To: Date: Sat, 21 Jan 1995 12:44:42 EST From: "Jerry Bryan" To: "der Mouse" Cc: "Cube Lovers List" Subject: Re: superflip in quarter turn metric In-Reply-To: Message of 01/21/95 at 09:05:55 from , mouse@Collatz.McRCIM.McGill.EDU On 01/21/95 at 09:05:55 der Mouse said: >> The superflip is especially amenable to a "two half depth search". >> Normally, you would have to build one tree with Start at the root, >> and a second tree with X at the root, where X is the position you >> were testing. But a search tree with superflip at the root is >> identical to a search tree with Start at the root except that the >> superflip tree has each element superflipped as compared to the >> respective element of the tree with Start at the root. >Isn't this equally true of any other position, except that the >conversion from a Start-rooted tree's position to an X-rooted tree's >position is more complicated than just superflipping? Just think of >your tree, instead of describing positions as "cubie in cubicle > ", as describing positions as "cubie that started in cubicle in >cubicle ". I am taking the liberty of CC'ing Cube-Lovers as well. A search tree giving distances from Start calculates d(I,IY) for all positions IY in the domain of inquiry. With an X-rooted tree, distances are of the form d(X,XZ) for all positions XZ in the domain of inquiry. In general, it is not the case that d(I,IY)=d(X,XY). Hence, we cannot simply take Z=Y, and elements of the form XY do not produce the X-rooted tree. Therefore, to perform two half-depth searches to connect I and X, you really do have to construct a standard Start-rooted tree as well as an X-rooted tree. You are looking for a position IY=XZ such that |IY|=|XZ|=|X|/2. However, in the case of the Superflip E, it is the case that d(I,IY)=d(E,EY). Hence, in order to construct an E-rooted tree, it is sufficient to calculate all elements of the form EY from your existing I-rooted tree of the form IY. >Or are you storing only M-conjugate-class representatives, and I'm >exposing my ignorance of basic group theory? :-) Yes, I am storing only M-conjugate-class representatives, but that isn't the problem (see above). However, it does make the processing a bit less trivial than I have indicated. For every Y in the Start-rooted tree, I first form EY, then {m'(EY)m}, and finally Repr{m'(EY)m}. These representatives are sorted and then compared against all the Y's (which are themselves representative elements, of course). We are looking for some V and W such that Repr{m'(IV)m}=Repr{m'(EW)m}, and this will be a "half-way" position. What I *really* want is some V such that Repr{m'(IV)m}=Repr{m'(EV)m}. It seems to me that all half way positions should be "symmetric" in this fashion, but I cannot prove it. The recent discussions by Mike Reid and Mark Longridge about the 24q superflips are suggestive in this regard. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From @uconnvm.uconn.edu:dmoews@xraysgi.ims.uconn.edu Sun Jan 22 01:25:28 1995 Return-Path: <@uconnvm.uconn.edu:dmoews@xraysgi.ims.uconn.edu> Received: from UConnVM.UConn.Edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA25252; Sun, 22 Jan 95 01:25:28 EST Received: from venus.ims.uconn.edu by UConnVM.UConn.Edu (IBM VM SMTP V2R2) with TCP; Sun, 22 Jan 95 01:25:48 EST Received: from xraysgi.ims.uconn.edu by venus.ims.uconn.edu (4.1/SMI-4.1) id AA05317; Sat, 27 Apr 02 04:47:10 EST Received: by xraysgi.ims.uconn.edu (920330.SGI/911001.SGI) for @venus.ims.uconn.edu:cube-lovers@ai.mit.edu id AA25808; Mon, 23 Jan 95 01:24:21 -0500 Date: Mon, 23 Jan 95 01:24:21 -0500 From: dmoews@xraysgi.ims.uconn.edu (David Moews) Message-Id: <9501230624.AA25808@xraysgi.ims.uconn.edu> To: cube-lovers@ai.mit.edu, dmoews@xraysgi.ims.uconn.edu Subject: Shamir's method on the superflip I can also report that the superflip requires at least 19 face turns. I got this result using Shamir's algorithm, which Mike Reid describes briefly in his message <9412162233.AA27627@ducie.ptc.com>. To repeat him: Shamir's method allows you to generate in lexicographic order all permutations st, where s and t are elements of lists S and T of permutations, respectively, while using only space proportional to the sum of the sizes of the lists. What I did was to first check that the superflip f couldn't be done in 11 or fewer face turns (easy) and to then try to solve f=stuv, where s and v have 4 face turns and t and u have 2 to 5 face turns. This is done by scanning through the (ordered) lists of all st's and all f v^(-1) u^(-1)'s and checking to see if there is a common element. Shamir's method then has to be applied to S and T and to V and T, where T is a list of permutations with 2 to 5 face turns, S is a list of permutations s with 4 face turns, and V is a list of permutations f v^(-1), where v has 4 face turns. The number of candidates for s and v can be reduced by making use of the fact that f is central, has order 2, and is invariant under conjugation by the symmetry group of the cube. The computation took 52 hours of CPU time on an SGI Crimson (R4000 50/100 MHz CPU.) More than half the CPU time is spent composing permutations and updating priority queues (see below.) Some have expressed concern that Shamir's method is a memory hog. Applying it to S and T requires a rather complicated tree of permutations in T and a priority queue of permutations in S. I used the wreath product representation of the cube group (so `permutation' is something of a misnomer,) and my memory usage was then as follows: Per element of S: 48 bytes permutation s in S (can be shared with other S's and T's) 40 bytes composition st (not absolutely necessary, but speeds things up) 16 bytes pointers internal to the queue and to an element t of T --------- 104 bytes Per element of T: 48 bytes permutation t in T (can be shared, as before) 8 bytes pointer immediately above t <=16 bytes Amortized cost of higher-up regions of the tree ---------- <=72 bytes The T tree is not altered during traversal, so if you are applying the method to S and T and V and T simultaneously you just need one T tree. All told, my memory usage was around 46M. Looking for a 20 face turn representation by this method would probably take around 59M of memory and 710 hours of CPU time (on this machine.) -- David Moews dmoews@xraysgi.ims.uconn.edu From @uconnvm.uconn.edu:dmoews@xraysgi.ims.uconn.edu Sun Jan 22 17:06:42 1995 Return-Path: <@uconnvm.uconn.edu:dmoews@xraysgi.ims.uconn.edu> Received: from UConnVM.UConn.Edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA23273; Sun, 22 Jan 95 17:06:42 EST Received: from venus.ims.uconn.edu by UConnVM.UConn.Edu (IBM VM SMTP V2R2) with TCP; Sun, 22 Jan 95 17:07:00 EST Received: from xraysgi.ims.uconn.edu by venus.ims.uconn.edu (4.1/SMI-4.1) id AA05345; Sat, 27 Apr 02 20:28:20 EST Received: by xraysgi.ims.uconn.edu (920330.SGI/911001.SGI) for @venus.ims.uconn.edu:cube-lovers@ai.mit.edu id AA27851; Mon, 23 Jan 95 17:05:33 -0500 Date: Mon, 23 Jan 95 17:05:33 -0500 From: dmoews@xraysgi.ims.uconn.edu (David Moews) Message-Id: <9501232205.AA27851@xraysgi.ims.uconn.edu> To: cube-lovers@ai.mit.edu, dmoews@xraysgi.ims.uconn.edu Subject: Symmetry reductions of the superflip As I mentioned in my last message, I used symmetries to reduce the number of candidate sequences for the superflip. Here's how: Suppose we have a sequence for the superflip that has at least 4 syllables. (Here, a syllable is a maximal sequence of commuting face turns, i.e., a maximal sequence of face turns on the same axis.) The sequence of axes in these syllables must look like (1) Z X ... X Y, (2) Z Y ... X Y, (3) X Z ... X Y, or (4) X Y ... X Y, for some distinct axes X, Y, and Z. Remember that the superflip is central, so we can cyclically permute the sequence of syllables. If doing this always results in pattern (4), we only use two axes, but this can't flip any edges; hence, we can get (1), (2) or (3). By inverting the (order 2) superflip we can change (2) to (3). Then we have (1) or (3). By applying a symmetry of the cube, we can let X, Y and Z be the FB, UD, and LR axes, respectively. We still have some of the symmetry group to work with, namely the set of the eight symmetries of the cube that fix all cube axes. If we need to, we can apply a 180-degree rotation of the cube about the UD or LR axes, which lets us restrict the first FB syllable to 9 of the 15 possibilities; then, rotating about the FB axis, we can do the same for the last UD syllable. Finally, we can reflect the cube through the plane between R and L; this lets us restrict the first LR syllable to 9 possibilities, although it expands the number of possibilities for the last UD and first FB syllables to 10 each. Some more estimated runtimes for my Shamir implementation: 20 CPU hr for a 20 qtw superflip; 190 CPU hr for a 22 qtw superflip. -- David Moews dmoews@xraysgi.ims.uconn.edu From @uconnvm.uconn.edu:dmoews@xraysgi.ims.uconn.edu Sun Jan 22 17:22:51 1995 Return-Path: <@uconnvm.uconn.edu:dmoews@xraysgi.ims.uconn.edu> Received: from UConnVM.UConn.Edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA23692; Sun, 22 Jan 95 17:22:51 EST Received: from venus.ims.uconn.edu by UConnVM.UConn.Edu (IBM VM SMTP V2R2) with TCP; Sun, 22 Jan 95 17:23:11 EST Received: from xraysgi.ims.uconn.edu by venus.ims.uconn.edu (4.1/SMI-4.1) id AA05349; Sat, 27 Apr 02 20:44:33 EST Received: by xraysgi.ims.uconn.edu (920330.SGI/911001.SGI) for @venus.ims.uconn.edu:cube-lovers@ai.mit.edu id AA27990; Mon, 23 Jan 95 17:21:46 -0500 Date: Mon, 23 Jan 95 17:21:46 -0500 From: dmoews@xraysgi.ims.uconn.edu (David Moews) Message-Id: <9501232221.AA27990@xraysgi.ims.uconn.edu> To: cube-lovers@ai.mit.edu, dmoews@xraysgi.ims.uconn.edu Subject: Symmetry reductions of the superflip (oops) I forgot to say: You should cyclically permute the sequence of face turns in the superflip to begin with to ensure that the sequence does not begin and end with turns on the same axis. Only then can you be sure that you have one of the forms (1)...(4). -- David Moews dmoews@xraysgi.ims.uconn.edu From mschoene@math.rwth-aachen.de Tue Jan 24 17:15:49 1995 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10382; Tue, 24 Jan 95 17:15:49 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rWtTe-000MPHC; Tue, 24 Jan 95 23:12 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rWtTd-00025hC; Tue, 24 Jan 95 23:12 WET Message-Id: Date: Tue, 24 Jan 95 23:12 WET From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu In-Reply-To: "Jerry Bryan"'s message of Wed, 18 Jan 1995 11:53:21 EST <9501181654.AA27651@life.ai.mit.edu> Subject: Re: Re: Re: Models for the Cube Jerry Bryan wrote in his message of 1995/01/18 Perhaps you could clarify your generating system and its respecting of costs a bit further? I shall try. This is partly to clarify things for myself. So excuse me if it is a bit long and formal. The Puzzle ---------- First let me formalize what kind of puzzles we are talking about. Assume that we have a set G of *basic states* with a unique basic solved state (we may need to add further marks to distuingish all states). Assume that we have a set S of *simple operations*, such that each ~~transforms each basic state~~into another, which we write as ~~. Assume that for each simple operation~~~~there is an *inverse operation*~~~~' in S, such that if~~~~=~~then ~~' =~~. A *process* is simply a sequence ... of simple operations. It induces an operation on the set G of basic states, i.e., it again transforms each basic state into another, through the definition ( ... ) := ((...( ) ... ) ). I say that a process *solves* a basic stage

, if =

. Assume that G and S are such that for each basic state there is a process that solves

(technically this means that the group of operations on G operates transitively on the set G of basic states). The goal of the puzzle is to find such a process for each basic state. If a process solves a basic state

, then the inverse process ', that we get by reversing the sequence and replacing each simple operation by its inverse, transforms

into , and I say ' *effects*

. Finally assume that G and S are such that if processes and effect the same basic state , then they induce the same operations, i.e., then = for any other basic state in G (technically this means that the group of operations on G operates regularly on the set G of basic states). This then allows us to identify the set G of basic states and the group of operations on G. This in turn allows us to view G as a group, with the generating system S. Sometimes it is necessary to distuingish between a process, the operation it induces, and the basic state it effects. When such a distinction is unnecessary, I shall simply talk about the *element* of G. I call the group G a model for the *basic puzzle*. For an example take Rubik's cube. There are 24 * 43252003274489856000 basic states. The simple operations are the face turns (or quarter face turns if you prefer) and the rotations of the rigid cube. Obviously each state can be solved and it is easy to verify that two processes that effect the same basic state induce the same operation. The group CG is the model for the basic Rubik's cube. The Essential Puzzle -------------------- Next we need to add the notion that, while all basic elements (states) are different, some are more different than others. Assume that there is a subgroup of *essentially free elements* F. Assume that we shall consider two elements and to be *essentially equal*, if there is an essentially free element in F such that = . Then the sets of essentially equal elements are of course exactely the (left) cosets ( F). We shall call such a coset an *essential element*. Assume that we have selected for each coset ( F) a representative r( F). Define the operation '*' on the set of left cosets by ( F) * ( F) := (r( F) r( F) F), i.e., the product of two cosets is the coset containing the product of the representatives. If the set of essential elements with this operations is a group, then I call this group a model for the *essential puzzle*. Note that there is no guarantee that we can select the representatives such that '*' defines a group. That is, for some puzzles there may not be a group model for the essential puzzle. This for example happens if G = < (1,2), (1,2,3,4) > is the symmetric group on four points and F = < (1,2)(3,4) >. Furthermore there is no guarantee that each selection that gives us a group, gives us the same group. That is, for some puzzles there may be different nonisomorphic group models for the essential puzzle. This for example happens if G = < (1,2), (1,2,3,4) > and F = < (1,2), (1,2,3) > is the stabilizer of one point, in which case C4 = < (1,2,3,4) > and V4 = < (1,2)(3,4), (1,3)(2,4) > are models. But if F is a normal subgroup, then it doesn't matter how we select the representatives; the operation '*' always gives us the factor group. Also if there is a supplement E of F (i.e., a subgroup E, such that G = E F and E F = { }), then selecting the elements of E as the representatives of the cosets gives us a group model for the essential puzzle. This group model is of course isomorphic to E (but note that there can be nonisomorphic supplements). But there can be group models for the essential puzzle that come neither from the factor group nor from a supplement. This for example happens if G = < (1,2,3,4,5,6,7,8), (2,8)(3,7)(4,6) > is the dihedral group of size 16 and F = < (1,2)(3,8)(4,7)(5,6), (1,5)(2,6)(3,7)(4,8) >, in which case there are again two nonisomorphic models. For example in the case of Rubik's cube we usually consider two basic states to be equal if they are related by a rotation of the rigid cube. That is the subgroup F of essentially free elements is the subgroup C of rotations of the rigid cube in this case. The usual group model for the essential Rubik's cube is the supplement G of C. The Costs --------- Finally we need the notion of costs, both for the basic puzzle and the essential puzzle. In general let G be an arbitrary group, X a generating system for G that is closed under taking inverses (that is, for each in X, ^-1 is also in X), and Z a subgroup of G. Then roughly the cost of an element in G wrt. X and Z is the length of a shortest process effecting , where we only count the generators in X, not the terms in Z. More formally define G_(0) := Z and G_(l+1) := G_(l) (G_(l) X Z). Since X is a generating system, there is a finite d such that G = G_(d) (and the smallest such d is called the diameter of G wrt. X and Z). We say that elements which lie in G_(l) but not in G_(l-1) have *cost* l. For the basic puzzle group G, we obviously use the cost function cost_G for G wrt. the generating system S and the subgroup F. So the cost of a basic state is the length of a shortest process effecting , where we count only the simple operations ~~in S, not the elements for the essentially solved operations~~in F. Note that of course the costs of two essentially equal elements are equal. For the essential puzzle group E, we want to find a cost function cost_E that preserves this cost. That is, we want cost_E( F ) = cost_G( ). So the question is, can we choose a generating system X_E of E and a subgroup Z_E of E such that the cost function for E wrt. to X_E and Z_E has the above property. If you think about it for a moment, you will see, that we actually don't have any choice if we require cost_E( F ) = cost_G( ). Namely Z_E is simply the subgroup of E of the elements with cost 0. But if cost_E( F ) is 1, then cost_G( ) must be 1, so must be in F, and then ( F) is F, i.e., the identity of E. Likewise X_E is simply the subset of E of the elements with cost 1. But if cost_E( F ) is 1, then cost_G( ) must be 1, so must have the form , so we see that X_E must be the set { ( ~~F) |~~in F, ~~in S }. Now it turns out that those two conditions are not only necessary, they are in fact sufficient. That is, if cost_E is the cost function for E wrt. the generating system X_E = { (~~~~F) |~~in F, ~~in S } and the subgroup Z_E = { (~~F) }, then cost_E preserves the cost, i.e. cost_E( F ) = cost_G( ). So for example in the case of Rubik's cube the cost of an element of CG is the length of shortest process effecting , where we only count the face turns (or only the quarter face turns), not the rotations of the rigid cube. A model for the essential Rubik's cube is the supplement G generated by the face turns (without the rotations). Because for each process we can collect all the rotations of the rigid cube at the end of a process, we see that the set X_E is simply the set of the face turns. For another example take the edges only cube CG[E]. The cost of an element is again the length of the shortest process effecting , where we only count the face turns, not the rotations. A model for the essential edges only cube is E = (i.e., a subgroup of CG[E] that fixes one edge) (Confusion warning: running out of letters again, the first E stands for *e*ssential, the others for *e*dges). If we want the cost function for E to preserve the costs in CG[E], we must take the generating system X_E = { ( ~~F) |~~in F, ~~in S } = { L[E],D[E],F[E],B[E],r[E]'*R[E],u[E]'*U[E], L[E]', ... }. Otherwise some elements of E, will appear more expensive than they really are. Summary ------- Assume we have a puzzle modelled by a group G of basic elements with a generating system S of simple elements and their inverses. Assume that we have a subgroup F of essentially free elements, and that we call two elements essentially equal if the lie in the same left coset of F in G. Given a system of representatives for the cosets of F in G, we define the product of two cosets as the coset containing the product of the representatives of the two cosets. If this multiplication turns G/F into a group, we call this group a model for the essential puzzle. Note that such a model need not exist, i.e., it may happen that no system of representatives gives a group. Also such a model need not be unique, i.e., different systems of representatives may give nonisomorphic models. The cost of an element in G is the length of a shortest process effecting this element, where we count only the simple elements from S, not the essentially free elements from F. Then the cost of an element in G is equal to the cost of its left coset in G/F wrt. the generating system { (~~~~F) |~~in F, ~~in S }. Have a nice day. Martin. PS. I admit this more than a *bit* formal and long. Count it as my submission for the understatement-of-the-year award ;-) -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From mschoene@math.rwth-aachen.de Tue Jan 24 18:01:35 1995 Return-Path:~~Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA13203; Tue, 24 Jan 95 18:01:35 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rWuBw-000MPHC; Tue, 24 Jan 95 23:58 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rWuBw-00025hC; Tue, 24 Jan 95 23:58 WET Message-Id: Date: Tue, 24 Jan 95 23:58 WET From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu In-Reply-To: "Jerry Bryan"'s message of Wed, 18 Jan 1995 11:53:21 EST <9501181654.AA27651@life.ai.mit.edu> Subject: Re: Re: Re: Models for the Cube Jerry Bryan wrote in his message of 1995/01/18 It is well known that G[E] must have an equal number of even and odd permutations. If we generate G[E] as , it is also the case that there are just as many positions an even distance from Start as an odd distance from Start because the parity of the distance from Start is the same as the parity of the permutation if we restrict ourselves to quarter turns. If you view the elements of G[E] as permutations on 24 facelets, then all elements are even. But if you forget for the moment the orientations of the edges, and view each element as only permuting the 12 edges, then there is an equal number of even and odd elements in G[E]. And then, since each quarter face turn cyclically permutes four edges, there must indeed be just as many states an even distance from Start as there are states an odd distance from Start. Jerry continued But in the computer search for God's Algorithm for edges only cubes, there were not equal numbers of positions an even distance from Start as an odd distance from Start. The computer search used the coset model G[E]/C[E], where this notation means the set of cosets of C, *not* the factor group. In and of itself, the mismatch between the number of positions at an even distance from Start and at an odd distance from Start should not pose a problem. It is not clear to me what it means to speak of the "parity" of a coset of C, and half of each coset will be even and the other half will be odd. Hence, it is not clear that a particular coset must *a priori* be an odd or even distance from Start. Allow me to translate this into the language I introduced in my other message. G[E] is the model for the basic puzzle. C[E] is the subgroup of essentially free elements. We consider two elements of G[E] to be essentially equal if they lie in the same left coset of C[E] in G[E]. The cost of an elementof G[E] (or the distance from the Start), is the length of a shortest process effecting , where we only count the quarter face turns, not the rotations of the rigid cube. It is clear that two essentially equal elements have equal costs. Jerry continued But if we map each coset to an element of G[E], it is meaningful to speak of the parity of the element of G[E]. And if the elements of G[E] to which we map the cosets form a subgroup, then there must be an equal number of odd and even elements in the subgroup (unless they are all even?!). If the mapping respects costs in the sense of maintaining the same distance from Start, then I don't understand how we can avoid a conflict between the equal number of even and odd permutations in the subgroup of G[E] and the unequal number of even and odd distances from Start in the coset model G[E]/C[E]. Pick one edge, say the right upper edge. Then each coset of C[E] contains one representative that fixes this edge. The set of those representative is a subgroup U, generated by L[E],D[E],F[E],B[E]. Formally U is a supplement for C[E] in G[E]. It is a model for the essential edges only cube. And indeed it contains the same number of even and odd permutations. So far so good. But we must now be carefull how we measure the cost of elements in U. If we measure by taking the length of a shortest process effecting such an element in U using only the generators L[E],D[E],F[E],B[E] (and their inverses), then some elements will appear more expensive than they really are. For example r[E]'*R[E] should have cost 1, but there is no process of length 1 effecting this element using only the generators above. So we must take a larger generating system. As I described in my other message, the generating system to take is the set of all elements in U that should have cost 1. This gives us the generating system { L[E], D[E], F[E], B[E], r[E]'*R[E], u[E]'*U[E], L[E]', ... }. Still, so far so good. So where is the problem? Well the new generators r[E]'*R[E] and u[E]'*U[E] are *even* permutations. And since not all generators are odd permutations any more, the argument that the number of elements with even cost and the number of elements with odd cost must be equal, simply doesn't work anymore. Have a nice day. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From VIKING1969@delphi.com Tue Jan 24 19:56:54 1995 Return-Path:Received: from bos1h.delphi.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA19301; Tue, 24 Jan 95 19:56:54 EST Received: from delphi.com by delphi.com (PMDF V4.3-9 #7804) id <01HM8J8E9RUO8YKNT5@delphi.com>; Tue, 24 Jan 1995 19:56:39 -0500 (EST) Date: Tue, 24 Jan 1995 19:56:39 -0500 (EST) From: VIKING1969@delphi.com Subject: To: cube-lovers@life.ai.mit.edu Message-Id: <01HM8J8EA1HU8YKNT5@delphi.com> X-Vms-To: INTERNET"cube-lovers@life.ai.mit.edu" Mime-Version: 1.0 Content-Type: TEXT/PLAIN; CHARSET=US-ASCII Content-Transfer-Encoding: 7BIT unsubsribecribe list viking1969 From rodrigo@lsi.usp.br Fri Jan 27 21:05:43 1995 Return-Path: Received: from ofelia (lsi.poli.usp.br) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA23203; Fri, 27 Jan 95 21:05:43 EST Reply-To: Received: by ofelia (4.1/SMI-4.1) id AA11945; Fri, 27 Jan 95 23:55:05 EDT Date: Fri, 27 Jan 1995 23:55:04 -0200 (EDT) From: Rodrigo de Almeida Siqueira X-Sender: rodrigo@ofelia To: cube-lovers@ai.mit.edu Subject: Robot using the Cube - WWW Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Yes. We have a robot that knows how to do it! The World Wide Web page with images of the 2 robots of DAIA (Departament of Artificial Intelligence and Automation) of LSI (Laboratory of Integrated Systems) at USP (University of Sao Paulo, Brazil) is here: http://www.lsi.usp.br/usp/rod/images/cube/rubik_cube.html Of course, it's Netscape enhanced. This page has also a link to a page I made with the X-Rubik's Cube software (xrubik.html in the same address), with inlined images of the software. Have fun. Rodrigo de Almeida Siqueira Webmaster at Universidade de Sao Paulo, Brazil. personal URL (full of things): http://www.lsi.usp.br/usp/rod/rod.html From @mail.uunet.ca:mark.longridge@canrem.com Sun Jan 29 23:48:39 1995 Return-Path: <@mail.uunet.ca:mark.longridge@canrem.com> Received: from seraph.uunet.ca (uunet.ca) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA14039; Sun, 29 Jan 95 23:48:39 EST Received: from portnoy.canrem.com ([198.133.42.17]) by mail.uunet.ca with SMTP id <86674-3>; Sun, 29 Jan 1995 23:49:42 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA09640; Sun, 29 Jan 95 23:45:33 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1CC7AE; Sun, 29 Jan 95 23:41:06 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Skewb thoughts From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.1021.5834.0C1CC7AE@canrem.com> Date: Sun, 29 Jan 1995 23:40:00 -0500 Organization: CRS Online (Toronto, Ontario) Extract from Martin's very detailed skewb analysis: >Then the group CG = < C, G > is the set of all positions a puzzler >could observe. There are 24 solved position in CG (solved up to >rotations). > >The group CG has size 2 * 6!/2 * ((3^4*4!/2) * (3^4*4!/2) / 3^2) > |CG| = 75,582,720 Note that: |CG| /24 = 3,149,280 >The group G has size 6!/2 * ((3^4*4!/2) * (3^4*4!/2) / 3^2) > |G| = 37,791,360 Note that: |G| /12 = 3,149,280 The number of positions both David Singmaster and Tony Durham (the inventor) find for the skewb is 3,149,280. If we use only one tetrad of the skewb then GAP also finds this number: corners centers (each turn permutes 4) (each turn permutes 3) skewb := Group( ( 1,11,17) ( 2,12,20)( 4,10,18)(22, 6,14) (25,27,29), ( 2,10,22) ( 1, 9,23)( 3,11,21)(17, 5,15) (25,27,30), ( 4,14,20) ( 1,15,19)( 3,13,17)( 7,11,23) (25,28,29), ( 6,12,18) ( 5,11,19)( 7, 9,17)(21, 1,13) (26,27,29) );; Size (skewb); > 3149280 Mr. Singmaster had indicated in his last Cubic Circular that we may determine the skewb's orientation if only one of the tetrads are moved. By moving first one tetrad and then the other we can easily change the skewb's orientation in space. Martin finds that the diameter of the skewb is 11 moves, with perhaps 90 antipodes. The idea that the skewb has 2 positions at 0 moves is rather odd, but I think if we divide Martin's table by 2 we should get the answer for visually distinguishable states for a skewb fixed in orientation. ------------------------------------------------------------ I'm still trying to tame the dodecahedron. -> Mark <- From mreid@ptc.com Mon Jan 30 11:04:29 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA02836; Mon, 30 Jan 95 11:04:29 EST Received: from ducie by ptc.com (5.0/SMI-SVR4-NN) id AA28955; Mon, 30 Jan 95 11:03:02 EST Received: by ducie (1.38.193.4/sendmail.28-May-87) id AA15148; Mon, 30 Jan 1995 11:16:56 -0500 Date: Mon, 30 Jan 1995 11:16:56 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501301616.AA15148@ducie> To: cube-lovers@ai.mit.edu Subject: Re: superflip requires 20 face turns Content-Length: 5225 as promised, i reran the face turn search and collected data along the way. total run time was 143.7 cpu hours (just a shade under six days) on an HP 9000 series 715, 100MHz clock. so this machine is a bit faster than some of the others that helped out on the original run. (there was also some overlap between different machines.) these figures also show why the cases starting with R1 L1 and R1 L3 are so slow: many more sequences in stage 1 to check. mike statistics below: depth in number of times solutions stage 1 stage 2 is reached found superflip R1 F1: 9f 2 23f, 22f 10f 942 21f, 20f 11f 19180 12f 255716 19f 13f 2967572 14f 32053344 15f 330809868 18f superflip R1 F2: 10f 948 22f, 21f 11f 19032 20f, 19f 12f 251312 13f 2913516 14f 31351632 15f 321390912 18f superflip R1 F3: 9f 2 21f 10f 942 11f 19180 20f, 19f 12f 255716 13f 2967572 14f 32053344 15f 330809868 18f superflip R1 U1: 9f 2 21f 10f 826 11f 17140 20f, 19f 12f 231130 13f 2702062 14f 29334386 15f 303689360 superflip R1 U2: 10f 812 22f 11f 17080 21f 12f 232452 20f, 19f 13f 2735896 18f 14f 29776092 15f 307802732 superflip R1 U3: 9f 2 23f, 22f 10f 826 11f 17140 21f, 20f 12f 231130 19f 13f 2702062 14f 29334386 15f 303689360 superflip R1 L1 F1: 7f 96 20f, 19f 8f 1824 18f 9f 21768 10f 229616 11f 2267728 12f 21151120 17f 13f 189906448 14f 1660964664 superflip R1 L1 F2: 8f 384 22f, 21f, 20f 9f 8448 19f 10f 113440 18f 11f 1268896 12f 12941696 13f 124124064 14f 1141576128 superflip R1 L1 F3: 7f 96 20f, 19f 8f 1824 18f 9f 21768 10f 229616 11f 2267728 12f 21151120 17f 13f 189906448 14f 1660964664 superflip R1 L1 F3: 7f 96 20f, 19f 8f 1824 18f 9f 21768 10f 229616 11f 2267728 12f 21151120 17f 13f 189906448 14f 1660964664 superflip R1 L1 U1: 9f 832 22f, 21f, 20f 10f 16912 19f 11f 224248 18f 12f 2597672 13f 27754280 14f 279317240 superflip R1 L1 U2: 8f 384 22f, 21f, 20f 9f 8448 19f, 18f 10f 113440 17f 11f 1268896 12f 12941696 13f 124124064 14f 1141576128 superflip R1 L1 U3: 9f 832 21f, 20f 10f 16912 19f 11f 224248 18f 12f 2597672 13f 27754280 14f 279317240 superflip R1 L3 F1: 7f 96 21f, 20f, 19f 8f 1824 18f 9f 21768 10f 229616 11f 2267728 12f 21151120 17f 13f 189906448 14f 1660964664 superflip R1 L3 F2: 8f 384 22f, 21f, 20f 9f 8448 19f 10f 113440 11f 1268896 12f 12941696 13f 124124064 18f 14f 1141576128 superflip R1 L3 U1: 9f 832 23f, 22f, 21f, 19f 10f 16912 11f 224248 12f 2597672 18f 13f 27754280 14f 279317240 17f superflip R1 L3 U2: 8f 384 21f, 20f 9f 8448 19f 10f 113440 18f 11f 1268896 12f 12941696 13f 124124064 14f 1141576128 From mschoene@math.rwth-aachen.de Tue Jan 31 08:58:26 1995 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA08559; Tue, 31 Jan 95 08:58:26 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rZG32-000MP6C; Tue, 31 Jan 95 11:43 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rZG32-00025cC; Tue, 31 Jan 95 11:43 WET Message-Id: Date: Tue, 31 Jan 95 11:43 WET From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu In-Reply-To: Mark Longridge's message of Sun, 29 Jan 1995 23:40:00 -0500 <60.1021.5834.0C1CC7AE@canrem.com> Subject: Re: Skewb thoughts Mark Longridge wrote in his e-mail message of 1995/01/29 Extract from Martin's very detailed skewb analysis: >Then the group CG = < C, G > is the set of all positions a puzzler >could observe. There are 24 solved position in CG (solved up to >rotations). >The group CG has size 2 * 6!/2 * ((3^4*4!/2) * (3^4*4!/2) / 3^2) > |CG| = 75,582,720 Note that: |CG| /24 = 3,149,280 >The group G has size 6!/2 * ((3^4*4!/2) * (3^4*4!/2) / 3^2) > |G| = 37,791,360 Note that: |G| /12 = 3,149,280 The number of positions both David Singmaster and Tony Durham (the inventor) find for the skewb is 3,149,280. Right. The SKEWB has 75582720 basic states. Just as with the cube, we consider two basic states to be essential equal if the differ only by a rotation of the rigid cube. Since there are 24 rotations of the rigid cube, the SKEWB has 3149280 = 75582720/24 essential states. Mark continued If we use only one tetrad of the skewb then GAP also finds this number: ## corners centers ## (each turn permutes 4) (each turn permutes 3) skewb := Group( ( 1,11,17) ( 2,12,20)( 4,10,18)(22, 6,14) (25,27,29), ( 2,10,22) ( 1, 9,23)( 3,11,21)(17, 5,15) (25,27,30), ( 4,14,20) ( 1,15,19)( 3,13,17)( 7,11,23) (25,28,29), ( 6,12,18) ( 5,11,19)( 7, 9,17)(21, 1,13) (26,27,29) );; Size (skewb); > 3149280 In my message on the SKEWB I used the subgroup H generated by LUB, LUF, RUB, and RUF. As I noted, this subgroup has a nontrivial intersection with the subgroup C of rotations of the rigid cube. Thus it is *not* a model for the essential SKEWB. The subgroup that Mark uses, which is generated by RUF, RUB, LUF, and RDF is much better. It has trivial intersection with C and is a model for the essential SKEWB. Note however, that the corners corresponding to the four generators for this subgroups do *not* form a tetrad. They are the corner RUF and the three adjacent corners. In particular, those four generators do not fix the positions of the four corners; the generator RUF permutes the three corner cubies at RUB, LUF, and RDF. This subgroup has 7 other conjugated subgroups, corresponding to the 7 other possible choices of the first generator (the one that is adjacent to the other 3 generators). So allow me to use the subgroup H generated by RUF, LUB, RDB, and LDF. The corresponding four corners do form a tetrad. This H also has trivial intersection with C and also has size 3149280. Thus it also is a model for the essential SKEWB. Note that those four generators never change the positions of the four corner cubies. This subgroup is ``almost normal''; it has only 1 other conjugated subgroup, corresponding to the stabilizer of the other tetrad. Mark continued Mr. Singmaster had indicated in his last Cubic Circular that we may determine the skewb's orientation if only one of the tetrads are moved. I am not certain that I understand what this means. One possible interpretation is, that for each state g of the SKEWB we can easily find the rotation x of the rigid cube, such that (g x) is in the subgroup H. That means that for each state g we can easily find how to rotate the rigid cube, so that the rotated state can be solved using only the four generators above. But this is obvious. Since the four generators do not change the positions of the four corner cubies of the tetrad, the rotation x must be the one that puts those four corner cubies to their home positions. Mark continued By moving first one tetrad and then the other we can easily change the skewb's orientation in space. This comment I don't understand at all. Could you clarify it a bit? Mark continued Martin finds that the diameter of the skewb is 11 moves, with perhaps 90 antipodes. The idea that the skewb has 2 positions at 0 moves is rather odd, but I think if we divide Martin's table by 2 we should get the answer for visually distinguishable states for a skewb fixed in orientation. Right. The diameter of the SKEWB is 11 moves and there are 90 essential different antipodes. The essential SKEWB does *not* have 2 states at 0 moves, only the subgroup H which I used has 2 essentially solved states. This is not odder than the notion that the basic SKEWB has 24 essentially solved states. And yes, if you divide the numbers in my table by 2, you get the table for the essential SKEWB. I rerun the computation using the new subgroup H as a model for the essential SKEWB. Here is the output. 0 1 0 0 0 0 0 0 0 0 1 1 8 0 0 0 0 0 0 8 0 0 2 48 0 0 0 0 0 0 48 0 0 3 288 0 0 0 0 0 0 288 0 0 4 1728 0 0 0 0 0 120 1608 0 0 5 10248 0 0 0 36 377 1322 8513 0 0 6 59304 12 87 662 2217 7561 15698 33067 0 0 7 315198 4331 16897 37723 61161 76931 66997 51158 0 0 8 1225483 515249 311594 186221 115830 65096 25012 6481 0 0 9 1455856 1384909 61839 8280 708 95 25 0 0 0 10 81028 80938 90 0 0 0 0 0 0 0 11 90 90 0 0 0 0 0 0 0 0 Since the group is smaller it run faster and also used less memory. Using some additional tricks, I could cut down the time to 40 seconds and the memory needed to 2.5 megabytes. As you can see, the numbers in the first column are exactely half of the corresponding numbers in my previous message (as was expected). The numbers in the other columns are close to half of the corresponding numbers in my previous message but not exactely identical. I have to rethink what those numbers mean and how they relate to the corresponding numbers for the basic SKEWB. Have a nice day. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From mschoene@math.rwth-aachen.de Wed Feb 1 07:05:22 1995 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA22110; Wed, 1 Feb 95 07:05:22 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rZdll-000MP6C; Wed, 1 Feb 95 13:02 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rZdlk-00025cC; Wed, 1 Feb 95 13:02 WET Message-Id: Date: Wed, 1 Feb 95 13:02 WET From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu In-Reply-To: "Martin Schoenert"'s message of Tue, 24 Jan 95 23:12 WET Subject: Re: Re: Re: Re: Models for the Cube In my previous message I introduced the basic puzzle and the essential puzzle and their models. There is one more thing I would like to say about models for the cube. The situation is the same as in my previous message. Assume we have a puzzle modelled by a group G of basic elements with a generating system S of simple elements and their inverses. Assume that we have a subgroup F of essentially free elements, and that we call two elements essentially equal if the lie in the same left coset of F in G. Given a system of representatives for the cosets of F in G, we define the product of two cosets as the coset containing the product of the representatives of the two cosets. If this multiplication turns G/F into a group, we call this group a model for the essential puzzle. Note that such a model need not exist, i.e., it may happen that no system of representatives gives a group. Also such a model need not be unique, i.e., different systems of representatives may give nonisomorphic models. The cost of an element in G is the length of a shortest process effecting this element, where we count only the simple elements from S, not the essentially free elements from F. Then the cost of an element in G is equal to the cost of its left coset in G/F wrt. the generating system { ( ~~F) |~~in F, ~~in S }. The Real Puzzle --------------- Assume that we call two elements~~and in G to be *really equal* if there are essentially free elements and in F, such that = . Then the sets of really equal elements are the double cosets (F F). Obviously two really equal elements have the same costs. The set of all double cosets is usually written F\G/F. Let us call the size of F\G/F the *real size* of the puzzle. Note that each double coset (F F) is a disjoint union of single cosets of F. On the other hand let H be the largest subgroup of F such that (H F) = ( F). Then the number of single cosets in the double cosets is the index of H in F. So we see that the size of each double coset is a multiple of |F| and a divisor of |F|^2. Furthermore note that the size of the double coset (F F) is |F|, i.e., (F F) is a single coset, if and only if normalizes F, i.e., ( F) = (F ). Now in general F\G/F is notoriously badly behaved. For example the size of F\G/F is in general not a divisor of the size of G. So there is no hope that we can turn F\G/F into a group that has anything to do with G. That means that we cannot model the real puzzle with a group. But that shouldn't stop us from investigating this real puzzle. One question we can ask is, what is the real size of the puzzle? Another question might be, what are the elements that lie in small double cosets. For an example, let us again take Rubik's cube. Here we have a very nice description of when two states are really equal. This is because the premultiplication with corresponds to a recoloring of the cube and the postmultiplication with corresponds to a rotation of the cube. So two states are really equal if we can recolor and rotate one state to get the other state. This idea has come up several times in this list, for example in Jerry Bryan's message about 1152 fold symmetry (see Jerry_Bryan__1152-fold_Symmetry_and_24-fold_Symmetry of 1993/12/08). Note that we must be a little bit more careful with the real cube than with the essential cube. With the essential cube it doesn't matter whether the subgroup of essentially free elements is the subgroup C of rotations of the rigid cube or the subgroup M of rotations and reflections of the rigid cube. That is the group G generated by the face turns is a model for the essential cube in both cases, i.e., G is a supplement of C in CG and is also a supplement of M in MG. But for the essential cube it does matter which subgroup we take. Dan Hoey computed the real size of M\MG/M as 901083404981813616 (see Dan_Hoey__The_real_size_of_cube_space of 1994/11/04). He used the fact that, since the supplement G is a normal subgroup of MG, the number of double cosets in M\MG/M is equal to the number of conjugacy classes in G under the operation of M. With the same idea we can compute the real size of C\CG/C as 1802166805653080256, which is slightly less than 2*901083404981813616. Dan Hoey and Jim Saxe searched for elements such that the double coset (M M) has size 48, 96, or 192 (see Dan_Hoey__Symmetry_and_Local_Maxima_(long_message) of 1980/12/14). More precisely, they classified the elements for which the subgroup H that fixes the single coset ( M) operates transitively on the set of quarter face turns, because those elements must be local maxima (except for the identity). They found 4 double cosets of size 48, 10 double cosets of size 96, and 12 double cosets of size 196, or 72 local maxima. Have a nice day. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From BECK@vax88a.pica.army.mil Wed Feb 1 08:19:36 1995 Return-Path: Received: from VAX88A.PICA.ARMY.MIL by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA24361; Wed, 1 Feb 95 08:19:36 EST Date: Wed, 1 Feb 1995 8:19:57 -0500 (EST) From: BECK@vax40a.pica.army.mil To: cube-lovers@ai.mit.edu Message-Id: <950201081957.40400150@VAX40A.PICA.ARMY.MIL> Subject: magic jack a friend of mine sent me the following: > At a recent visit to Games People Play we saw a Magic Jack from Fun Tech. The design was similar to a Rubiks Cube. Have you seen? ANYBODY OUT THERE KNOW MORE of this puxxle ???? From GPATYK@aol.com Wed Feb 1 11:08:10 1995 Return-Path: Received: from mail04.mail.aol.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA04681; Wed, 1 Feb 95 11:08:10 EST Received: by mail04.mail.aol.com (1.37.109.11/16.2) id AA170534691; Wed, 1 Feb 1995 11:04:51 -0500 Date: Wed, 1 Feb 1995 11:04:51 -0500 From: GPATYK@aol.com Message-Id: <950201110450_10093643@aol.com> To: cube-lovers@life.ai.mit.edu Subject: cubelovers-request@ai.ai.mit.edu thank you >greg From @ibm.co.hennepin.mn.us:WF5435@CO.HENNEPIN.MN.US Thu Feb 2 13:38:26 1995 Return-Path: <@ibm.co.hennepin.mn.us:WF5435@CO.HENNEPIN.MN.US> Received: from IBM.CO.HENNEPIN.MN.US by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA27718; Thu, 2 Feb 95 13:38:26 EST Message-Id: <9502021838.AA27718@life.ai.mit.edu> Received: from CO.HENNEPIN.MN.US by IBM.CO.HENNEPIN.MN.US (IBM MVS SMTP V3R1) with BSMTP id 0229; Wed, 01 Feb 95 13:00:31 CST Date: Wed, 1 Feb 95 13:00:07 CST To: cube-lovers@life.ai.mit.edu From: SUBSCRIBE cube-lovers-request Jill Lyons From @mail.uunet.ca:mark.longridge@canrem.com Fri Feb 3 03:32:33 1995 Return-Path: <@mail.uunet.ca:mark.longridge@canrem.com> Received: from seraph.uunet.ca (uunet.ca) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA18834; Fri, 3 Feb 95 03:32:33 EST Received: from portnoy.canrem.com ([198.133.42.17]) by mail.uunet.ca with SMTP id <88129-3>; Fri, 3 Feb 1995 03:32:45 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA20793; Fri, 3 Feb 95 03:28:33 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1CD83B; Fri, 3 Feb 95 02:50:28 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: More skewb thoughts From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.1030.5834.0C1CD83B@canrem.com> Date: Fri, 3 Feb 1995 00:40:00 -0500 Organization: CRS Online (Toronto, Ontario) The following is a follow up to the discussion on the SKEWB containing quotes from messages of Martin and myself. >> The number of positions both David Singmaster and Tony Durham >> (the inventor) find for the skewb is 3,149,280. > Right. The SKEWB has 75582720 basic states. Just as with the cube, > we consider two basic states to be essential equal if the differ only > by a rotation of the rigid cube. Since there are 24 rotations of > the rigid cube, the SKEWB has 3149280 = 75582720/24 essential states. I just noticed that the number of states of the pyraminx (with vertex rotations included) also equals 75,582,720. (933,120 * 3^4) >>Mark continued >> >>If we use only one tetrad of the skewb then GAP also finds this >> number: >> >> ## corners centers >> ## (each turn permutes 4) (each turn permutes 3) >> skewb := Group( >> ( 1,11,17) ( 2,12,20)( 4,10,18)(22, 6,14) (25,27,29), >> ( 2,10,22) ( 1, 9,23)( 3,11,21)(17, 5,15) (25,27,30), >> ( 4,14,20) ( 1,15,19)( 3,13,17)( 7,11,23) (25,28,29), >> ( 6,12,18) ( 5,11,19)( 7, 9,17)(21, 1,13) (26,27,29) >> );; I'll amend 'each turn permutes 4' to 'rotates one, 3-cycles the others', although half the corners do move in some way. Also the operators are RUF, RUB, RDF and lastly LUF. The corner LDB remains fixed, so just like the 2x2x2 cube we are fixing a corner. >Note however, that the corners corresponding to the four generators for >this subgroups do *not* form a tetrad. They are the corner RUF and the >three adjacent corners. My computer Webster says that a tetrad is 'A group of four'. Perhaps there is another meaning in geometry or group theory? Certainly I agree with the 2nd statement. >Snip< I concur with the Martin's next paragraph (excuse the editing) >So allow me to use the subgroup H generated by RUF, LUB, RDB, and LDF. >The corresponding four corners do form a tetrad. Martin, could you clarify the use of tetrad here? :-) >More Snips< >> Mr. Singmaster had indicated in his last Cubic Circular that we may >> determine the skewb's orientation if only one of the tetrads are >> moved. > I am not certain that I understand what this means. >Snip< I'm going to re-read the article and think about this some more. >> By moving first one tetrad and then the other we can easily change >> the skewb's orientation in space. > This comment I don't understand at all. Could you clarify it a bit? I shall amend by comment >> above to: By moving first one half of the puzzle and then the other we can easily change the skewb's orientation in space. As stated in Douglas Hofstadter's column in the July 1982 issue of Scientific American, the skewb is a deep-cut puzzle, that is the part of the puzzle that is being operated on is no smaller than the stationary portion. -> Mark <- From BRYAN@wvnvm.wvnet.edu Sat Feb 4 12:08:24 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17871; Sat, 4 Feb 95 12:08:24 EST Message-Id: <9502041708.AA17871@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 4730; Sat, 04 Feb 95 09:25:25 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 9067; Sat, 4 Feb 1995 09:25:25 -0500 X-Acknowledge-To: Date: Sat, 4 Feb 1995 09:25:24 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Level 11, Whole Cube, Q-turns Distance X Branching {m'Xm} Branching Ratio Local from Factor Factor of Max Start Cubes to Classes 0 1 1 0 1 12 12.000 1 1.000 12.000 0 2 114 9.500 5 5.000 22.800 0 3 1,068 9.368 25 5.000 42.720 0 4 10,011 9.374 219 8.760 45.712 0 5 93,840 9.374 1,978 9.032 47.442 0 6 878,880 9.366 18,395 9.300 47.778 0 7 8,221,632 9.355 171,529 9.325 47.931 0 8 76,843,595 9.347 1,601,725 9.338 47.976 0 9 717,789,576 9.341 14,956,266 9.338 47.993 0 10 6,701,836,858 9.337 139,629,194 9.336 47.997 11 62,549,615,248 9.333 1,303,138,445 9.333 47.9992 This chart includes a column for local maxima, which my charts usually do not. With all the data kept in files instead of memory, it is not a very natural calculation to determine which positions are local maxima. With the data in memory, for any position X you would calculate the 12 neighbors Xq, and immediately determine which of the 12 neighbors were one move closer to Start. It is easy to identify local maxima in this situation. With the data written to files, the neighbors Xq are sorted before determining which are closer to Start, and there is no (easy) way to relate a given Xq back to its original X. However, let me describe the sorting/merging process in a little more detail. There is a file containing all cubes X such that |X|=n. The neighbors Xq are written to a file. The file is sorted, with duplicates deleted. (Actually, the problem is so large that there are *many* files containing the neighbors Xq. Each file is sorted, and then the results are merged). Finally, the resulting file is matched against another file containing all cubes Y such that |Y|=(n-1). Any matches are deleted, and whatever is left over becomes the file containing all cubes Z such that |Z|=(n+1). The difference between the number of matches deleted and the number of cubes in the n-1 file is the number of local maxima of length n-1. (Remember that all the X's and Y's and Z's and Xq's are representative elements of M-conjugacy classes.) The last time through this process, I generated neighbors of level 10 to create level 11, sorted and deleted duplicates, and matched against level 9 deleting matches. Hence, the last level for which I have local maxima information is level 9. There are not any local maxima through level 9. I am not really expecting any until Pons Asinorum at level 12. However, it would be nice to verify that Pons Asinorum is the shortest local maximum. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From mschoene@math.rwth-aachen.de Sun Feb 5 19:07:52 1995 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA22273; Sun, 5 Feb 95 19:07:52 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rbGx8-000MPPC; Mon, 6 Feb 95 01:05 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rbGx8-00025cC; Mon, 6 Feb 95 01:05 WET Message-Id: Date: Mon, 6 Feb 95 01:05 WET From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu In-Reply-To: Mark Longridge's message of Fri, 3 Feb 1995 00:40:00 -0500 <60.1030.5834.0C1CD83B@canrem.com> Subject: Re: More skewb thoughts Mark Longridge wrote in his e-mail message of 1995/01/29 If we use only one tetrad of the skewb then GAP also finds this number: ... shows how GAP computes the size of this subgroup as 3149280 ... I replied in my e-mail message of 1995/01/31 Note however, that the corners corresponding to the four generators for this subgroups do *not* form a tetrad. Mark Longridge replied in his e-mail message of 1995/02/03 My computer Webster says that a tetrad is 'A group of four'. Perhaps there is another meaning in geometry or group theory? Sorry for the confusion. There is no special meaning of the word ``tetrad'' that I am aware of, neither in geometry nor in group theory. I interpreted Mark's ``one tetrad of the skewb'' as ``four corners of the skewb that are the corners of a regular tetrahedron'', probably because of the common prefix ``tetra''. Note that it is problematic to interpret Mark's ``one tetrad of the skewb'' as ``one group of four corners of the skewb'', since not for all groups of four corners of the skewb the subgroup generated by the corresponding generators has size 3149280, for example the subgroup generated by the generators corresponding to the four corners of the up face, which I used in my first e-mail message, has size 6298560. All in all there are 70 different ways to select a 4-tuple of corners of the cube. Up to rotation there are 6 (essentially) different types. +------* +------* *------* +------* +------* +------* /| /| /| /| /| /| /| /| /| /| /| /| *------+ | *------* | *------* | *------* | *------* | +------* | | | | | | | | | | | | | | | | | | | | | | | | | | *----|-+ | +----|-+ | +----|-+ | *----|-+ | +----|-+ | *----|-+ |/ |/ |/ |/ |/ |/ |/ |/ |/ |/ |/ |/ +------* +------* +------+ +------+ *------+ *------+ The first type is what I proposed in my last e-mail message. The 4 corners are the corners of a regular tetrahedron. There are 2 such 4-tuples (corresponding to the 2 tetrahedrons). The subgroup generated by the corresponding generators has size 3149280, and is a model for the essential SKEWB (i.e. the SKEWB up to rotations). It leaves the 4 corners RUB, LUF, RDF, and LDB at their home positions, so it is easy to determine the orientation of an arbitrary state (in the sense that it is easy to determine how to rotate this state so that the rotated state is in the subgroup generated by RUB, LUF, RDF, and LDB). The second type is what Mark proposed in his last e-mail message. There are 8 such 4-tuples (corresponding to the 8 possible choices for the ``central'' corner RUF). The subgroup generated by the corresponding generators also has size 3149280, and is a model for the essential SKEWB. It fixes the corner LDB, so it is again easy to determine the orientation of an arbitrary state. The third type is what I proposed in my first e-mail message. There are 6 such 4-tuples (corresponding to the 6 faces). The subgroup generated by the corresponding generators has size 6298560, so it is too large by a factor of 2 to be a model for the essential SKEWB. It fixes the face center of the down face. In this case it is not easy to determine the orientation of an arbitrary state (in the sense above it is in fact impossible, because for every state there are *two* rotations such that the rotated cube is in the subgroup generated by RUB, LUB, RUF, and LUF). There are 24 4-tuples of the fourth type. The subgroup generated by the corresponding generators has size 9447840, so it is too large by a factor of 3 to be a model for the essential SKEWB. It fixes nothing. There are 24 4-tuples of the fifth type, and 6 4-tuples of the sixth type. The subgroups generated by the corresponding generators have size 37791360, so it is in fact the group G generated by all 8 generators. So if we want a model for the essential SKEWB then we have to take one of the first two types. My preference is for the first type, which I think is more special than the second. Namely there are only 2 such 4-tuples, whereas there are 8 4-tuples of the second type. Correspondingly there are only 2 such subgroups (which are both normal in the group G generated by 8 generators, though they are conjugated in the group CG generated by the 8 generators and the rotations of the rigid cube). Mark Longridge wrote in his e-mail message of 1995/01/29 By moving first one tetrad and then the other we can easily change the skewb's orientation in space. I replied in my e-mail message of 1995/01/31 This comment I don't understand at all. Could you clarify it a bit? Mark Longridge replied in his e-mail message of 1995/02/03 I shall amend by comment >> above to: By moving first one half of the puzzle and then the other we can easily change the skewb's orientation in space. I interpret that as follows. By first using an element g1 from the subgroup H1 generated by RUB, RUF, LUF, and RDF, and then an element g2 from the subgroup H2 generated by RDB, LDB, LDF, and LUB, we can acchieve *any* rotation c of the rigid cube. Now it is true that by first using an element g1 from the subgroup H1 generated by RUB, RUF, LUF, and RDF, and then an element g2 from the subgroup H2 generated by RDB, LDB, LDF, and LUB, we can acchieve any element of the group G generated by all 8 generators (this follows from the fact that |G| = |H1| |H2| / |H1 H2|). But G contains only one half of the rotations of the rigid cube. So of the 24 rotations of the rigid cube we can only achieve 12 (the even ones if we view the rotations as permutations of the 4 diagonals of the cube). This becomes obvious if you note that the 8 generators never exchange the two sets of four corners that form tetrahedrons. Mark also wrote in his e-mail message of 1995/02/03 I just noticed that the number of states of the pyraminx (with vertex rotations included) also equals 75,582,720. (933,120 * 3^4) Is this just by chance, or is there some connection between those two puzzles? Could you describe the pyraminx? Have a nice day. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From @mail.uunet.ca:mark.longridge@canrem.com Fri Feb 10 11:54:22 1995 Return-Path: <@mail.uunet.ca:mark.longridge@canrem.com> Received: from seraph.uunet.ca (uunet.ca) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA08853; Fri, 10 Feb 95 11:54:22 EST Received: from portnoy.canrem.com ([198.133.42.17]) by mail.uunet.ca with SMTP id <109773-2>; Fri, 10 Feb 1995 11:55:11 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA26149; Fri, 10 Feb 95 00:10:57 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1CF175; Fri, 10 Feb 95 00:03:07 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: The Pyraminx Lost From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.1035.5834.0C1CF175@canrem.com> Date: Thu, 9 Feb 1995 23:55:00 -0500 Organization: CRS Online (Toronto, Ontario) Subgroup Sizes of the Pyraminx Octahedron ------------------------------------------ 8 * 9 = 72 facelets (triangles) The standard Pyraminx Octahedron has 8 faces, 6 vertices, and 12 edges. It's vertices rotate. One may imagine a "Master" Pyraminx Octahedron with edge AND face rotations as well. Christoph Bandelow has a version of the Pyraminx Octahedron (I call it "Octa" for short) which has no tips. Size of Groups without rotating vertex tips: Name Subgroup # of Elements ---- -------- ------------- OCT1 4 OCT216 OCT3116,121,600 OCT4613,312,204,800 OCT5502,269,581,721,600 OCT62,009,078,326,886,400 Size of Groups with rotating vertex tips: Name Subgroup # of Elements ---- -------- ------------- OCT116 OCT2256 OCT37,431,782,400 OCT4157,007,924,428,800 OCT5514,324,051,682,918,400 OCT68,229,184,826,926,694,400 Approximately 8.2 * 10^18 ..so still less than the 3x3x3 cube The number of elements increases by a factor of 4^N for each successive group if we include the trivial vertex rotations. A Skewb Summary --------------- Without repeating Martin's results on the skewb, (which I concur with) here is a quick summary on Skewb facts: It is impossible for any face piece to turn in place 90 degrees. It is impossible to flip a single face piece 180 degrees. It is impossible to transpose 2 face pieces. The Skewb has no non-trivial centre. The SuperSkewb has non-trivial centre with all 6 face pieces rotated 180 degrees. The Mystery of the Five Pyraminxi --------------------------------- Or perhaps that should be Pyraminxes... but I can not resist comparing the Five Pyraminxes to the Five Wizards of J.R.R Tolkien, due to their mysterious nature. We are probably all familar with the Popular Pyraminx created by Uwe Meffert. What really confounds me is that Dr. Ronald Turner- Smith kepts referring to the 5 pyraminxes in ad literature and his book "The Amazing Pyraminx". The Master Pyraminx I understand, it has all the basic properties of the standard popular pyraminx plus all 6 of it's edges can rotate 180 degrees (which flips one edge, transposes 2 tips, and swaps 2 pairs of interior edge pieces) giving a total number of permutations of 446,965,972,992,000. Then there is the mysterious "Senior Pyraminx" (this is like Tolkien's Blue Wizards no one knows about). I can only speculate on the properties of the Senior Pyraminx having never read a description, and never seen the physical puzzle itself. The only fact on the Senior Pyraminx I am sure about is that it has less permutations than the Master Pyraminx. My theory is that the Senior Pyraminx has all the properties of the standard pyraminx plus it can rotate SOME of it's edges but not all 6 like the Master Pyraminx (perhaps one or two?). Perhaps Mr. Singmaster, who has seen magic solid variants from all over the world, can shed some light on the matter! -> Mark <- Email: mark.longridge@canrem.com From villa@esaii.upc.es Fri Feb 10 15:26:58 1995 Return-Path:Received: from diable.upc.es by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA22924; Fri, 10 Feb 95 15:26:58 EST Received: by diable.upc.es (4.1/SMI-4.1) id AA29541; Fri, 10 Feb 95 08:04:16 +0100 X400-Received: by /PRMD=Iris/ADMD=Mensatex/C=Es/; Relayed; Fri, 10 Feb 1995 8:04:13 UTC+0100 X400-Received: by /PRMD=es/ADMD=/C=/; Relayed; Fri, 10 Feb 1995 8:00:32 UTC+0200 Date: Fri, 10 Feb 1995 8:00:32 UTC+0200 X400-Originator: villa@esaii.upc.es X400-Recipients: non-disclosure:; X400-Content-Type: P2-1984 (2) X400-Mts-Identifier: [/PRMD=es/ADMD=/C=/;950210080032] Content-Identifier: 75 From: Ricard Villa To: cube-lovers@life.ai.mit.edu Message-Id: <75*/S=villa/OU=esaii/O=upc/PRMD=iris/ADMD=mensatex/C=es/@MHS> Mime-Version: 1.0 (Generated by Ean X.400 to MIME gateway) help From ccw@eql12.caltech.edu Fri Feb 10 19:14:16 1995 Return-Path: Received: from EQL12.Caltech.Edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA05888; Fri, 10 Feb 95 19:14:16 EST Date: Fri, 10 Feb 95 16:14:11 PST From: ccw@eql12.caltech.edu Message-Id: <950210161411.25007867@EQL12.Caltech.Edu> Subject: I have a non-standard Pyraminx. (its magic number is 5) To: cube-lovers@ai.mit.edu X-St-Vmsmail-To: ST%"cube-lovers@ai.mit.edu" It is a shallow cut Dodecahedron. Could this be one of the "Five Pyraminxes"? I don't remember what it's official name is, though I thought it was the Master Pyraminx. (I will have to check my collection at home) I only ever sow these once, in J.C Penny's, thankfully I bought one. I always viewed this as a combining of 2 puzzles, Alexander's Star and a round one, whose name escapes me at the moment. My copy of this puzzle has 2 yellow and 2 red faces. I think they ran out of colors. This means that if I am not carefull I can appear to have 2 edges switched. This is more apparant then real because the stickers for each face have ridges which can be used to make the proper choice. There are 12 faces, which can be independantly turned by 72 degrees. Faces do not move with respect to each other. There are 20 corners which can only be in Even Permutations. Corners are like the cube, trios can be spun in the same direction, pairs can be spun in opposite directions. There are 30 edges which can only be in Even Permutations. Edges can flipped in pairs, just like the normal cube. group size should be 20 30 30! 20! 3 2 --- * --- * --- * --- 2 2 3 2 Edge Corn Spin Flip for the supergroup, increase by a factor of 12 5 From mschoene@math.rwth-aachen.de Sun Feb 12 19:02:40 1995 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07507; Sun, 12 Feb 95 19:02:40 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rdoCr-000MPEC; Mon, 13 Feb 95 00:59 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rdoCq-00025cC; Mon, 13 Feb 95 00:59 WET Message-Id: Date: Mon, 13 Feb 95 00:59 WET From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu In-Reply-To: "Martin Schoenert"'s message of Tue, 31 Jan 95 11:43 WET Subject: Re: Re: Skewb thoughts I wrote in my e-mail message about the SKEWB of 1995/01/15 Here is the table for H. The first column contains the lenght. The second column contains the number of positions of that length in H. The third column contains the number of positions of that length that are local maxima, i.e., the number of positions such that for no generator the position * is longer. The fourth column contains the number of positions such that for one generator the position * is longer. And so on. So the eleventh column contains the number of positions such that for all eight generators * is longer (this happens of course only for the 2 solutions). length #pos #loc max 0 2 0 0 0 0 0 0 0 0 2 1 16 0 0 0 0 0 0 16 0 0 2 96 0 0 0 0 0 0 96 0 0 3 576 0 0 0 0 0 0 576 0 0 4 3456 0 0 0 0 0 240 3216 0 0 5 20496 0 0 0 48 729 2766 16953 0 0 6 118608 48 161 1231 4228 14779 32993 65168 0 0 7 630396 8266 33358 76349 121363 153892 137755 99413 0 0 8 2450966 1025322 621763 381098 234661 128570 47822 11730 0 0 9 2911712 2768641 126056 15344 1422 199 50 0 0 0 10 162056 161876 180 0 0 0 0 0 0 0 11 180 180 0 0 0 0 0 0 0 0 ... note that this is the H = < RUF, RUB, LUF, LUB > ... And in my e-mail message of 1995/01/31 I rerun the computation using the new subgroup H as a model for the essential SKEWB. Here is the output. 0 1 0 0 0 0 0 0 0 0 1 1 8 0 0 0 0 0 0 8 0 0 2 48 0 0 0 0 0 0 48 0 0 3 288 0 0 0 0 0 0 288 0 0 4 1728 0 0 0 0 0 120 1608 0 0 5 10248 0 0 0 36 377 1322 8513 0 0 6 59304 12 87 662 2217 7561 15698 33067 0 0 7 315198 4331 16897 37723 61161 76931 66997 51158 0 0 8 1225483 515249 311594 186221 115830 65096 25012 6481 0 0 9 1455856 1384909 61839 8280 708 95 25 0 0 0 10 81028 80938 90 0 0 0 0 0 0 0 11 90 90 0 0 0 0 0 0 0 0 As you can see, the numbers in the first column are exactely half of the corresponding numbers in my previous message (as was expected). The numbers in the other columns are close to half of the corresponding numbers in my previous message but not exactely identical. I have to rethink what those numbers mean and how they relate to the corresponding numbers for the basic SKEWB. ... note that this is now H = < RUF, LUB, RDB, LDF > ... The reason that the numbers in the other columns of the second table are not exactely half of the corresponding numbers in the first table is rather simple. They are *both wrong*. The correct numbers for H = < RUF, LUB, RDB, LDF > are as follows 0 1 0 0 0 0 0 0 0 0 1 1 8 0 0 0 0 0 0 8 0 0 2 48 0 0 0 0 0 0 48 0 0 3 288 0 0 0 0 0 0 288 0 0 4 1728 0 0 0 0 0 0 1728 0 0 5 10248 0 0 0 0 120 240 9888 0 0 6 59304 0 0 84 96 1740 6024 51360 0 0 7 315198 198 144 3600 9768 42900 94344 164244 0 0 8 1225483 15783 73016 199808 316776 343992 208584 67524 0 0 9 1455856 1001960 365792 74976 11760 1224 144 0 0 0 10 81028 80308 720 0 0 0 0 0 0 0 11 90 90 0 0 0 0 0 0 0 0 and the correct numbers for H = < RUF, LUB, RUB, LUF > are exactely twice as large. I figured out what those numbers mean. It is all rather simple. Everybody who thought about them probably knows everything that follows. I use the terms from my last few messages about models for the cube. The basic states of cost 1 are exactely the elements in (F S F), where F is the subgroup of essentially free elements, and S is the set of simple elements (the set of generators) of G. Not all those elements need to be different. Assume that there are basic states of cost 1. Each basic state has neighbors, namely the elements (F S F). The set of neighbors of each state is obviously a union of right cosets of F. Furthermore if