From mreid@ptc.com Sat Jan 14 17:07:00 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 AA28724; Sat, 14 Jan 95 17:07:00 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA14825; Sat, 14 Jan 95 17:05:36 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA27289; Sat, 14 Jan 1995 17:18:30 -0500 Date: Sat, 14 Jan 1995 17:18:30 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501142218.AA27289@ducie.ptc.com> To: cube-lovers@ai.mit.edu Subject: more on superflip Content-Length: 3294 recently i said: > when searching for superflip in the face turn metric, it's > sufficient to search through depth 17 in stage 1! since posting this, i've realized that we can do much better. here's my current approach. everything below refers to the face turn metric. (i have similar reductions for quarter turns, but they're not quite as good.) proposition 1. there is a minimal sequence for superflip of the form sequence_1 sequence_2 where sequence_1 is in stage 1, sequence_2 is in stage 2, and sequence_1 is at most 17f long. proof. consider the different possibilities for the length of a minimal sequence for superflip: 20f, 19f, 18f, 17f or less. in the first case, we already know a maneuver of the form. in the second case, my discussion on thursday shows that we'll have such a maneuver. in the case of 18f , we may suppose that the last face turned is U , so we'll have such a maneuver. and in the last case, we may take sequence_2 to be the empty sequence. this proves prop. 1. proposition 2. there is a minimal sequence for superflip of the form R1 sequence_1 sequence_2 where sequence_1 is in stage 1, sequence_2 is in stage 2, and sequence_1 is at most 16f long. proof. consider the maneuver given by prop. 1. by applying one of the 16 symmetries that fix the U - D axis, we may suppose that the first turn of sequence_1 is either U1, U2, R1, or R2. in the case of U1 sequence_1 sequence_2, replace this by sequence_1 sequence_2 U1, and try again. handle the cases starting with U2 and R2 similarly. we will either exhaust the stage 1 part of the sequence (which is impossible, since superflip isn't in the subgroup of stage 2) or we'll wind up with a manuever starting with R1 , as desired. this proves prop. 2. there's still some more symmetry left to exploit. proposition 3. there is a minimal sequence for superflip of one of the forms R1 F1 sequence_1 sequence_2, R1 F2 sequence_1 sequence_2, R1 F3 sequence_1 sequence_2, R1 U1 sequence_1 sequence_2, R1 U2 sequence_1 sequence_2, R1 U3 sequence_1 sequence_2, R1 L1 sequence_1 sequence_2, or R1 L3 sequence_1 sequence_2, where sequence_1 is in stage 1, sequence_2 is in stage 2, and sequence_1 is at most 15f long. proof. by applying the symmetry C_R2 if necessary, we may suppose that the second turn of the maneuver given by prop. 2 is one of F1, F2, F3, U1, U2, U3, L1, L2 or L3. this gives nine cases. in the case R1 L2 sequence_1 sequence_2, replace this by R1 sequence_1 sequence_2 L2 and try again. this proves prop. 3. i have these cases running right now, and i hope to have results soon! mike From mschoene@math.rwth-aachen.de Sat Jan 14 19:20:51 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 AA03767; Sat, 14 Jan 95 19:20:51 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rTIfA-000MP6C; Sun, 15 Jan 95 01:17 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rTIf9-00025cC; Sun, 15 Jan 95 01:17 WET Message-Id: Date: Sun, 15 Jan 95 01:17 WET From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu, ishius@ishius.com In-Reply-To: der Mouse's message of Tue, 10 Jan 1995 18:14:15 -0500 <199501102314.SAA10516@Collatz.McRCIM.McGill.EDU> Subject: Re: Difficulty of Skewb Der Mouse wrote in his e-mail message of 1995/01/10 The size of the thing is thus somewhere on the order of 500 million configurations. This is why I called it trivial next to the 3x3x3. :-) The group structure in terms of facicles, for what's-his-name to sic GAP on should he care to, derived from the following facicle labeling Of course ``what's-his-name'' couldn't resist ;-). Here are my findings about the SKEWB. The SKEWB Puzzle ================ I took the liberty to renumber the points. This makes the orbits easier recognizable. up +----------+ | 9 10 | | 27 | left | 12 11 | right back +----------+----------+----------+----------+ | 5 6 | 18 17 | 1 2 | 22 21 | | 26 | 29 | 25 | 30 | | 8 7 | 19 20 | 4 3 | 23 24 | +----------+----------+----------+----------+ | 13 14 | | 28 | | 16 15 | +----------+ down I call the 8 possible turns LUB, LUF, RUB, RUF, LDB, LDF, RDB, RDB. Here LUB denotes the turn around the corner common to the L(eft), U(p), and B(ack) faces that turns L to U, U to B, and B back to L. Those turns all have order 3, and I denote the inverses with ^-1 (at least there is no question which metric to use for the SKEWB ;-). With respect to the above numbering, the generators are the following permutations. ## corner other corners centers RUF := ( 1,11,17) ( 2,12,20)( 4,10,18)(22, 6,14) (25,27,29); RUB := ( 2,10,22) ( 1, 9,23)( 3,11,21)(17, 5,15) (25,27,30); LUF := ( 6,12,18) ( 5,11,19)( 7, 9,17)(21, 1,13) (26,27,29); LUB := ( 5, 9,21) ( 6,10,24)( 8,12,22)(18, 2,16) (26,27,30); RDF := ( 4,14,20) ( 1,15,19)( 3,13,17)( 7,11,23) (25,28,29); RDB := ( 3,15,23) ( 2,14,24)( 4,16,22)( 8,10,20) (25,28,30); LDF := ( 7,13,19) ( 6,16,20)( 8,14,18)( 4,12,24) (26,28,29); LDB := ( 8,16,24) ( 5,13,23)( 7,15,21)( 3, 9,19) (26,28,30); With r, u, and f I denote the 3 rotations of the rigid cube, which generate the full automorphism group of the cube. Here r means the rotation around the axis going through the r and l faces, turning the r face in clockwise direction. ## corners opposite centers r := ( 1, 2, 3, 4) ( 6, 5, 8, 7) (27,30,28,29) (11,22,15,20)(12,21,16,19)(10,23,14,17)( 9,24,13,18); u := ( 9,10,11,12) (16,15,14,13) (30,25,29,26) (22, 1,18, 5)(23, 4,19, 8)(21, 2,17, 6)(24, 3,20, 7); f := (17,20,19,18) (21,22,23,24) (25,28,26,27) ( 1,14, 7,12)( 2,15, 8, 9)( 3,16, 5,10)( 4,13, 6,11); Let G be the group generated by the 8 turns; G = < LUB, LUF, RUB, RUF, LDB, LDF, RDB, RDF >. Let C be the group generated by the 3 rotations; C = < r, u, f >. Obviously |C| = 24 and C ~ S_4. Let C' be the derived subgroup of C; C' = . Obviously |C'| = 12 and C' ~ A_4. Then the group CG = < C, G > is the set of all positions a puzzler could observate. 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). The group G has size 6!/2 * ((3^4*4!/2) * (3^4*4!/2) / 3^2) (and is a normal subgroup of CG, since |CG/G| = 2). Note that this implies that |C G| = 12. This is not suprising, since G obviously contains all the commutators: Comm(u,f) = LUB * RDF, Comm(r,u) = LUF * RDB, Comm(f,r) = RUB * LDF, Comm(u,f^-1) = RUF * LDB, (those are the rotations of the entire cube around the 4 diagonals), and so G must contain the derived subgroup C' of C. The numbers imply that of the 6! * 3^8 * 8! position one can obtain by taking the puzzle apart and randomly reassembling it, only ~ 0.04% are solvable. Much less than the ~ 8.3% one gets for Rubik's cube. If you choose to puzzle that way, it is certainly a lot more difficult than Rubik's cube ;-). The Structure of the SKEWB Group ================================ G has three orbits on [1..30]. Namely the six face centers F = [25..30], the odd corners C1 = [1,3..23], and the even corners C2 = [2,4..24]. C shall denote the set of all corners, i.e., the union of C1 and C2. The two orbits on the corners are the two tetrahedral sets of corners mentioned by der Mouse. Let G[F] be the operation of G on the faces centers, i.e., G[F] = G/G_F, where G_F is the stabilizer in G of the face centers (the subgroup of those elements of G that fix all face centers). Let G[C] be the operation of G on the corners, i.e., G[C] = G/G_C, where G_C is the stabilizer in G of the corners. As usual with the operation of a group on several orbits, the stabilizers are normal subgroups, and they intersect trivially. On the other hand the size of G_C is 6!/2 and the size of G_F is (3^4*4!/2 * 3^4*4!/2)/3^2. So |G|=|G_C||G_F| and we see that G is the direct product of G_C and G_F. What that means puzzle-wise is that there are no dependencies between the operations on the faces and corners. So take any achivable position x[F] of the faces and any achivable position y[C] of the corners. Then there is a position z that has simultaineously z[F] = x[F] and z[C] = y[C] (in the case of Rubik's cube this is not possible, you can flip a single edge if you ignore what happens at the corners, but you cannot combine this flip of a single edge with a trivial operation on the corners). So we can fully understand the structure of G simply by understanding the structures of G_C and G_F. Of course we can also analyse G[F] and G[C], since the isomorphism theorem tells us that G_C ~ G[F] and G_F ~ G[C]. Obviously G[F] is simply the alternating group A_6. That means we can achieve any even permutation on the center faces. This is not suprising. All 8 generators effect 3-cylces on the center faces. And with 8 3-cycles, one expects the full alternating group to pop up. G[C] has the 2 orbits C1 and C2. Clearly G[C1] and G[C2] are isomorphic. G[C1] is the wreath product of the cyclic group C_3 and the alternating group A_4. That means you can twist each corner independently and achieve any even permutation on the four corners. That you can only achieve even permutations is obvious, since all generators of G[C] permute 3 corners in a 3-cycle. So |G[C1]| = |G[C2]| = 3^4*4!/2. Now G[C] is the subdirect product of G[C1] and G[C1]. That means it is isomorphic to a subgroup of the direct product of G[C1] and G[C2]. It is a subgroup of index 9. That means |G[C]| = |G[C1]| |G[C2]| / 9 = (3^4*4!/2 * 3^4*4!/2) / 3^2. G[C] is the subgroup of G[C1] * G[C2] of those permutations where each (anti)clockwise twist of a corner in C1 is combined with a (anti)clockwise 3-cycle of corners in C2 and each (anti)clockwise twist of a corner in C2 is combined with a (anti)clockwise 3-cycle of corners in C1. This was the most surprising observation for me, so allow me to talk a little bit more about this aspect. The subdirect product G[C] is a product where we ``glue'' together a common factor group of G[C1] and G[C2]. Now this common factor group is the direct product C_3*C_3 of two cyclic groups of size 3. One of them, K say, comes from the normal subgroup C_3^4 of those elements that only twist the corners. The other, L say, comes from the alternating group A_4. Now those factor groups are glued together crosswise, that is, K of G[C1] is glued to L of G[C2], and L of G[C1] is glued to K of G[C2]. In case anybody cares, G has trivial center. This is because the central elements of G[C1] must be combined in G[C] with non-central elements of G[C2] and vice versa. And of course G[F] has trivial center. The Normal Subgroups of the SKEWB Group ======================================= I have also computed the lattice of normal subgroups of the SKEWB group. Since the group is so small, I don't need any complicated argument. G is a little bit too large to simply try 'NormalSubgroups(G);' in GAP. But G[F] and G[C] are both small enough. G[F] is almost trivial (GAP finds in a few seconds that G[F] has no proper normal subgroups). G[C] is a little bit more difficult (but it took me much longer to draw a reasonable picture, then it took GAP to compute the normal subgroups). Anyhow, allow me to first present the normal subgroups lattice of G[C1], which is of course identical to the normal subgroups lattice of G[C2]. G[C1] (972) //|\ / / | \ L1 L2 L3 K[C1] (324) \ \ | / \ \\|/ \ (108) G[C1]' \ \ V[C1] (81) \ / \ \ / \ (27) W[C1] \ \ \ \ \ \ \ \ Z[C1] (3) \ / \ / <1> Here V[C1] is elementary abelian subgroup (the vector space) of those 3^4 elements of G[C1] that only twist the corners, but do not permute them. G[C1]/V[C1] is the A_4 permuting the corners. K[C1]/V[C1] is the subgroup of G[C1]/V[C1] of the double transpositions, i.e, the elements that permute the corners in two pairs of two corners each. G[C1]' is the derived subgroup of G[C1], i.e., G[C1]/G[C1]' is the largest abelian factor group of G[C1] (b.t.w. note that the fact that G is a direct product implies that G[C1]' = G'[C1]). L1, L2, and L3 are three more normal subgroups of index 3, which I don't know how to describe easily. Z[C1] is the center of G[C1]. And now the lattice of normal subgroups of G[C]. G[C] (104976) //|\ / / | \ L1 L2 L3 K[C] (34992) \ \ | / \_ \\|/ | \ (11664) G[C]' \ \ \_ V1 V2 (8748) | \ / X \ \ X / \ \ (2916) W1 W2 \ \ / X \ \ \ |_/ \ \ \ \ / \ \ \ \ (729) W[C] \ \ \ \ \ \ \ \ \ \ \ \ Z1 Z2 (324) \ \ \ / / \_ \ X / | \ S1 S2 (108) \ \ / / \ \ / / \ X / T1 T2 (27) / / / / / / |_/ / / / / <1> S1 and S2 are the stabilizers G[C]_C1 and G[C]_C2, so the normal subgroup lattices above S1 and S2 are identical to the normal subgroup lattices of G[C1] (= G[C2]). Those two lattices over S1 and S2 share the normal subgroups over G[C]' (this is where G[C1] and G[C2] are glued together). W[C] (the intersection of W1 and W2) is the elementary abelian subgroups (the vectorspace) of those elements of G[C] that only twist the 8 corners, but do not permute them. G[C]/W[C] is the A_4*A_4 permuting the two sets of corners. G[C]' is the derived subgroup of G[C], i.e., G[C]/G[C]' is the largest abelian subgroup of G[C]. Now we get the normal subgroup lattice of G by taking the above picture twice, once below G_F (because G_F ~ G[C]), and once above G_C (because G/G_C ~ G[C]). G_______ //|\ \ LLL K \ D \ \ \ VV \ WW \\ G_F W \\ \\ //|\ \ \\ ZZ LLL K \\ SS D \ TT \ VV // WW \\ / W \\ \\ G_C \ \\ ZZ \ \\ SS \ TT \ // \_______ / <1> God's algorithm for the SKEWB ============================= The next was to compute God's algorithm for the SKEWB. G is not very large, but is is easier to use a smaller model. Let H be the subgroup generated by the 4 turns LUB, LUF, RUB, and RUF. Repeated application of the rules -> , LDB -> Comm(u,f^-1) * RUF^-1, LDF -> Comm(f,r) * RUB^-1, RDB -> Comm(r,u) * LUF^-1, RDF -> Comm(u,f) * LUB^-1, allows us to translate any process in CG to one that starts with a single rotation and continues with a process in H, i.e., it starts with a rotation and continues with a process that involves only LUB, LUF, RUB, and RUF and their inverses. Note however, that H is *not* a supplement for C in CG. This is because the intersection of H and C is not trivial. Namely H contains d^2, i.e., the rotation by 180 degree around the axis through the down face (which is fixed by H) and the up face. That means that H contains 2 solved positions, and each position of H contains to 12 positions of CG. In other word H has index 12 in CG. 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 To get the table for CG, simply multiply each number by 12. This was computed with a small C program in 200 seconds on a Pentium 90 system using approx 16 MByte of memory. Since this is my first computation of this kind, I would be glad if somebody could independently verify this table. The SuperSKEWB ============== If we do not ignore the orientation of the face centers we obtain the SuperSKEWB. This could for example be done by drawing a line over one corner and the center for each face of the cube. Mathematically I modelled the SuperSKEWB by representing each face center with a set of four numbers (instead of a single number). That pushed the total number of moved points from 30 to 48 (still pretty small). The size of the SuperSKEWB group SG is a factor 32 greater than G's size, i.e., it is (2^5*6!/2) * ((3^4*4!/2) * (3^4*4!/2) / 3^2). The size of CSG (closure of C and SG) is also a factor 32 greater than CG's size, i.e., it is 2*(2^5*6!/2) * ((3^4*4!/2) * (3^4*4!/2) / 3^2). It is easy to see that you cannot turn a face center by 90 degrees in SG. Namely the corner pieces fall into two tetrahedral sets, which are not interchanged by SG. Now a given edge of a face center will always be adjacent to corners in one of those two sets of corner pieces. Simply by looking at the generators of SG, we see that each element of SG must turn an even number of face centers. So we can turn at most five of the six face centers independently; after that the orientation of the sixth face center is determined. So there are at most 2^5 different orientations possible. Since |SG| = 2^5 |G|, we see that all 2^5 orientations are indeed achievable. The structure of SG is of course very similar to the structure of G. SG[C] is identical to G[C]. Remember that G[F] was A_6. SG[F] is a subgroup of index 2 in the wreath product 2 A_6. The index 2 is because one cannot turn a single face. Note that SG has a nontrivial center, namely the element that turns all face centers at once. Thus the lattice of normal subgroups of SG is very similar to the lattice of G. The only difference is that SG_C (and of course also SG/SG_F) has two nontrivial normal subgroups with sizes 32 and 2 (resp. with sizes 32*104976 and 2*104976). I cannot compute God's algorithm for the SuperSKEWB. Would I use the same approach that I used for the SKEWB, I would need 32 times as much memory, i.e., ~ 1/2 GByte. Does anybody have an idea how to tackle the SuperSKEWB (provided anybody cares, I certainly don't)? Have a nice day. Martin. PS: No, I don't own a SKEWB. Yes, I intent to order one. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From mreid@ptc.com Wed Jan 18 10:02:03 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 AA20530; Wed, 18 Jan 95 10:02:03 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA06914; Wed, 18 Jan 95 10:00:38 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA00811; Wed, 18 Jan 1995 10:13:45 -0500 Date: Wed, 18 Jan 1995 10:13:45 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501181513.AA00811@ducie.ptc.com> To: cube-lovers@ai.mit.edu Subject: superflip requires 20 face turns Content-Length: 3124 superflip is now known to require 20 face turns. in particular, the diameter of the cube group is at least 20 face turns (and i conjecture that it's larger). as far as i can tell, this is the first improvement to the lower bound (18f) given by a simple counting argument. in my previous two messages, i gave a proof of the fact that there is a minimal sequence for superflip in one of the following forms: R1 F1 sequence_1 sequence_2, R1 F2 sequence_1 sequence_2, R1 F3 sequence_1 sequence_2, R1 U1 sequence_1 sequence_2, R1 U2 sequence_1 sequence_2, R1 U3 sequence_1 sequence_2, R1 L1 sequence_1 sequence_2, or R1 L3 sequence_1 sequence_2, where sequence_2 is in the subgroup of stage 2 of kociemba's algorithm, and sequence_1 is at most 15f long. as of monday morning, the first six cases were completely searched, but the final two seemed to be much slower. fortunately, there is more symmetry available here (which is at least part of the reason that these cases are so slow). in the case starting with R1 L1, we have four symmetries (generated by C_R2 and C_U2) which fix the subgroup of stage 2. using these symmetries, we may suppose that the third face turn is one of U1, U2, U3, F1, F2 or F3. in the case starting with R1 L3, we again have four symmetries which fix the subgroup of stage 2. in this case, the symmetries are generated by C_R2 and reflection through the R - L plane. using these symmetries, we may suppose that the third face turn is one of U1, U2, F1 or F2. even with these reductions, the last two cases are still somewhat stubborn. finally they were completed this morning. here's a summary of what i tested: position tested: depth tested superflip R1 F1: 15f deep in stage 1 best solution found: 15 + 3 = 18f superflip R1 F2: 15f deep in stage 1 best solution found: 15 + 3 = 18f superflip R1 F3: 15f deep in stage 1 best solution found: 15 + 3 = 18f superflip R1 U1: 15f deep in stage 1 best solution found: 11 + 8 = 19f superflip R1 U2: 15f deep in stage 1 best solution found: 13 + 5 = 18f superflip R1 U3: 15f deep in stage 1 best solution found: 12 + 7 = 19f superflip R1 L1 U1: 14f deep in stage 1 best solution found: 11 + 7 = 18f superflip R1 L1 U2: 14f deep in stage 1 best solution found: 10 + 7 = 17f superflip R1 L1 U3: 14f deep in stage 1 best solution found: 11 + 7 = 18f superflip R1 L1 F1: 14f deep in stage 1 best solution found: 12 + 5 = 17f superflip R1 L1 F2: 14f deep in stage 1 best solution found: 10 + 8 = 18f superflip R1 L1 F3: 14f deep in stage 1 best solution found: 12 + 5 = 17f superflip R1 L3 U1: 14f deep in stage 1 best solution found: 14 + 3 = 17f superflip R1 L3 U2: 14f deep in stage 1 best solution found: 10 + 8 = 18f superflip R1 L3 F1: 14f deep in stage 1 best solution found: 12 + 5 = 17f superflip R1 L3 F2: 14f deep in stage 1 best solution found: 13 + 5 = 18f total run time was about 210 cpu hours (somewhat more than i'd hoped for) distributed across several machines of varying ability. mike From mreid@ptc.com Wed Jan 18 10:39:55 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 AA22619; Wed, 18 Jan 95 10:39:55 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA07119; Wed, 18 Jan 95 10:38:31 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA00837; Wed, 18 Jan 1995 10:51:39 -0500 Date: Wed, 18 Jan 1995 10:51:39 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501181551.AA00837@ducie.ptc.com> To: cube-lovers@ai.mit.edu Subject: searching for superflip in quarter turn metric Content-Length: 3083 here's my approach to searching for superflip in the quarter turn metric. i gave a maneuver of length 24q for superflip on january 10. suppose there is a maneuver of length 22q (or shorter). consider three cases: case 1. there is a minimal maneuver which contains a half-turn. case 2. no minimal maneuver contains a half-turn, but there is a minimal maneuver which contains consecutive turns of opposite faces. case 3. neither case 1 nor case 2 hold. in case 1, we may find a minimal sequence of the form sequence_1 sequence_2, where sequence_2 is at least 3q long. as in the face turn metric, we may also suppose that sequence_1 starts with one of R1 F1, R1 F2, R1 F3, R1 U1, R1 U2, R1 U3, R1 L1 U1, R1 L1 U2, R1 L1 U3, R1 L1 F1, R1 L1 F2, R1 L1 F3, R1 L3 U1, R1 L3 U2, R1 L3 F1, R1 L3 F2. furthermore, the case starting with R1 F2 may be included in the case starting with R1 F1, and similarly for other cases. thus we may suppose that sequence_1 starts with one of R1 F1, R1 F3, R1 U1, R1 U3, R1 L1 U1, R1 L1 U3, R1 L1 F1, R1 L1 F3, R1 L3 U1, R1 L3 F1. in case 2, we may find a minimal sequence of the form sequence_1 sequence_2, where sequence_2 is at least 2q long. as in case 1, we may suppose that sequence_1 starts with one of the ten sequences above. in case 3, the best we can do is 1q in stage 2. however, i claim that we can find three consecutive turns of mutual adjacent faces. otherwise, we'd have a maneuver for superflip using only the four faces F, R, B, L, (for example) which is ridiculous, because edges can't change orientation using only these turns. therefore, we may suppose that a minimal sequence starts with three consecutive turns of mutual adjacent faces. up to symmetry, there are eight cases for these turns: U1 R1 F1, U1 R1 F3, U3 R1 F1, U3 R1 F3, D1 R1 F1, D1 R1 F3, D3 R1 F1, D3 R1 F3. replace U1 R1 F1 sequence by R1 F1 sequence U1 , and similarly for the other seven cases. thus we have a minimal maneuver in the form sequence_1 sequence_2 , where sequence_2 is 1q long and sequence_1 starts with either R1 F1 or R1 F3. combining all the above cases, a maneuver for superflip in 22q or less (assuming one exists) may be found in one of the forms: R1 L1 U1 sequence_1 sequence_2, R1 L1 U3 sequence_1 sequence_2, R1 L1 F1 sequence_1 sequence_2, R1 L1 F3 sequence_1 sequence_2, R1 L3 U1 sequence_1 sequence_2, R1 L3 F1 sequence_1 sequence_2, where sequence_1 is at most 17q long, R1 U1 sequence_1 sequence_2, R1 U3 sequence_1 sequence_2, where sequence_1 is at most 18q long, R1 F1 sequence_1 sequence_2, R1 F3 sequence_1 sequence_2, where sequence_1 is at most 19q long. i don't know how feasible this is (but it sure looks formidable). to get some idea, first i'll test for 20q or less. mike From BRYAN@wvnvm.wvnet.edu Wed Jan 18 11:54:12 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA27651; Wed, 18 Jan 95 11:54:12 EST Message-Id: <9501181654.AA27651@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5427; Wed, 18 Jan 95 11:53:36 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 7576; Wed, 18 Jan 1995 11:53:35 -0500 X-Acknowledge-To: Date: Wed, 18 Jan 1995 11:53:21 EST From: "Jerry Bryan" To: Subject: Re: Re: Models for the Cube In-Reply-To: Message of 12/10/94 at 15:12:00 from , Martin.Schoenert@math.rwth-aachen.de Both the original note and the reply were rather lengthy, so I will not quote the whole thing. We were at the point where we were discussing models for cubes with edges only. Such a cube can be modeled as a set of cosets of C, or as a subset of G or of CG. We arrived at the following dialog which discussed the correspondence between the two kinds of models. On 12/10/94 at 15:12:00 Martin Schoenert said: >Jerry continued > A similar argument applies to G[E]/C[E] except that we have to fix > an edge cubie instead of a corner cubie. >Almost. But there is a tricky problem here. Again G[E] = CG[E], >so it doesn't matter whether we talk about G[E]/C[E] (as you prefer) >or about CG[E]/C[E] (as I prefer). Again we can find a supplement >for C[E] in CG[E], namely the subgroup of all elements of CG[E] >that leave a particular edge cubie fixed. Assume that we fix the >upper-right edge cubie, then this supplement is . >But this does *not* respect costs. That is take an element e of CG[E]. >Let r be its representative in , i.e., c e = r, >where c is a rotation of the entire cube. The the costs of the two >elements, viewed as elements of CG[E] is clearly the same (remember, >rotations cost nothing). But the cost of r, viewed as an element of > *with this generating system*, may be higher. Indeed, *is* higher a large percentage of the time, I think. >For example take R[E] * r[E]' (where r is the rotation of the entire >cube). In CG[E] this element has cost 1. And this element lies in >, since it fixes the upper-right edge cubie. >But the cost of this element *with respect to the generating system >L[E],D[E],F[E],B[E]* is not 1. >We can repair this by choosing a different generating system for >, for example the system >L[E],D[E],F[E],B[E],R[E]*r[E]',U[E]*u[E]'. >So in general a model for the solution up to rotations for a >certain set , is a supplement of C[] in CG[], >with a generating system that respects costs. I guess I need to understand a little more precisely what we mean by "respecting costs", but I have a question here. I was thinking about this issue of representing edges only cubes by cosets vs. representing edges only cubes as subsets of G before your note arrived, and I thought I saw a problem. 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. 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's as 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 element of 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 OCT2 16 OCT3 116,121,600 OCT4 613,312,204,800 OCT5 502,269,581,721,600 OCT6 2,009,078,326,886,400 Size of Groups with rotating vertex tips: Name Subgroup # of Elements ---- -------- ------------- OCT1 16 OCT2 256 OCT3 7,431,782,400 OCT4 157,007,924,428,800 OCT5 514,324,051,682,918,400 OCT6 8,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 exacte