From @mail.uunet.ca:mark.longridge@canrem.com Mon Sep 12 01:05:56 1994 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 AA24942; Mon, 12 Sep 94 01:05:56 EDT Received: from portnoy.canrem.com ([198.133.42.251]) by mail.uunet.ca with SMTP id <101743-2>; Mon, 12 Sep 1994 01:05:58 -0400 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA20552; Mon, 12 Sep 94 01:03:01 EDT Received: by canrem.com (PCB-UUCP 1.1f) id 1AF26D; Mon, 12 Sep 94 00:48:46 -0400 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: More UR Stuff! From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.799.5834.0C1AF26D@canrem.com> Date: Mon, 12 Sep 1994 00:28:00 -0400 Organization: CRS Online (Toronto, Ontario) Notes on the UR Group --------------------- Well, some small news about the < U, R > group. Previously I believed that my 3-cycle of edges: UR1 = U3 R3 U2 R1 U1 R3 U1 R1 U1 R1 U2 R3 U3 R1 U3 R3 = 18 q, 16 h ...discovered by hand was minimal. My newly created < U, R > solver (now being at the point of churning out correct results) as happily proven me wrong! UR2 = U3 R1 U2 R1 U1 R1 U1 R2 U3 R3 U3 R2 U1 = 16 q, 13 h Also I found 6 "UR-Reflective" processes altogether. This is all there are up to and including 12 q turns: U3 R1 U1 R1 (U2) R3 U3 R3 U1 = R3 U1 R1 U1 (R2) U3 R3 U3 R1 (10) U1 R3 U3 R3 (U2) R1 U1 R1 U3 = R1 U3 R3 U3 (R2) U1 R1 U1 R3 (10) ( U2 R2 ) ^ 3 = ( R2 U2 ) ^ 3 (12) U1 R1 U2 R3 U2 R3 U2 R1 U1 = R1 U1 R2 U3 R2 U3 R2 U1 R1 (12) ( U1 R1 U3 R3 ) ^3 = ( R1 U1 R3 U3 ) ^3 (12) ( U3 R3 U1 R1 ) ^3 = ( R3 U3 R1 U1 ) ^3 (12) The program is still a sluggish beast, but I think with further refinements it should eventually find other interesting results like antipodes and pure twists, etc. -> Mark <- Email: mark.longridge@canrem.com From BRYAN@wvnvm.wvnet.edu Mon Sep 12 17:56:28 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA09587; Mon, 12 Sep 94 17:56:28 EDT Message-Id: <9409122156.AA09587@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 0953; Mon, 12 Sep 94 15:35:41 EDT Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 2448; Mon, 12 Sep 1994 15:35:41 -0400 X-Acknowledge-To: Date: Mon, 12 Sep 1994 15:35:32 EDT From: "Jerry Bryan" To: "Cube Lovers List" Subject: God's Algorithm, Q-Moves Through Level 10 Distance Number Branching Number Branching Ratio of from of Factor of Factor Cubes to Start Cubes M-Conjugate M-Conjugate Classes Classes 0 1 1 1 12 12.000 1 1.000 12.000 2 114 9.500 5 5.000 22.800 3 1,068 9.368 25 5.000 42.720 4 10,011 9.374 219 8.760 45.712 5 93,840 9.374 1,978 9.032 47.442 6 878,880 9.366 18,395 9.300 47.778 7 8,221,632 9.355 171,529 9.325 47.931 8 76,843,595 9.347 1,601,725 9.338 47.976 9 717,789,576 9.341 14,956,266 9.338 47.993 10 6,701,836,858 9.337 139,629,194 9.336 47.997 Some of you may remember previous results where I calculated equivalence classes of the form {m'Xmc} for all 48 elements m in M, the set of all cube rotations and reflections, and for all 24 elements c in C, the set of all cube rotations. This is effectively calculating M-conjugate classes for centerless cubes. My previous data bases have contained representative elements Y for each equivalent class {m'Xmc}. To get cubes with centers (where rotational orientation makes a difference), I then calculated Yc for each c in C, forming a matrix indexed by Y and c. The previous approach permits a very compact representation of God's algorithm, and I used it for corners-only cubes and am presently using it for edges-only cubes. However, I find that the {m'Xmc} approach does not work well for whole cubes. The problem is that the matrix is extremely sparse close to Start. With corners-only or edges-only cube, I can calculate the entire problem. With the whole cube, I cannot even come close to calculating the whole problem, and the matrix representation wastes space rather than saving space. Hence, for whole cubes, I am calculating equivalence classes (which are M-conjugate classes) of the form {m'Xm} for all 48 elements m in M. My data base includes a representative element Z for each M-conjugate class {m'Xm}. This reduces the size of the problem by about 48 times, and lets me calculate about two more levels of the search tree with the same level of effort as before. Just to reiterate some obvious points that have appeared before: 1) X is an arbitrary element of {m'Xm}, but Z is a particular element of {m'Xm} chosen with a selection function. 2) Z is in {m'Xm} and we have {m'Zm} = {m'Xm}. 3) |Z| = |X| = |m'Xm| = |m'Zm| for all m in M and for all X in {m'Xm}. This trivial equivalence is what makes M-conjugate classes a viable approach for brute force calculation of God's algorithm. 4) Most M-conjugate classes of the form {m'Xm} contain 48 elements. The size of {m'Xm} can be used as a measure of the symmetry of X, with |{m'Xm}|=1 for the most symmetric cubes and |{m'Xm}|=48 for the least symmetric cubes. Conversely, Symm(X) is the set of all m in M such that m'Xm=X. |Symm(X)|=48 for the most symmetric cubes, |Symm(X)|=1 for the least symmetric cubes, and |{m'Xm}| * |Symm(X)| = 48 in all cases. 5) The ratio of cubes to M-conjugate classes is close to, but not exactly equal to, 48. The reason the equality is inexact is symmetry (see item #4 above). The ratio is closer to 48 when you get further from Start because the proportion of asymmetric cubes is higher when you are further from Start. I actually calculated (and previously reported) God's Algorithm directly through level 8. For levels 9 and 10, I only calculated the number of M-equivalence classes directly. I then calculated the size of each M-equivalence class to obtain the number of cubes. This particular data base has 14 bytes for each cube (actually for each representative element Z). Hence, 14*139,629,194= 1,954,808,716 bytes are required to store level 10 (each level is in a separate file). This is about 2 gigabytes of storage, which is quite large, but which is by no means outrageous. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From BRYAN@wvnvm.wvnet.edu Wed Sep 21 11:32:38 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17783; Wed, 21 Sep 94 11:32:38 EDT Message-Id: <9409211532.AA17783@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 7073; Wed, 21 Sep 94 11:31:44 EDT Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 6772; Wed, 21 Sep 1994 11:31:44 -0400 X-Acknowledge-To: Date: Wed, 21 Sep 1994 11:31:42 EDT From: "Jerry Bryan" To: "Cube Lovers List" Subject: M-Conjugate Classes as a Group C is the set of twenty-four rotations of the cube. After much bungling (see my notes of 13 Feb 1994, 23 May 1994, and 19 July 1994), I showed that the left cosets of C, denoted by xC or {Xc}, form a group, and that the group is isomorphic to a subgroup of G. I consider this to be important because I use left cosets of C to model centerless cubes. M is the set of forty-eight rotations and reflections of the cube. I often model the cube with M-conjugate classes of the form {m'Xm}. Therefore, it seems that I should try to define an operation such that the M-conjugate classes form a group, and such that the group is isomorphic to a subgroup of G. I would like to start by reviewing briefly the results for left cosets. Two operations were defined: 1.a. {Xc} * {Yc} = {(VW)c} 1.b. V ** W = (VW) where V and W are representative elements of {Xc} and {Yc}, respectively. Further, the mapping V <--> {Vc} defines an isomorphism between the set of left cosets and the operation * on the one hand, and the set of representative elements and the operation ** on the other hand. Since the ** operation is simply normal cube multiplication and since the set of representative elements are a group under **, the set of representative elements form a subgroup of G. I tried to define groups without using representative elements and failed. Not only that, the representative elements had to be selected in a special way rather than arbitrarily. For example, we could choose as the representative element of {Xc} the unique element V such that the ur cubie is positioned properly. Positioning the ur cubie properly is not the only selection function for a representative element which will work, but any selection function must satisfy two criteria in order to work: A. It must select a representative element based on a property which is possessed by exactly one element of each coset. B. There must be closure in the sense that if V is the representative element of {Xc} and W is the representative element of {Yc}, then (VW) must be the representative element of {(VW)c}. Criterion #B merits some additional discussion. First, it is the criterion that really proves you have a group. Associativity for a subset of a group generally follows from the the associativity of the group. For a finite group, closure for a subset implies the identity and the complement for the subset, so closure is the key factor in demonstrating that a set of cubes is a group. Second, criterion #B will bear directly on our attempt to define a group operation for the M-conjugate classes. Suppose we choose not to require criterion #B. We still need to have closure in order to have a group. We could obtain closure by brute force as follows: 2.a. {Xc} * {Yc} = {(Repr{(VW)c})c} 2.b. V ** W = Repr{(VW)c} It is probably a little easier to see what is going on in equation 2.b. than in 2.a., but it is the identical mechanism in both cases. Suppose we don't have closure. That is, suppose the selection function operates in such a way that if V is the representative element of {Xc} and W is the representative element of {Yc} that (VW) is not necessarily the representative element of {(VW)c}. We can still find the representative element of {(VW)c} by simply applying the selection function, which we have done. Equations 2.a and 2.b define groups, where the left cosets are a group under * and the representative elements are a group under **. Furthermore, the mapping V <--> {Vc} defines an isomorphism between the two groups. But even though the set of representative elements is a subset of G, and even though they form a group under **, they are not a subgroup of G. The problem is that the operation ** as defined by equation 2.b. is not the same operation as standard cube multiplication as it was in equation 1.b. Now, let's look at M-conjugate classes. By analogy with the left coset case, there are two possibilities to define a group: 3.a. {m'Xm} * {m'Ym} = {m'(VW)m} 3.b. V ** W = (VW) 4.a. {m'Xm} * {m'Ym} = {m'(Repr{m'(VW)m})m} 4.b. V ** W = Repr{m'(VW)m} As before, X and Y are any cubes in G, and V and W are the representative elements of {m'Xm} and {m'Ym}, respectively. In order to make 3.a. and 3.b. work, we need some characteristic which can be used by the selection function which possesses the properties of uniqueness and closure as defined by #A and #B above. But I can't think of any such property, and I don't think such a property exists (see below). 4.a and 4.b certainly work. That is, they define operations * and ** under which the set of M-conjugate classes and the set of representative elements, respectively, form groups, and the groups are isomorphic under the mapping V <--> {m'Vm}. However, the groups fail to be subgroups of G for the same reason elements of left cosets fail to be subgroups of G under equation 2.b. Namely, the ** operation is not really the same operation as normal cube multiplication. As to the question of whether 3.a. and 3.b. can be made to work, I think we can prove that they cannot. Suppose the contrary. That is, suppose that there is some property such that it is possessed by exactly one element of each M conjugancy class and such that the normal cube product of two such elements also possesses the property. Then, it would be the case that the set of representative elements would be a subgroup of G. But the number of representative elements is the same as the number of M conjugate classes, and the number of M conjugate classes is known not to divide the number of cubes in G evenly. Hence, the set of representative elements of M-conjugate classes is not a subgroup of G. Working backwards contrapositively, the desired property cannot exist. So, the final result is that the set of M conjugate classes can be made into a group, and the set of representative elements of the M conjugate classes can be made into a group. But neither group is a subgroup of G, nor is either group isomorphic to any subgroup of G. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From BRYAN@wvnvm.wvnet.edu Wed Sep 21 18:35:37 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA13435; Wed, 21 Sep 94 18:35:37 EDT Message-Id: <9409212235.AA13435@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 8591; Wed, 21 Sep 94 16:38:18 EDT Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 4810; Wed, 21 Sep 1994 16:38:17 -0400 X-Acknowledge-To: Date: Wed, 21 Sep 1994 16:38:16 EDT From: "Jerry Bryan" To: Subject: Re: < U, R> Group In-Reply-To: Message of 08/09/94 at 01:48:00 from mark.longridge@canrem.com I wanted to get back to some of the symmetry considerations associated with the Two-Generator Group. In particular, I wanted to calculate God's Algorithm in terms of something analogous to M-conjugates. I haven't started the calculations, but I wanted to go ahead and discuss what those calculations will consist of. First, we can make the obvious observation that the group is not the only Two-Generator group. Any two adjacent faces can serve as generators for a Two-Generator Group, and there are twelve such pairs of adjacent faces. All twelve groups have identical structures, and are isomorphic under M-conjugation. With respect to any particular Two-Generator Group such as , the associated symmetry group is not M, it is a subgroup of M. Dan Hoey has determined that M has 98 subgroups, and that the 98 subgroups may be grouped into 33 classes. Dan has developed a taxonomy for the 33 classes and 98 subgroups. I have seen bits and pieces of Dan's taxonomy posted to the list, and he has sent me a good bit of it via private E-mail, but I don't think I have ever seen the whole thing all in one piece. In any case, let's talk a little bit about the 98 subgroups and 33 classes. Frey and Singmaster use script characters to describe whole cube rotations. For the purposes of this note, I will use lower case letters. For example, r will be used to describe grabbing the right face and turning the whole cube 90 degrees clockwise (to be distinguished from R, which means to turn only the right face 90 degrees clockwise). In this notation, = {i,r,rr,rrr} is one of the 98 subgroups of M. (Note that is the same group as .) Similarly, = {i,u,uu,uuu} and = {i,f,ff,fff} are subgroups of M. The groups , , and have identical structures (isomorphic under rotation), and the collection (, , ) is one of Dan's 33 classes. Similarly, (, , ) is another of Dan's 33 classes. is a subgroup of , is a subgroup of , and is a subgroup of . Dan's taxonomy includes a complete description of group-subgroup relationships within the subgroups of M, or maybe I should say that it is a complete description of class-subclass relationships. The Frey-Singmaster script notation is adequate for rotations, but it is not adequate for reflections. Instead, I will use a notation which I believe originated with Dan Hoey (e.g., 28 Dec 1993). For example, you could write r=(FUBD), where the upper case letters describe movements of whole faces (*not* quarter-turns in this context!). (FUBD) means Front goes to Up goes to Back goes to Down goes to Front, which is what happens when you perform r. In the same notation, a Front-Back reflection would be (FB), etc. With that all said, the symmetry group for is <(UR)(DL),(FB)> = {I, (FB), (UR)(DL), (FB)(UR)(DL)} In Dan's taxonomy, this group is a member of the W class, and there are six such groups -- W1 through W6. I am not sure which one this one is (I only have a list of the classes, not of the groups), but let's say for the sake of the argument it is W3. Then for , I will be calculating W3-conjugate classes of the form {w'Xw} for all w in W3. The size of the problem will be reduced by about four times, compared to a reduction of about forty-eight times for whole cube problems where M-conjugation can be used. I was initially surprised that there are twelve groups M-conjugate with , but only six corresponding symmetry groups in M. This arises, for example, because the and (diagonally opposed) groups share the same symmetry group. I really shouldn't have been surprised. After all, we know how many subgroups of G there are, namely "over three beelion" (Dan Hoey, 20 Aug 1992), and we know how many subgroups of M there are, namely 98. Since "over three beelion" is a lot more than 98, there must be many, many subgroups of G which share the same symmetry properties in the sense of sharing a subgroup of M. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From BRYAN@wvnvm.wvnet.edu Tue Sep 27 01:22:13 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10639; Tue, 27 Sep 94 01:22:13 EDT Message-Id: <9409270522.AA10639@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 7161; Mon, 26 Sep 94 14:29:38 EDT Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 3724; Mon, 26 Sep 1994 14:29:38 -0400 X-Acknowledge-To: Date: Mon, 26 Sep 1994 14:29:31 EDT From: "Jerry Bryan" To: Subject: Re: < U, R> Group (W-conjugate results) In-Reply-To: Message of 08/09/94 at 01:48:00 from mark.longridge@canrem.com I have completed the God's Algorithm calculations for the group in terms of W-conjugate classes (or really, in terms of representative elements of W-conjugate classes), with the results below. In general, the use of W-conjugates reduces the size of the problem by about four times. However, I was surprised to see that for levels 1, 3, 5, 7, 9, and 11 the number of cubes was exactly four times larger than the number of W-conjugate classes. My interpretation is that all cubes in at these levels are completely "asymmetric" with respect to W. (They are somewhat symmetric with respect to M, of course.) However, when level 13 turned out not to have a ratio of exactly 4 between cubes and W-conjugate classes, I was rescued from the task of explaining why all cubes at an odd distance from Start were asymmetric. Level W-Conjugate Branching Total Branching Ratio Classes Factor Cubes Factor of Cubes to Classes 0 1 1 1 1 1 1 4 4 4 2 3 3 10 2.5 3.333 3 6 2 24 2.4 4 4 15 2.5 58 2.416 3.866 5 35 2.333 140 2.413 4 6 85 2.429 338 2.414 3.976 7 204 2.4 816 2.414 4 8 493 2.417 1,970 2.414 3.996 9 1,189 2.412 4,756 2.414 4 10 2,863 2.408 11,448 2.407 3.999 11 6,862 2.397 27,448 2.398 4 12 16,324 2.379 65,260 2.378 3.998 13 38,550 2.362 154,192 2.363 3.9997 14 90,192 2.340 360,692 2.339 3.9992 15 206,898 2.294 827,540 2.294 3.9997 16 462,893 2.237 1,851,345 2.237 3.9996 17 992,268 2.144 3,968,840 2.144 3.9998 18 1,973,209 1.989 7,891,990 1.988 3.9996 19 3,415,314 1.731 13,659,821 1.755 3.9996 20 4,618,491 1.352 18,471,682 1.352 3.9995 21 4,147,448 0.898 16,586,822 0.898 3.9993 22 2,010,449 0.485 8,039,455 0.485 3.9988 23 378,110 0.118 1,511,110 0.188 3.9965 24 11,894 0.031 47,351 0.031 3.9811 25 27 0.002 87 0.002 3.222 Total 18,373,824 73,483,200 3.9993 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From bagleyd@source.asset.com Thu Sep 29 14:03:19 1994 Return-Path: Received: from source.asset.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA02511; Thu, 29 Sep 94 14:03:19 EDT Received: by source.asset.com (AIX 3.2/UCB 5.64/4.03) id AA25973; Thu, 29 Sep 1994 13:34:37 -0400 Date: Thu, 29 Sep 1994 13:34:37 -0400 From: bagleyd@source.asset.com (David A. Bagley) Message-Id: <9409291734.AA25973@source.asset.com> To: Cube-Lovers@ai.mit.edu Subject: X-Puzzles HI I've been busy updating X puzzles on ftp.x.org in /contrib/games/puzzles. Here's the blurb from the xpuzzle.README file there. ------------------------------- What's new?: xrubik now has a undo, save, and recall as well as self-solver (computer solves cube) up to 3x3x3. Currently it is the only one in this collection with a self-solver, undo, save, and recall. xmball recently added, atan2 problem on Suns fixed xmlink recently added, initialize error fixed xhexagons minor update The collection includes: SLIDING BLOCK PUZZLES xcubes: expanded 15 puzzle xtriangles: same complexity as 15 puzzle xhexagons: 2 modes: one ridiculously easy, one harder than 15 puzzle ROTATIONAL 3D PUZZLES hold down control key to move whole cube letters that represent colors can be changed in mono-mode xrubik: a nxnxn Erno Rubik's Cube(tm) (or Magic Cube) self-solves 2x2x2 and 3x3x3 (non-orient mode). xpyraminx: a nxnxn Uwe Meffert's Pyraminx(tm) (and Senior Pyraminx), a tetrahedron with Period 2, Period 3, and Combined cut modes and it also a sticky mode to simulate a Halpern's Tetrahedron or a Pyraminx Tetrahedron xoct: a nxnxn Uwe Meffert's Magic Octahedron (or Star Puzzler) and Trajber's Octahedron with Period 3, Period 4, and Combined cut modes and it also includes a sticky mode xskewb: a Meffert's Skewb (or Pyraminx Cube), a cube with diagonal cuts xmball: a variable cut Masterball(tm), variable number of latitudinal and longitudinal cuts on a sphere, where the longitudinal cuts permit only 180 degree turns. COMBINATION ROTATIONAL AND SLIDING 3D PUZZLES xmlink: a nxm Erno Rubik's Missing Link(tm) Future directions: Sorry about the lack of self-solvers, but I would rather write the puzzle than the tedious solution. The ability to take back moves, record moves, and start with a entered position to other puzzles besides xrubik should be done. Currently the saved file for xrubik is cryptic (not intentionally). Also xmlink and xmball need better algorithms for drawing sectors than just a series of arcs. A Billion Barrel would be nice but only with a self-solver (the puzzle is too hard (I confess, I never solved it)). Newbies (especially DOS users 8-) ): DOS/Windows & Mac users, sorry no port currently available. What you need: 80386 or better, or Risc, etc. UNIX: Linux and FreeBSD are freely available (it may work on VMS). X: XFree86 is freely available on Linux and FreeBSD distributions. gunzip: freely available from GNU and the above distributions. tar: freely available from GNU also. What you do: After transfering the PUZZLE file to your machine (DOS users may want to rename the file PUZZLE.tar.gz to PUZZLE.tgz) gunzip PUZZLE.tar.gz (or gunzip PUZZLE.tgz) tar xvf PUZZLE.tar (tar xvzf PUZZLE.tar.gz or tar xvzf PUZZLE.tgz may work as a short cut) Then read the README generated by the above command. ---------- I hope you enjoy David From ishius@ishius.com Fri Sep 30 18:16:33 1994 Return-Path: Received: from holonet.net (zen.holonet.net) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AB29180; Fri, 30 Sep 94 18:16:33 EDT Received: from DialupEudora (ishius@localhost) by holonet.net (Anton Dovydaitis) with SMTP id OAA00476; Fri, 30 Sep 1994 14:58:27 -0700 Date: Fri, 30 Sep 1994 14:58:27 -0700 Message-Id: <199409302158.OAA00476@holonet.net> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: ishius@ishius.com From: ishius@ishius.com (ishius@holonet.net) Subject: COMMERCIAL: Penrose, Cutler, Masterball COMMERCIAL POSTING September 30, 1994 Dear Puzzle Enthusiast: Sometimes the pieces of a puzzle just seem to fall into place. For the Fall season, we have several new puzzles whose pieces may easily fall into place for you. Or perhaps they'll prove more challenging than watching autumn leaves. Chief among our Fall puzzles is our new plastic puzzle, Sneaky Squares. It's hard to talk about this puzzle without saying that it is truly a great puzzle. A great puzzle should be simple in concept and design, but require a right angle turn of the mind in order to arrive at the solution. Sneaky Squares was invented by veteran puzzle designer Bill Cutler. He calls it his finest achievement. It consists of just 4 blocks that must be fitted into a box. What could be simpler you say? Yet it stumps 99% of the people we show it to. But, once you have figured out the solution, you can demonstrate it to your friends in seconds. Because of its simple elegance, this is an excellent gift for people who might be intimidated by a complex or esoteric puzzle. At just $15, Sneaky Squares is a must for your collection, and a great gift for your friends! Birds of an entirely different feather comprise the Perplexing Poultry series of puzzles. These intriguing puzzles, from England, are based on the tiling theories of mathematician and cosmologist Roger Penrose. Penrose became interested in the shapes of tiles that will cover a plane. Some regular shapes (such as squares) do this, but Penrose came up with a number of irregular tile sets that could cover a plane. These tiles produce patterns that are non-periodic (that is, the patterns do not repeat). They are called 'quasi-periodic' since the pattern appears to repeat regularly until you examine it closely. (Scientists have since found some real-world crystals that form in a quasi-periodic way.) The quasi-periodic tile sets make interesting puzzles. To decide the position of the next tile you place, you must take into account more than just the neighbor tiles -- you have to think about the 'whole-board position.' Choose either a color or black and white version of the Perplexing Poultry. The Black & White is reminiscent of the work of M.C. Escher. (Many of Escher's drawings, incidentally, are examples of periodic tiling.) Additionally, four of the tile sets have been made into jigsaw puzzles. The jigsaws are unusual and colorful. 500 die-cut pieces build to a 19" diameter circle in each of them. Although these are conventional jigsaws, they are quite difficult because of the quasi-periodicity of the pattern. See the enclosed flyer for illustrations of each jigsaw and for more information about Perplexing Poultry. As a special offer, to get your fingers moving as fast as your brain, we'll throw in free shipping on orders of $50 or more, if you place them by October 15! So hurry and dig into these new brainteasers. Happy puzzling, James W. Connelley President Ishi Press International P.S. We picked up a limited number of Circusmaster and Dragonmaster Masterballs at a special price. Masterball is a rotational puzzle with the sphere divided along lines of latitude and longitude. Masterballs usually sell for $19.95. While they last, we are offering these at the special price of just $11.70 each. Because they came from a European shop, the packaging is not in perfect condition, but the puzzles are just fine. Take advantage of this special offer before we run out! Dear Ishi - Please send me the following puzzles to brighten my Fall days! Puzzle Price s/h o Sneaky Squares $15.00 1 o Puzzling Poultry, B&W (PX01) $69.00 6 o Puzzling Poultry, Color (PX02) $99.00 6 o Perplexing Poultry Jigsaw (PX05) $15.00 2 o Cat Amongst the Pigeons (PX06) $15.00 2 o Perplexing Pisces (PX07) $15.00 2 o Pentaplex (PX08) $15.00 2 o Circusmaster Masterball $11.70 2 o Dragonmaster Masterball $11.70 2 Total $_______ ____ FREE shipping on orders of $50 or more received by Oct. 15, 1994! Please send these puzzles to: ________________________________________ ________________________________________ ________________________________________ ________________________________________ MC/VISA___________________________ exp:__________ California residents please include 8.25% sales tax. Toll Free order line: (800) 859-2086 Always feel free to write me if you have any questions or comments. Anton Dovydaitis Customer Support =========================================================================== Ishi Press International 408/944-9900 vc, 408/944--9110 FAX 76 Bonaventura Drive 800/859-2086 Toll Free Order Line San Jose, CA 95134 ishius@ishius.com (or @holonet.net) From @mail.uunet.ca:mark.longridge@canrem.com Mon Oct 3 05:48:56 1994 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 AA07705; Mon, 3 Oct 94 05:48:56 EDT Received: from portnoy.canrem.com ([198.133.42.251]) by mail.uunet.ca with SMTP id <102162-2>; Mon, 3 Oct 1994 05:49:15 -0400 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA01841; Mon, 3 Oct 94 05:46:17 EDT Received: by canrem.com (PCB-UUCP 1.1f) id 1B2945; Mon, 3 Oct 94 05:23:07 -0400 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: < U, R > Processes From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.808.5834.0C1B2945@canrem.com> Date: Mon, 3 Oct 1994 01:13:00 -0400 Organization: CRS Online (Toronto, Ontario) Alas, no antipodes yet, but some interesting results nonetheless. Process UR8 improves on the best known process for a certain quad-twist in the U layer at 20 q turns. Table 3 in Winning Ways gives a 22 q turn process. The following results should be particularly interesting to the physical cube solver as it is easier to execute a sequence of 2 adjacent sides compared to a sequence using 3 or more sides, which may require some re-orienting of the cube. I will measure the "face index" of a process by the number of different sides used in a certain cube sequence. Such a measure could be used to evaluate the relative elegance of two equally long processes with respect to their face indices. Jerry Bryan mentions: > Also, the global maxima are of length 25. > Does this tell us anything about the Q-turn length of the global > maxima for the full cube group? Well, that reminds me of one of the hardest patterns that Dik Winter tried to find an optimal sequence for: p141a alternate method F1 R1 L2 U3 R2 L3 U3 D2 R2 F1 D1 B1 D1 F2 U3 of Superfliptwist + 6 X R3 D3 F2 D2 L2 **This process was one of the hardest ever to reduce to 20 moves, requiring over 19 hours on an SGI R4K Indigo, 28 q turns** My own $.02 worth is that an antipode for the full group of the 3x3x3 cube is probably deeper than an antipode for the < U, R > group. Optimal Sequences for < U, R > group elements (positions) --------------------------------------------------------- Edge 3-cycle UR1 = U3 R1 U2 (R1 U1)^2 R2 U3 R3 U3 R2 U1 (16 q, 13 h) Double adjacent edge swap UR2 = U3 R3 U3 R2 U1 R1 U1 R3 U3 R1 U1 (R1 U3)^2 R3 U3 (18 q, 17 h) Diagonal Corner twist UR3 = U1 R1 U3 R1 U3 R2 U1 R1 U1 R3 (U3 R1)^2 U2 R3 U3 R3 (20 q, 18 h) Double opposite edge swap, also in sq group 24 q, 12 h UR4 = R2 U2 R3 (U2 R2)^2 U2 R3 U2 R2 (20 q, 11 h) Edge 7-cycle, equivalent to (U1 R1)^15 UR5 = U3 R1 U3 R3 U3 R1 U2 R3 U1 R3 U2 R1 U3 R3 (U3 R1)^2 (20 q, 18 h) Corner Tri-Twist UR6 = (U3 R3)^2 U1 R1 U3 R3 U3 R2 U1 R2 U3 R3 U3 R1 U1 R3 (20 q, 18 h) Corner Quad-Twist, Flat style UR7 = R1 U3 (R1 U1)^2 (R3 U3)^2 R2 U3 R1 U1 R3 U3 R1 U3 R3 (20 q, 19 h) Corner Quad-Twist, Arms & Legs style (20 q, 20 h) UR8 = R1 U1 R3 U1 R3 U3 R1 U1 R1 (U3 R3)^2 (U1 R1)^2 U3 R3 U3 ML Doodle Position UR9 = (U2 R2)^2 U2 R3 U1 R2 (U3 R2)^2 U1 R1 (22 q, 14 h) Same position found by hand: (a non-optimal 24 q, 15 h) (U2 R2)^3 U1 R1 (U2 R3)^2 U2 R1 U1 4 Opp Corner Swap, also in sq group at 26 q, 13 h UR10 = U3 R3 (U1 R1)^2 U2 R3 U1 R1 (U2 R2)^2 U1 R3 U1 (22 q, 17 h) Other Subgroups within reach ---------------------------- 11. || = 2^12 3^4 5^2 7 = 58060800 12. || = 2^12 3^4 5^2 7 = 58060800 17. || = 2^8 3^5 5^2 7 = 10886400 21. || = 2^13 3^4 5^2 7 = 116121600 22. || = 2^15 3^4 5^2 7^2 = 3251404800 I welcome any proposed < U, R > group antipodes. I haven't really looked for anything exotic like < U, R > positions which are shift invariant, or even if such a beast is possible! Of course I already mentioned that... U2 R2 U2 R2 U2 R2 = R2 U2 R2 U2 R2 U2 ...but aside from that nothing comes to mind. Generally when there are elements which occur in both the square's group AND the < U, R > group the latter is the shorter in q turns. -> Mark <- Email: mark.longridge@canrem.com From BRYAN@wvnvm.wvnet.edu Fri Oct 7 14:48:43 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA25784; Fri, 7 Oct 94 14:48:43 EDT Message-Id: <9410071848.AA25784@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 1254; Fri, 07 Oct 94 10:52:59 EDT Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 2941; Fri, 7 Oct 1994 10:52:59 -0400 X-Acknowledge-To: Date: Fri, 7 Oct 1994 10:52:58 EDT From: "Jerry Bryan" To: Subject: Re: < U, R> Group -- Q+H In-Reply-To: Message of 08/09/94 at 01:48:00 from mark.longridge@canrem.com Distance Number Branching Number Branching Ratio of from of Factor of Factor Cubes to Start W-Conjugate Cubes W-Conjugate Classes Classes 0 1 1 1 1 2 2 6 6 3 2 5 2.5 18 3 3.6 3 14 2.8 54 3 3.857 4 41 2.929 162 3 3.951 5 122 2.976 486 3 3.984 6 365 2.992 1,457 2.998 3.992 7 1,091 2.989 4,360 2.992 3.996 8 3,256 2.984 13,016 2.985 3.998 9 9,627 2.957 38,482 2.957 3.997 10 28,282 2.938 113,094 2.939 3.9987 11 82,243 2.908 328,920 2.908 3.9994 12 235,611 2.865 942,351 2.865 3.9996 13 654,297 2.777 2,616,973 2.777 3.9997 14 1,693,858 2.589 6,774,848 2.589 3.9997 15 3,776,718 2.230 15,105,592 2.230 3.9997 16 6,058,483 1.604 24,231,019 1.604 3.9995 17 4,856,334 0.802 19,421,274 0.802 3.9992 18 961,504 0.198 3,843,568 0.198 3.997 19 11,954 0.012 47,465 0.012 3.971 20 16 0.001 54 0.002 3.375 Total 18,373,824 73,483,200 3.9993 Notice that using Q+H turns instead of Q turns reduces the maximum distance from Start from 25 down to 20. When I first calculated God's Algorithm for for Q turns, I calculated it for cubes first, then for W-conjugate classes. In this case, I really did it only for W-conjugate classes (problem is four times smaller). The "Number of Cubes" column is then derived by calculating the size of each W-conjugate class; no real search is needed to obtain the number of cubes if the W-conjugate classes are already 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From dik@cwi.nl Wed Oct 12 21:55:07 1994 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07797; Wed, 12 Oct 94 21:55:07 EDT Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Thu, 13 Oct 1994 02:55:06 +0100 Received: by boring.cwi.nl id AA21510 (5.65b/3.8/CWI-Amsterdam); Thu, 13 Oct 1994 02:55:05 +0100 Date: Thu, 13 Oct 1994 02:55:05 +0100 From: Dik.Winter@cwi.nl Message-Id: <9410130155.AA21510=dik@boring.cwi.nl> To: cube-lovers@life.ai.mit.edu Subject: CFF 34, summary of contents CFF #34 came out, it ought to have been in June but is a bit late. Still, the editors expect the next issue in December. Summary of contents. Leo Links: On Folding Puzzles. A discussion about folding puzzles made from paper or cardboard that display a particular figure or text when folded. Frits Goebel and Bernhard Wiezorke: Problems for Einstein. They discuss a puzzle consisting of 8 octonimo's which is marketed as IQ CREATOR, MAGIC BLOCK or EINSTEIN PUZZLE. They show a few pretty patterns that can be formed with the 8 pieces. Vic Stok: Skyline Tetracubes. This discusses figures that can be formed from the 8 different pieces consisting of 4 cubes glued together. Jacques Haubrich and Nanco Bordewijk: Cube Chains. This discusses a number of puzzles. Each consists of 27 cubes connected to each other by an elastic string. The objective is to form a 3x3x3 cube. Bernhard Wiezorke: On Nob's L-Puzzle. This duscusses Nob's puzzle. It consists of 10 L shaped pieces, 3 squares high, 2 squares wide; all in the same orientation, one such piece 4 squares high (also the same orientation) and one 3 square high piece in different orientation (i.e. turned over). The objective is to fill a 7x7 square, turnover of the pieces is not permitted. Jacques Haubrich: Pantactic Patterns and Puzzles. This discusses an extension of the memory wheel. On the wheel the digits 0 and 1 are written such that when you look at 3 consecutive digits, all 8 different can be created. This can be generalized to n consecutive digits. It is well known (since N.G. de Bruijn) that 2^n digits are needed. An 2-dimensional extension was made by B. Astle who had a 5x5 square with a black-white pattern such that when you look at the 16 different 2x2 subsquares you will find all 16 different configurations. C.J. Bouwkamp made this into a puzzle (in the early 70's) as follows: You have 16 2x2 squares with all possible patterns. The puzzle is to put them together in a larger square such that the borders match. Rotation is *not* permitted. Torsten Sillke: Three 3x3 Matching-Puzzles. A discussion about three puzzles consisting of 9 squares that have to be put in a 3x3 square where some form of marking has to match. Jacques Haubrich: Cube 216. The puzzle Gemini consists of 10 pieces where each piece is made by joining two 1x2x2 blocks together. This is done in all possible ways. It is known that there are 50 possible ways to pack them in a 4x4x5 block. Yoshikatsu Hara extended this with 22 pieces that form all possible ways to join two 1x3x3 blocks together. One result is that there are (at least) 11 selections of 12 of these pieces so that they can be packed in a 6x6x6 cube in an unique way. There are more results and the author asks also for input. Chris Roothart: Polylambdas. Polylambdas are formed from the 30/60/90 degree triangle. Lambdas can be joined at corresponding edges. Joining along the hypothenusa is not allowed. There are 4 dilambdas, 4 trilambdas, 11 tetralambdas en 12 pentalambdas. These 31 pieces can fill a parallelogram of 4 by 31 units (the short leg is the unit). Many other problems are stated. Columns: Mark Peters: Books and Magazines (book reviews) Edward Hordern: What's Up? (details some new puzzles) ------ CFF (Cubism For Fun) is the newsletter published by the Nederlands Kubus Club NKC (Dutch Cubists Club). Membership fee is NLG 25 individual, NLG 80 institutional. (USD 1 ~ NLG 1.70). Applications for membership to the treasurer: Lucien Matthijsse Loenapad 12 3402 PE IJsselstein The Netherlands If you write, please add an international reply coupon (can be obtained at your post office). From f94dk@efd.lth.se Fri Oct 14 15:24:33 1994 Return-Path: Received: from kobra.efd.lth.se by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA04994; Fri, 14 Oct 94 15:24:33 EDT Received: from efd.lth.se [130.235.46.16] (hacke-6.efd.lth.se) by kobra.efd.lth.se with smtp (perl jhmail 0.20) (rfc1413: f94dk@hacke-6.efd.lth.se) id 2e9ea741_2e8_1 ; Fri, 14 Oct 1994 16:44:01 MET Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Message-Id: Date: Fri, 14 Oct 1994 16:43:57 MET From: David Kaspar To: CUBE-LOVERS@life.ai.mit.edu Subject: You are my only hope... Hi !! My name is David. Long time ago I was able to solve Rubik's Cube but I ha= ve unfortunatly (Ooops the spelling) forget it now. Can you please help me??= I would be very grateful, because you are my only hope. Many thankx, David email: f94dk@efd.lth.se = From ma2gapen@lucano.uco.es Tue Oct 18 08:13:23 1994 Return-Path: Received: from lucano.uco.es by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA13612; Tue, 18 Oct 94 08:13:23 EDT Received: by lucano.uco.es (4.1/SMI-4.1) id AA29888; Tue, 18 Oct 94 13:12:54 +0100 Date: Tue, 18 Oct 94 13:12:54 +0100 From: ma2gapen@lucano.uco.es (Nicolas G. Pedrajas) Message-Id: <9410181212.AA29888@lucano.uco.es> To: cube-lovers@life.ai.mit.edu Subject: help! hello, I used to know how to resolve rubik's cube, but i've forgotten it. Can anybody here help me? Thanks in advance for any help. Adios. From @mail.uunet.ca:mark.longridge@canrem.com Sun Oct 23 03:41:06 1994 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 AA09529; Sun, 23 Oct 94 03:41:06 EDT Received: from portnoy.canrem.com ([198.133.42.251]) by mail.uunet.ca with SMTP id <86581-4>; Sun, 23 Oct 1994 03:41:30 -0400 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA05154; Sun, 23 Oct 94 03:38:20 EDT Received: by canrem.com (PCB-UUCP 1.1f) id 1B6751; Sun, 23 Oct 94 03:23:51 -0400 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Cross and X's From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.814.5834.0C1B6751@canrem.com> Date: Sun, 23 Oct 1994 02:36:00 -0400 Organization: CRS Online (Toronto, Ontario) ----------------------------- Possible Legal Cross Patterns ----------------------------- Plummer Cross (6 Cross order 3) = 8 patterns Christman Cross (6 Cross order 2) = 6 patterns 4 Cross order 2 (sq group) = 3 patterns 4 Cross order 4 = 6 patterns ----------- 14 Six Cross + 9 Four Cross = 23 total legal Cross patterns There are 0 total cross patterns in the swap orbit ------------------------- Possible Legal X Patterns ------------------------- 6 X order 3 = 8 patterns 6 X order 6 = 8 patterns 6 X order 2 (sq group) = 1 pattern 4 X order 2 (sq group) = 3 patterns 2 X order 2 (sq group) = 3 patterns ----------- 17 Six X + 3 Four X + 3 Two X = 23 total legal X patterns For a while I thought that [6 x order 3] combined with the [2 x pattern] would make a new sort of [6 x order 6], but combining [6 x order 3] with the [2 x pattern] is essentially the same as combining 6 x order 3 with the pons asinorum or 6 x order 2. ------------------------------ Possible Swap-Orbit X Patterns ------------------------------ 6 X order 2 = 6 patterns 6 X order 4 = 6 patterns 4 X order 2 = 6 patterns 4 X order 4 = 6 patterns ----------- 12 Six X + 12 Four X = 24 total swap-orbit X patterns Some description of the swap-orbit patterns is in order. The 6 X order 2 pattern has a 2-cycle of opposite edges and 2 sets of 2-cycles of adjacent edges. The 6 X order 4 pattern has a 2-cycle of opposite edges and a 4-cycle of edges of adjacent faces. The 4 X order 2 has 2 sets of 2-cycles of adjacent edges. The 4 X order 4 has a 4-cycle of edges of adjacent faces. To make any of these swap-orbit patterns one would have to first exchange any 2 edge cubies. Interestingly, a thin line 6 X order 3 is possible on the 5x5x5 cube. No process as yet.... -> Mark <- Email: mark.longridge@canrem.com From mschoene@math.rwth-aachen.de Mon Oct 24 16:59:39 1994 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 AA05394; Mon, 24 Oct 94 16:59:39 EDT Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0qzWSu-000MP8C; Mon, 24 Oct 94 21:58 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0qzWSu-0000PrC; Mon, 24 Oct 94 21:58 PST Message-Id: Date: Mon, 24 Oct 94 21:58 PST From: Martin.Schoenert@math.rwth-aachen.de To: cube-lovers@life.ai.mit.edu Subject: Shift invariant processes Mark Longridge wrote in is e-mail message of 1994/04/02 The resultant position generated by process p8 is invariant under shifting, specifically 2 X on the Left and Right sides. P8 2 x ORDER 2: shift 0 D2 F2 T2 F2 B2 T2 F2 T2 1 T2 D2 F2 T2 F2 B2 T2 F2 ... 7 F2 T2 F2 B2 T2 F2 T2 D2 This is the longest process I've found so far. Certainly this property is not true of all squares group processes. I suspect there are no processes in the full group with this property (of any significant length). Perhaps the fact that the L and R faces never rotate will give some clue on how to generate processes with this property. I have classified all such shift invariant processes, using a little bit of group theory and the computer algebra system GAP. Let me first repeat the definition. A *process* g_1 g_2 ... g_n, where the letters g_i come from the set {U,U2,U3,D,D2,D3,...,B,B2,B3}, is called *shift invariant* if each of the processes g_1 g_2 ... g_n, g_2 ... g_n g_1, ..., g_n g_1 ... g_{n-1} effects the same element g in the cube group G. In the following I will be a bit sloppy and neither distinguish between letters and the corresponding generators of the cube group nor between processes and the elements of the cube group they effect. With this terminology a shift invariant processes would be one where g_1 g_2 ... g_n = g_2 ... g_n g_1 = g_n g_1 ... g_{n-1}. So lets assume that g = g_1 g_2 ... g_n is a shift invariant process. Then for every letter g_i in g we have g_i' g = g_i' (g_i g_{i+1} ... g_{i-1}) = (g_{i+1} ... g_{i-1}) = (g_{i+1} ... g_{i-1} g_i) g_i' = g g_i'. That means that g commutes with (the inverses) of each of its letters. Because g commutes with each of its letters, it also commutes with all elements of the subgroup H = < g_1, g_2, ..., g_n > generated by its letters. The set of those elements of H which commute with all elements of H is called the centre of H. Thus g lies in the centre of H. Obviously the other direction is also true. If g lies in the centre of H = < g_1, g_2, ..., g_n >, i.e., if it commutes with every element of H, then it especially commutes with its letters, and so the corresponding process is shift invariant. This says that if we have an element g in the centre of a subgroup H = < g_1, g_2, ..., g_n >, then *every* process that effects g and uses the letters g_1, g_2, ..., g_n will be a shift invariant process. So there are finitely many such elements (after all there are only finitely many elements in the entire cube group), but each gives rise to infinitely many different shift invariant processes. In particular there is *no* longest shift invariant process. So the task is to search for subgroups H generated by subsets of {U,U2,U3,D,D2,D3,...,B,B2,B3} that have non-trivial centres. There are 729 = 3^6 such subgroups. Of course we are only interested in representatives under the operation of M (the subgroup of symmetries of the entire cube), which leaves us with 56 subgroups. Of those 21 have a non-trivial centre (for this computation I used GAP). The centres are all very small and contain mostly the same elements, i.e., the same element lies in the centre of different such subgroups. I do not want to bore you with the details. Allow me to jump to the discussion of the results. There are 5 different types of elements that give rise to shift invariant processes. 1) The ``trivial'' element. The identity element lies in the centre of every subgroup H. Thus every process that effects the identity is shift invariant. There is exactely one such element in the entire group. 2) The ``central'' element. The superflip, which flips all edges, is in the centre of G. Thus every process that effects the superflip is shift invariant. There is exactely one such element in the entire group. 3) The ``abelian'' elements. The subgroups < U > and < U, D > (and their conjugates under M) are abelian, and are therefore equal to their centre. Therefore every element in < U > and < U, D > is shift invariant. There are 45 such elements in the entire group. 4) The ``odd'' element. The element (UR)^140 lies in the centre of the subgroup . It is the only shift invariant element of odd order (hence the name). Thus this process and its inverse are shift invariant. There are 24 such elements in the entire group (two for each edge). 5) The ``square'' elements. The following elements live in the ``square ring'' group (though some of them are central in proper supergroups of it). 5a) The ``single square'' elements. The element (U2 R2)^3 lies in the centre of . Thus this process is shift invariant. There are 12 such elements in the entire group (one for each edge). 5b) The ``edge square'' elements. The element (U2 R2)^3 (U2 L2)^3 = (D2 R2)^3 (D2 L2)^3 lies in the centre of . Thus this process is shift invariant. There are 6 such elements in the entire group (two for each axis). 5c) The ``diagonal square'' elements. The element (U2 R2)^3 (D2 L2)^3 = (U2 L2)^3 (D2 R2)^3 lies in the centre of . Thus this process is shift invariant. There are 3 such elements in the entire group (one for each axis). For me the most amazing elements were the ``odd'' element and the ``diagonal square'' element. They are special in the sense that the smallest subgroup in which they lie and the largest subgroup in which they are central are equal. That means that you have no choice which letters to choose to write them (you have lots of choices how arrange those letters and how often to repeat them of course). You cannot use less, because they do not lie in a smaller group, and you cannot use more, because they are not central in a larger group. Let me return to Mark's e-mail and discuss it in the light of the above. Mark writes The resultant position generated by process p8 is invariant under shifting, specifically 2 X on the Left and Right sides. P8 2 x ORDER 2: shift 0 D2 F2 T2 F2 B2 T2 F2 T2 ... Believe it or not, this is a process for the ``diagonal square'' element. Mark writes This is the longest process I've found so far. How about (UR)^140 or (UR)^1400? As mentioned above, you can make the processes as long as you wish. Mark writes Certainly this property is not true of all squares group processes. No, only for processes that effect one of the 21 elements mentioned above (31 if you want to count the ``trivial'' and ``abelian'' elements in the square group). Mark writes I suspect there are no processes in the full group with this property (of any significant length). Not true. The interesting ones are the processes effecting the ``central'' element and the ``odd'' elements. Mark writes Perhaps the fact that the L and R faces never rotate will give some clue on how to generate processes with this property. Now this remark makes me very suspicious. Did Mark know the full story? The squares subroup has trivial centre (containing only the identity), you have to leave out at least two generators belonging to opposite faces, to get a subgroup with non-trivial centre. Mark writes in another e-mail message of 1994/04/10 The following processes are also shift invariant: 2 Swap D2 R2 D2 R2 D2 R2 (6) (symmetry level 12, SI level 2) p21 2 H L2 R2 B2 L2 R2 F2 (6) (symmetry level 6, SI level 6) Amazingly, the process p3 (found using Dik Winter's program) is actually a series of 20 processes which all result in the same displacement! p3 12 flip R1 L1 D2 B3 L2 F2 R2 U3 D1 R3 D2 F3 B3 D3 F2 D3 R2 U3 F2 D3 (20) (symmetry level 1, SI level 20) The first is obviously a ``single square'' element, the second is a ``edge square'' element, and 'p3' is the ``central'' element. Thus at this time all non-trivial such elements had been found, except for the ``odd'' element. Have a nice day. Martin. PS: GAP is really a nice program to analyze the cube group from the group-theoretical side, though I would not use it to enumerate positions in search for god's algorithm. PPS: Of course I am biased, because I am one of the main authors of GAP ;-) -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From dbisel@adrian.adrian.edu Wed Oct 26 10:26:30 1994 Return-Path: Received: from adrian (adrian.adrian.edu) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA00775; Wed, 26 Oct 94 10:26:30 EDT Date: Wed, 26 Oct 1994 10:25:43 -0400 Message-Id: <94102610254293@adrian.adrian.edu> From: dbisel@adrian.adrian.edu To: cube-lovers@life.ai.mit.edu X-Vms-To: smtp%"cube-lovers@ai.ai.mit.edu" Does the "mit" in the address stand for Michigan Tech University? I am a student at Adrian College. What is the record in minutes (or seconds) for the time to solve a rubik's cube? Do you happen to have any brain teasers or hypothetical questions? I would love to hear from you. Diana Bisel From MALONEY9146@a12t.cc.fredonia.edu Wed Oct 26 11:03:59 1994 Return-Path: Received: from a12t.cc.fredonia.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA03085; Wed, 26 Oct 94 11:03:59 EDT Date: Wed, 26 Oct 1994 11:02 am EDT (15:02:37 UT) From: "Daniel P. Maloney" Organization: State University of New York - College at Fredonia To: dbisel@adrian.adrian.edu Cc: cube-lovers@life.ai.mit.edu In-Reply-To: Your message of 26 Oct 1994 10:25:43 - Message-Id: <35483102694110235@FREDONIA> I'm not sure what the record is, but I used to have a book called "Jeff Conquers The Cube In 45 Seconds (And So Can You!)". Needless to say, I never got cloise to that. Dan BTW MIT is probably Massachusetts Institute of Technology (a big, expensive school) Dan From nivek@frc2.frc.ri.cmu.edu Wed Oct 26 11:19:52 1994 Return-Path: Received: from FRC2.FRC.RI.CMU.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA03787; Wed, 26 Oct 94 11:19:52 EDT Received: from mattock.frc.ri.cmu.edu by FRC2.FRC.RI.CMU.EDU (4.1/5.17) id AA01502; Wed, 26 Oct 94 11:18:26 EDT Date: Wed, 26 Oct 94 11:18:26 EDT From: Kevin Dowling Message-Id: <9410261518.AA01502@FRC2.FRC.RI.CMU.EDU> Received: by mattock.frc.ri.cmu.edu (4.1/SMI-4.0) id AA13535; Wed, 26 Oct 94 11:19:49 EDT To: dbisel@adrian.adrian.edu, cube-lovers@life.ai.mit.edu In-Reply-To: <94102610254293@adrian.adrian.edu> (dbisel@adrian.adrian.edu) Subject: MIT Reply-To: nivek@cmu.edu (Kevin Dowling) No sorry, it stands for Massachusetts Institute of Technology, a little technical school located in Cambridge, MA, on the Charles River near Boston. CMU doesn't stand for Central Michigan University either. nivek aka: Kevin Dowling tel: 412.268.8830 Carnegie Mellon University fax: 412.682.1793 The Robotics Institute net: 5000 Forbes Avenue Pittsburgh, PA 15213 From bosch@smiteo.esd.sgi.com Wed Oct 26 11:28:44 1994 Return-Path: Received: from sgigate.sgi.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA04158; Wed, 26 Oct 94 11:28:44 EDT Received: from sgihub.corp.sgi.com by sgigate.sgi.com via ESMTP (940627.SGI.8.6.9/911001.SGI) id IAA17571; Wed, 26 Oct 1994 08:28:10 -0700 Received: from smiteo.esd.sgi.com by sgihub.corp.sgi.com via SMTP (940519.SGI.8.6.9/911001.SGI) id IAA26133; Wed, 26 Oct 1994 08:28:07 -0700 Received: by smiteo.esd.sgi.com (931110.SGI/940406.SGI.AUTO) for @sgihub.corp.sgi.com:cube-lovers@life.ai.mit.edu id AA01707; Wed, 26 Oct 94 08:27:59 -0700 From: "Derek Bosch" Message-Id: <9410260827.ZM1705@smiteo.esd.sgi.com> Date: Wed, 26 Oct 1994 08:27:59 -0700 In-Reply-To: "Daniel P. Maloney" "" (Oct 26, 11:02am) References: <35483102694110235@FREDONIA> X-Mailer: Z-Mail-SGI (3.0S.1026 26oct93 MediaMail) To: "Daniel P. Maloney" , dbisel@adrian.adrian.edu Cc: cube-lovers@life.ai.mit.edu Subject: Fast cubing Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 I too, have read the book, Jeff Conquers The Cube in 45 seconds, as well as Minh Thai's book on the cube (he's the world record holder, with 22 seconds as an official world record. I used to compete back in the cubing days, and could regularly get under 25 seconds, using a strategy of solving the corners, solving the edges on two opposite sides, followed by the middle slice. Several people on this mailing list have done serious analysis trying to reach "God's Algorithm", which isn't terribly useful to me. The operators that these analyses generate are really slow to crank out on the cube. I prefer slightly longer ones, that are more optimized for speed (hand positions, etc). Derek -- Derek Bosch "Time flies like an arrow, (415) 390-2115 but fruit flies like bananas" bosch@sgi.com J. Blaylock From HOWSER@lua6.lu.edu Wed Oct 26 11:59:14 1994 Return-Path: Received: from LUA6.LU.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AB06158; Wed, 26 Oct 94 11:59:14 EDT From: HOWSER@lua6.lu.edu Date: 26 OCT 94 11:03 To: Subject: Record times for the cube Comments: Automatic Return Receipt Requested Message-Id: Ouch! I fat-fingered it, sorry. ------- Forwarded message ------- Date: Wed, 26 Oct 1994 10:23 am CDT (15:23:26 UT) From: Gerry Howser To: bcc: Gerry Howser Subject: Record times for the cube Comments: Automatic Return Receipt Requested Message-ID: I recall a demo on Johnny Carson where a guy solved seven cubes in seven minutes and I think he had the current world record of around 21 seconds. I have solved a cube in 39 seconds but it was luck more than anything else. When I was play- ing around with making modifications to my solution to the cube I could solve any cube in about a minute and a half, which was fast enough to earn me a few drinks in bars. I think that a legitimate record would be around 30-45 seconds and would have to be an average for multiple cubes. ------------------------------------------------------------------------ Gerry Howser INTERNET: howser@lua6.lu.edu Postmaster@lua6.lul.edu howser@penny.lu.edu (Alternate) VOICE: (314) 681-5400 FAX: (314) 681-5566 ------------------------------------------------------------------------ ------- End of forwarded message(s) ------- ------------------------------------------------------------------------ Gerry Howser INTERNET: howser@lua6.lu.edu Postmaster@lua6.lul.edu howser@penny.lu.edu (Alternate) VOICE: (314) 681-5400 FAX: (314) 681-5566 ------------------------------------------------------------------------ From diamond@jrdv04.enet.dec-j.co.jp Wed Oct 26 20:35:05 1994 Return-Path: Received: from jnet-gw-1.dec-j.co.jp by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA08345; Wed, 26 Oct 94 20:35:05 EDT Received: by jnet-gw-1.dec-j.co.jp (8.6.9/JNET-GW-940327.1); id JAA20823; Thu, 27 Oct 1994 09:34:28 +0900 Message-Id: <9410270034.AA24443@jrdmax.jrd.dec.com> Received: from jrdv04.enet.dec.com by jrdmax.jrd.dec.com (5.65/JULT-4.3) id AA24443; Thu, 27 Oct 94 09:34:52 +0900 Received: from jrdv04.enet.dec.com; by jrdmax.enet.dec.com; Thu, 27 Oct 94 09:34:53 +0900 Date: Thu, 27 Oct 94 09:34:53 +0900 From: Norman Diamond 27-Oct-1994 0932 To: cube-lovers@life.ai.mit.edu Apparently-To: cube-lovers@life.ai.mit.edu Subject: Re: Record times for the cube Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=ISO-2022-JP >Ouch! I fat-fingered it, sorry. >From: Gerry Howser >To: >I could solve any cube in about a minute and a half, Nonsense. Anyone who can't hit the "v" key on their keyboard is surely incapable of manipulating the right cubie :-) -- Norman Diamond diamond@jrdv04.enet.dec.com [Digital did not write this.] From dbisel@adrian.adrian.edu Thu Oct 27 15:47:08 1994 Return-Path: Received: from adrian (adrian.adrian.edu) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA02964; Thu, 27 Oct 94 15:47:08 EDT Date: Thu, 27 Oct 1994 15:46:27 -0400 Message-Id: <94102715462720@adrian.adrian.edu> From: dbisel@adrian.adrian.edu To: cube-lovers@life.ai.mit.edu Subject: other games X-Vms-To: smtp%"cube-lovers@ai.ai.mit.edu" What other games are you interested in besides the Rubik's Cube? Do you know of any other addresses where I can get fun, cool information at? Diana Bisel From ybanezs%geds@mhsgate.salem.ge.com Thu Oct 27 16:22:05 1994 Return-Path: Received: from ns.ge.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA04610; Thu, 27 Oct 94 16:22:05 EDT Received: from thomas.ge.com by ns.ge.com (5.65/GE Gateway 1.26) with SMTP id AA15091; Thu, 27 Oct 94 16:02:04 -0400 Received: from carsdb.salem.ge.com by thomas.ge.com (5.65/GE Internal Gateway 1.26) with SMTP id AA00792; Thu, 27 Oct 94 16:22:01 -0400 Received: from mhsgate.salem.ge.com by salem.ge.com (4.1/SMI-4.1)id AA29388; Thu, 27 Oct 94 16:21:48 EDT Received: by mhsgate.salem.ge.com from NetWare MHS, SMF-70via XGATE 2.12 MHS to SMTP Gateway (XSMTP Module) Message-Id: <71F79C380105AED1@mhsgate.salem.ge.com> Date: Thu, 27 Oct 94 16:20:08 EST From: Ybanez Sheldon To: cube-lovers@ai.mit.edu Subject: Solution.. X-Mailer: XGATE 2.12 MHS/SMTP Gateway I have been able to solve the Cube in under a minute... but that was years ago when my reflexes and memory was better in Junior High... now I pull the old cube out for limbering the fingers... and seeing how much I remember the solutions... now they are so ingrained in me... I no longer remember them as separate moves.... but a conglomeration of twists and turns... the book --the title I can't remember-- I originally learned from, showed the solution as a TOP to BOTTOM approach... doing the first top layer... then the center edges... and then completing the last layer... I noticed then Mihn used the top, bottom, middle approach... when he won the World's Cube solving championship on the show 'THAT"S INCREDIBLE', which was also advocated by the solution book that was available from the address that was included with the original cubes... so then I was able to solve it either way... finding the latter approach a little faster... now the Revenge I can solve in about 5 minutes... maybe quicker, but I never really bothered to accurately time myself... I only learned the one way to solve the 4x4x4 cube... from Mihn's book. Now since I joined this mailing list I have been inundated with all these algorithms.... how do I translate them? Being a neophyte to cube 'theory' its pretty frustrating trying to figure out what all the letters and numbers mean... and what they are trying to achieve.... can anyone help? thanks in advance... ,,, ______________________________________________________ (o o) _________ +----------------------------------------------------ooO-(_)-Ooo-------+ | Sheldon Ybanez [ybanez-s@salem.ge.com] GE Drive Systems Salem, VA | | Always "Remember. No matter where you go, there you are." 88 | +======================================================================+ From BRYAN@wvnvm.wvnet.edu Thu Oct 27 17:47:30 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA11008; Thu, 27 Oct 94 17:47:30 EDT Message-Id: <9410272147.AA11008@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 8777; Thu, 27 Oct 94 17:00:31 EDT Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 8983; Thu, 27 Oct 1994 17:00:31 -0400 X-Acknowledge-To: Date: Thu, 27 Oct 1994 17:00:30 EDT From: "Jerry Bryan" To: "Ybanez Sheldon" , "Cube Lovers List" Subject: Re: Solution.. In-Reply-To: Message of 10/27/94 at 16:20:08 from , ybanezs%geds@mhsgate.salem.ge.com On 10/27/94 at 16:20:08 Ybanez Sheldon said: >Now since I joined this mailing list I have been inundated with all these >algorithms.... how do I translate them? Being a neophyte to cube >'theory' its pretty frustrating trying to figure out what all the letters >and numbers mean... and what they are trying to achieve.... >can anyone help? I was thinking of suggesting a few references, but then it occurs that perhaps there are not very many references currently in print. Here is a little Cube Theory 101. In the "Standard Model" (or maybe the "Singmaster Model") of the 3x3x3 cube, the cube is not rotated in space. The only thing you can do is twist one of the six faces. Singmaster designates the faces as Up, Down, Right, Left, Front, and Back. The names are chosen so that no two of the faces start with the same letter. There have been some latter day efforts to rename Up as Top so that all the faces have names beginning with consonants. Twists are designated by the first letter of their name -- U, D, R, L, F, and B for clockwise quarter-turns; U', D', R', L', F', and B' for counter-clockwise quarter-turns; U2, D2, R2, L2, F2, and B2 for half- turns (180 degrees). In proper typography, the "2" in "U2" is written as a superscript. Sometimes U3, D3, etc. are used to denote counter-clockwise quarter-turns because three clockwise quarter-turns produce the same result as one counter-clockwise quarter-turn. A sequence of twists is written left-to-right -- e.g., FRU'LLR. The complement notation which is used to convert clockwise quarter-turns into counter-clockwise quarter-turns may also be applied to a group of twists -- e.g., (FRU')' is equal to UR'F' (twisting in the opposite order and in the opposite direction). The same sort of notation is used to describe cubies -- the up-right cubie is ur. Singmaster distinguishes between cubies and cubicles via italic and Roman text, but that is a bit hard to do via E-mail. Things get a bit more complicated when you consider slice moves, cubes larger than 3x3x3, and rotations of the whole cube. Note that most people solving "real cubes" (as opposed to mathematical models of cubes) do indeed rotate the whole cube, for example they move the Bottom face to the Up (or Top), to make it easier to twist. However, the "Standard Model" does not rotate the whole cube because mathematically it is just as easy to twist one face as any other. Hope this helps. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From BRYAN@wvnvm.wvnet.edu Fri Oct 28 08:54:11 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA19906; Fri, 28 Oct 94 08:54:11 EDT Message-Id: <9410281254.AA19906@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 1336; Fri, 28 Oct 94 08:53:53 EDT Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 1056; Fri, 28 Oct 1994 08:53:53 -0400 X-Acknowledge-To: Date: Fri, 28 Oct 1994 08:53:52 EDT From: "Jerry Bryan" To: "Ybanez Sheldon" , "Cube Lovers List" Subject: Re: Solution.. In-Reply-To: Message of 10/27/94 at 17:00:30 from BRYAN@wvnvm.wvnet.edu On 10/27/94 at 17:00:30 Jerry Bryan said: >On 10/27/94 at 16:20:08 Ybanez Sheldon said: >The same sort of notation is used to describe cubies -- the up-right >cubie is ur. Singmaster distinguishes between cubies and cubicles >via italic and Roman text, but that is a bit hard to do via E-mail. Ooops. I just pulled out my Frey and Singmaster. Cubies and cubicles are both italics, and the distinction is one of upper case italics vs. lower case italics (still hard to do on E-mail). Face twists are Roman (block) letters. Whole cube rotations are script letters. Also, in proper typography, a complement (as in R') would normally be a superscript "-1" rather than an apostrophe. (By the way, even with a word processor or text processor, I have trouble with script letters. I can't get Word Perfect to do script letters, nor Waterloo Script. I used to use TeX, and I don't think it could do script letters. I haven't tried desk top publishing of the Pagemaker ilk. Does anybody have any suggestions? If so, I suspect this is the sort of thing where private E-mail might be more appropriate than broadcasting to the entire list. Thank in advance.) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From hoey@aic.nrl.navy.mil Fri Oct 28 11:38:16 1994 Return-Path: Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA29189; Fri, 28 Oct 94 11:38:16 EDT Received: by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA17190; Fri, 28 Oct 94 11:38:15 EDT Date: Fri, 28 Oct 94 11:38:15 EDT From: hoey@aic.nrl.navy.mil (Dan Hoey) Message-Id: <9410281538.AA17190@Sun0.AIC.NRL.Navy.Mil> To: "Cube Lovers List" Cc: "Jerry Bryan" Subject: Cube colors and face names Keywords: Rubiksong, Varga, Colors, Humor > Singmaster designates the faces as Up, Down, Right, Left, Front, and > Back. The names are chosen so that no two of the faces start with > the same letter. There have been some latter day efforts to rename > Up as Top so that all the faces have names beginning with > consonants. Yes, this is the main reason for using Top, because of the Rubiksong introduced by Varga that I described (unfortunately with many typos) on 22 Feb 90 ( is a URL that I hope works--anyone who is actually able to point and click on this, please let me know). But there's another reason. Remember the annoying feature that the color assignments to faces were never standardized? The first cube I bought had red opposite yellow, blue opposite white, and orange opposite green (I think). Even though in later days most cubes are manufactured with opposite faces ``differing by yellow''--red opposite orange, blue opposite green, and yellow opposite white--there does not seem to be a standard for the handedness of the coloring. This has long been a problem on cube-lovers, where everyone starts out asking ``I've got my cube solved except a blue sticker on the white face, a white sticker on the green face, and a green sticker on the blue face,'' and the puzzle becomes trying to figure out where those faces are. (This was fixed in Square 1, where they printed a full-color instruction book coordinated with the puzzle). My modest proposal is to define the Standard Earth-Tone Cube, which has the faces in standard and easily remembered places. The colors are taupe, dun, fawn, beige, loam, and roan. This supports the use of Top over Up, because ``taupe'' is so much more evocative than ``umber''. ``Dun'' is also a major win, and I wish I had better names for the other faces. I have yet not tried painting such a cube, because I can't figure out which color is which. Dan Hoey@AIC.NRL.Navy.Mil From @mail.uunet.ca:mark.longridge@canrem.com Fri Oct 28 11:50:15 1994 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 AA29859; Fri, 28 Oct 94 11:50:15 EDT Received: from portnoy.canrem.com ([198.133.42.251]) by mail.uunet.ca with SMTP id <86790-2>; Fri, 28 Oct 1994 11:48:59 -0400 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA01388; Fri, 28 Oct 94 11:44:45 EDT Received: by canrem.com (PCB-UUCP 1.1f) id 1B76FC; Fri, 28 Oct 94 10:52:00 -0400 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Shift Invariant Part 2 From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.825.5834.0C1B76FC@canrem.com> Date: Thu, 27 Oct 1994 21:56:00 -0400 Organization: CRS Online (Toronto, Ontario) Continuing the previous discussion on shift invariance... Mark writes: >> This is the longest process I've found so far. Martin writes: >How about (UR)^140 or (UR)^1400? As mentioned above, you can make the >processes as long as you wish. ...or (U1 R1)^35 ? And indeed, (U1 R1)^(35 * 40) is shift invariant. I meant to say (and should have said): "This is the longest optimal process I've found so far." Although I was inspecting (U1 R1)^N patterns in the quest for shift invariance, (U1 R1)^35 = (R1 U1)^35 escaped me. In fact it was my mistaken belief that the < U , R > group had no shift invariant processes. I did not realize the connection between the centre of a group and shift invariance until Martin's message of Mon Oct 24 17:10:27 1994. I actually did use GAP on the < U, R > group but I couldn't resolve the resulting position (can GAP use letters? I should have used letters). The missing insight was realizing that, although the full group had a unique centre, other subgroups have different centres. So without further adieu: 6 Counterclockwise Twist, Equivalent to (U1 R1)^35= (R1 U1)^35 & Shift Invariant UR11 = U2 R1 U1 R1 U1 R3 U1 R3 U1 R3 U2 R1 U1 R1 U1 R3 U1 R3 U1 R3 (22 q or 20 h moves) (U3 R3)^35 would execute a 6 clockwise twist. Martin writes: > 4) The ``odd'' element. > The element (UR)^140 lies in the centre of the subgroup . > It is the only shift invariant element of odd order (hence the name). > Thus this process and its inverse are shift invariant. > There are 24 such elements in the entire group (two for each edge). Is this odd due to ( U1 R1 )^35? Actually everything about the above description appears even. It is an even number of quarter turns... Martin writes: > For me the most amazing elements were the ``odd'' element and the > ``diagonal square'' element. I concur completely, although the all-commuting 12-flip is definitely interesting too. I was surprised to see the process was shift invariant. Martin writes: > Thus at this time all non-trivial such elements had been found, except > for the ``odd'' element. For which I refer to the process UR11, 22 q turns. Martin, you will be pleased to hear that I like GAP, but I need a bigger hard drive for that beast! -> Mark <- Email: mark.longridge@canrem.com From @mail.uunet.ca:mark.longridge@canrem.com Fri Oct 28 12:08:29 1994 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 AA01294; Fri, 28 Oct 94 12:08:29 EDT Received: from portnoy.canrem.com ([198.133.42.251]) by mail.uunet.ca with SMTP id <86708-3>; Fri, 28 Oct 1994 11:49:16 -0400 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA01392; Fri, 28 Oct 94 11:44:45 EDT Received: by canrem.com (PCB-UUCP 1.1f) id 1B76FD; Fri, 28 Oct 94 10:52:00 -0400 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Speed Cubing From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.826.5834.0C1B76FD@canrem.com> Date: Thu, 27 Oct 1994 21:57:00 -0400 Organization: CRS Online (Toronto, Ontario) Derek Bosch writes: > I too, have read the book, Jeff Conquers The Cube in 45 seconds, as > well as Minh Thai's book on the cube (he's the world record holder, > with 22 seconds as an official world record. I used to compete back > in the cubing days, and could regularly get under 25 seconds, using > a strategy of solving the corners, solving the edges on two opposite > sides, followed by the middle slice. The "official" world record was set by Minh Thai at the 1982 World Championships in Budapest Hungary, with a time of 22.95 seconds. Keep in mind mathematicians provided standardized dislocation patterns for the cubes to be randomized as much as possible. I think the Guiness Book of Records dropped the entry in the 1985 edition due to the fact that the contests all dried up. Interestingly David Allen, the #2 cubist in the United States, also uses the Jeff Varasano method. I met him in Buffalo NY in the a regional American Cube-a-thon on Sept 18, 1982. (Yes, that long ago!) Did you enter any of the tournaments Derek? Derek continues: > Several people on this mailing list have done serious analysis > trying to reach "God's Algorithm", which isn't terribly useful to me. > The operators that these analyses generate are really slow to crank > out on the cube. I prefer slightly longer ones, that are more > optimized for speed (hand positions, etc). I can't agree entirely. I use computer generated sequences for a lot of patterns and I find them quite useable in some cases. Also the < U, R > group processes only use 2 sides, and those I can do without moving the cube in space. Usually I rotate them in space first. -> Mark <- Email: mark.longridge@canrem.com From BRYAN@wvnvm.wvnet.edu Fri Oct 28 12:55:14 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA03736; Fri, 28 Oct 94 12:55:14 EDT Message-Id: <9410281655.AA03736@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 2674; Fri, 28 Oct 94 12:54:58 EDT Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 8315; Fri, 28 Oct 1994 12:54:58 -0400 X-Acknowledge-To: Date: Fri, 28 Oct 1994 12:54:56 EDT From: "Jerry Bryan" To: Subject: Re: Speed Cubing In-Reply-To: Message of 10/27/94 at 21:57:00 from mark.longridge@canrem.com Has any analysis of speed cubing been performed in the sense of how many twists were performed? How many twists does somebody accomplish in under 45 seconds or in 22.95 seconds? For example, you might video tape somebody and replay it in slow motion. It would still be hard to get an accurate count, I think. You would have to ignore whole cube rotations, and it might be hard to distinguish between half and quarter turns, plus somebody might be using slice moves. But if such an analysis *could* be done, it would be interesting to to compare the results to what is known mathematically about God's Algorithm. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From ybanezs%geds@mhsgate.salem.ge.com Fri Oct 28 15:57:15 1994 Return-Path: Received: from ns.ge.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA14911; Fri, 28 Oct 94 15:57:15 EDT Received: from thomas.ge.com by ns.ge.com (5.65/GE Gateway 1.26) with SMTP id AA01985; Fri, 28 Oct 94 15:36:26 -0400 Received: from carsdb.salem.ge.com by thomas.ge.com (5.65/GE Internal Gateway 1.26) with SMTP id AA01096; Fri, 28 Oct 94 15:57:11 -0400 Received: from mhsgate.salem.ge.com by salem.ge.com (4.1/SMI-4.1)id AA16210; Fri, 28 Oct 94 15:57:08 EDT Received: by mhsgate.salem.ge.com from NetWare MHS, SMF-70via XGATE 2.12 MHS to SMTP Gateway (XSMTP Module) Message-Id: <90439D380105AED1@mhsgate.salem.ge.com> Date: Fri, 28 Oct 94 15:56:21 EST From: Ybanez Sheldon To: cube-lovers@ai.mit.edu, bryan@wvnvm.wvnet.edu Subject: Re: Speed Cubing Return-Receipt-To: X-Mailer: XGATE 2.12 MHS/SMTP Gateway >Has any analysis of speed cubing been performed in the sense of how >many twists were performed? How many twists does somebody accomplish >in under 45 seconds or in 22.95 seconds? I too had wondered this... and in what way was the solved cube 'scrambled' for most of you cubists know that all scrambling is not equal... I have found some of my quickest times involved arriving at the solution much sooner than expected by not needing to perform some auxiliary, but essential and long routines.... Could these world record times have been accomplished with random scrambling..... I have always pondered how fast I would have completed the cube if I was handed the 'same' cube that Minh 'flew' on.... A move count would be very interesting indeed.... With the right equipment and a good copy of the world record video tape... it may be conceivable to actually count the moves.... In the Hey day of cubing, during a younger version myself, I also found by making a good guess at which way to solve the cube (ie.. Top to bottom or top, bottom, then middle) I could easily cut a few seconds off my S.T. (solution time)... but I can't for the life of me remember the criteria.. ,,, ______________________________________________________ (o o) _________ +----------------------------------------------------ooO-(_)-Ooo-------+ | Sheldon Ybanez [ybanez-s@salem.ge.com] GE Drive Systems Salem, VA | | Always "Remember. No matter where you go, there you are." 88 | +======================================================================+ From mschoene@math.rwth-aachen.de Fri Oct 28 17:54:41 1994 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 AA22088; Fri, 28 Oct 94 17:54:41 EDT Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0r0ycG-000MPgC; Fri, 28 Oct 94 22:13 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0r0ycB-0000PrC; Fri, 28 Oct 94 22:13 PST Message-Id: Date: Fri, 28 Oct 94 22:13 PST From: Martin.Schoenert@math.rwth-aachen.de To: cube-lovers@life.ai.mit.edu In-Reply-To: Mark Longridge's message of Thu, 27 Oct 1994 21:56:00 -0400 <60.825.5834.0C1B76FC@canrem.com> Subject: Re: Shift Invariant Part 2 Mark Longridge writes in his e-mail message of 1994/01/27 ...or (U1 R1)^35 ? And indeed, (U1 R1)^(35 * 40) is shift invariant. Mark kindly points out, that my process (UR)^140 for the ``odd'' element is a strange choice, given that (UR)^140 = (UR)^35. I can't recall how I arrived at this process. Somehow I simply missed that (UR)^140 = (UR)^35, which is especially strange since I know that (UR) has order 105 since 1982. Mark continues Equivalent to (U1 R1)^35= (R1 U1)^35 & Shift Invariant UR11 = U2 R1 U1 R1 U1 R3 U1 R3 U1 R3 U2 R1 U1 R1 U1 R3 U1 R3 U1 R3 (22 q or 20 h moves) Is UR11 the shortest process effecting the ``odd'' element in ? Mark continues Is this odd due to ( U1 R1 )^35? Actually everything about the above description appears even. It is an even number of quarter turns... The ``odd'' element o has odd order as element of the cube group, i.e., o^3 = id. All other shift invariant elements e have even order, i.e., either e^2 = id or e^4 = id (for some ``abelian'' elements). Mark continues I actually did use GAP on the < U, R > group but I couldn't resolve the resulting position (can GAP use letters? I should have used letters). I assume you wonder whether GAP can find a process for a given element. In fact GAP can do this (you define a homomorphism from the free group on U,D,L,R,F,B to the cube group and then ask for a preimage of the element). But the process is usually extremly long, e.g., for the ``central'' element GAP finds a process that has length > 2*10^6 (don't try this at home ;-). There is an improved algorithm by Philip Osterlund, which is a lot better, but still not good enough to help in the quest for god's algorithm. For example it finds a process for the ``central'' element of length 228. Mark continues Martin, you will be pleased to hear that I like GAP, but I need a bigger hard drive for that beast! Look at it this way: The system costs you $200, and you even get a hard drive for free! Seriously, you don't need the full distribution (32 MByte), but only the executable and the library (5 MByte). However, you should have enough real memory; 8 Mbyte is the minimum, 16 MByte is better, and the 64 MByte that I have in my workstation don't hurt. 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 brett@math.toronto.edu Mon Oct 31 14:36:30 1994 Return-Path: Received: from math.toronto.edu (riemann.math.toronto.edu) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07023; Mon, 31 Oct 94 14:36:30 EST Message-Id: <9410311936.AA07023@life.ai.mit.edu> Subject: To: cube-lovers@ai.mit.edu (cube) Date: Mon, 31 Oct 1994 14:35:34 -0500 (EST) From: "Brett Stevens" X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 1214 I joined this list in the middle of an ongoing discussion on shift invariance. can someone fill me in with the important definitions and what has already been discussed (if it is not too much work) brett stevens plus I am interested, scince seeing a part of Jerry Slokam's collection at the exhibit in chicago in august if anyone had a list or reference to a list of all made rubiks cube type puzzles ie external shape and intenal, rotaional structure I wouls very much like to know where I cvan get the following 1 a 2X2X2 cube 2 a the various puzzles with the pyramids internal structure but and also the cubes internal structue (3X3X3) but different external structurs. 3 conglomeration cubes--Ideal made one of these that was two 3X3X3 cubes sharing three cubies in a row I have made one of these myself by surgery on two cubes but I know that there are other "conglomerates out there" 4 kitsch-cubes (my name) but things like royal4 kitsch-cubes (my name) but things like royal4 kitsch-cubes (my name) but things like royal4 kitsch-cubes (my name) but things like royal wedding cubes, mount rushmore etc. thanks brett stevens brett@math.toronto.edu From brett@math.toronto.edu Mon Oct 31 14:43:38 1994 Return-Path: Received: from math.toronto.edu (riemann.math.toronto.edu) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07328; Mon, 31 Oct 94 14:43:38 EST Message-Id: <9410311943.AA07328@life.ai.mit.edu> Subject: diameter To: cube-lovers@ai.mit.edu (cube) Date: Mon, 31 Oct 1994 14:42:43 -0500 (EST) From: "Brett Stevens" X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 564 what is the diameter of the group of 3X3X3 rubiks cube rotations? ie. the longest cyclic subgroup. what is the shortest path to solved? also I thought that red-orange blue-white yellow-green was standard. all the ideal manufacturede c ubes were this way. and the two orientations available with the above colouring are not only an inconvienience --Dr. Hana Bizek at ARgonne NAtional LAbs has used these two parities to do veery intersesting cube sculptures or designs as she calls them brett stevens brett@math.toronto.edu From brett@math.toronto.edu Mon Oct 31 14:45:33 1994 Return-Path: Received: from math.toronto.edu (riemann.math.toronto.edu) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07473; Mon, 31 Oct 94 14:45:33 EST Message-Id: <9410311945.AA07473@life.ai.mit.edu> Subject: diameter To: cube-lovers@ai.mit.edu (cube) Date: Mon, 31 Oct 1994 14:42:43 -0500 (EST) From: "Brett Stevens" X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 564 what is the diameter of the group of 3X3X3 rubiks cube rotations? ie. the longest cyclic subgroup. what is the shortest path to solved? also I thought that red-orange blue-white yellow-green was standard. all the ideal manufacturede c ubes were this way. and the two orientations available with the above colouring are not only an inconvienience --Dr. Hana Bizek at ARgonne NAtional LAbs has used these two parities to do veery intersesting cube sculptures or designs as she calls them brett stevens brett@math.toronto.edu From alan@curry.epilogue.com Mon Oct 31 16:31:07 1994 Return-Path: Received: from curry.epilogue.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AB14288; Mon, 31 Oct 94 16:31:07 EST Received: (from alan@localhost) by curry.epilogue.com (8.6.8/8.6.6) id QAA11987; Mon, 31 Oct 1994 16:34:39 -0500 Date: Mon, 31 Oct 1994 16:34:39 -0500 Message-Id: <31Oct1994.155118.Alan@LCS.MIT.EDU> From: Alan Bawden Sender: Cube-Lovers-Request@ai.mit.edu To: brett@math.toronto.edu, cube-lovers@ai.mit.edu In-Reply-To: Brett Stevens's message of Mon, 31 Oct 1994 14:35:34 -0500 (EST) <9410311936.AA07023@life.ai.mit.edu> Subject: Administrivia Date: Mon, 31 Oct 1994 14:35:34 -0500 (EST) From: Brett Stevens I joined this list in the middle of an ongoing discussion on shift invariance. can someone fill me in with the important definitions and what has already been discussed (if it is not too much work) This is what the archives are for! Some of you old-timers may have forgotten where the archives are, and it's been a while (several years) since I reminded everybody about the existence of Cube-Lovers-Request, so I have included the standard greeting message I send to all new subscribers below. Some quick administrative observations while I have your attention: Today are 151 entries on the main mailing list. Some of those entries are local redistribution lists. I estimate there are about 160 of us. We celebrated our 14 birthday last July. I'd bet we are among the top ten oldest active mailing lists on the Internet. I periodically get requests for FTP archives of cube-related material other than our mailing list archives (simulators and other programs, tables of results, catalogs of merchandise, etc.) I am not aware of any such centralized collection of Cubist stuff. If someone knows of such a collection, or would like to organize one, or simply has a list of cube related resources on the network, I'd like to hear from them. My policy on advertising: Since Cube-Lovers is an unmoderated mailing list, I really have no control over what is sent here, but I do complain to people who send advertising that isn't obviously Cube related. And I reserve the right to start complaining about -all- advertising should it ever get out of hand. ------- Begin Greeting Message ------- Our addresses are Cube-Lovers@AI.MIT.EDU for submissions and Cube-Lovers-Request@AI.MIT.EDU for administrivia. Please note that Cube-Lovers-Request is processed by a human being, not a computer program (such as LISTSERV or Majordomo). If your request is not instantly processed, it is because I don't spend my entire life reading my electronic mail. I do know how to interpret many of the commands typically sent to such programs, but I would prefer it if instead you can remember to address me in complete sentences. If you are interested in the archives of the Cube-Lovers mailing list: Using FTP, connect to FTP.AI.MIT.EDU, login as "anonymous" (any password), and in the directory "pub/cube-lovers" you will find the thirteen (compressed) files "cube-mail-0.gz" through "cube-mail-12.gz". Archive vital statistics (when uncompressed): File From To Size (bytes) ---- ---- -- ------------ cube-mail-0 12 Jul 80 23 Oct 80 185037 cube-mail-1 3 Nov 80 9 Jan 81 135719 cube-mail-2 10 Jan 81 3 Aug 81 138566 cube-mail-3 3 Aug 81 3 May 82 137753 cube-mail-4 4 May 81 11 Dec 82 139660 cube-mail-5 11 Dec 82 6 Jan 87 173364 cube-mail-6 10 Jan 87 13 Apr 90 216733 cube-mail-7 12 Oct 90 9 Sep 91 137508 cube-mail-8 1 Nov 91 25 May 92 171205 cube-mail-9 28 May 92 7 Jan 93 155755 cube-mail-10 20 Mar 93 6 Dec 93 171881 cube-mail-11 6 Dec 93 18 Feb 94 349772 cube-mail-12 24 Feb 94 5 Sep 94 181193 In addition, the file "recent-mail" contains a copy of the currently active section of the archive. (Unfortunately, due to the way mail works here at the AI Lab, it is not possible to have new mail accumulate directly into this file, so there may be some delay before a new message arrives here.) Finally, the file "README" contains the information you are currently reading. - Alan ------- End Greeting Message ------- From BRYAN@wvnvm.wvnet.edu Mon Oct 31 16:48:57 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA14977; Mon, 31 Oct 94 16:48:57 EST Message-Id: <9410312148.AA14977@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 4808; Mon, 31 Oct 94 15:39:05 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 7362; Mon, 31 Oct 1994 15:39:05 -0500 X-Acknowledge-To: Date: Mon, 31 Oct 1994 15:39:04 -0500 (EST) From: "Jerry Bryan" To: "Cube Lovers List" Subject: Speed Cubing Path Lengths I have received several private E-mail messages indicating that the algorithms used by speed cubists solve the cube in 50 or 60 moves. On the one hand, that seems astonishingly good to me, being fairly close to the solutions from early Thistlethwaite programs. On the other hand, it is roughly double (depending, I suppose on whether H-turns are counted or not) what is probably the true God's Algorithm. Hence, it doesn't tell us much about God's Algorithm except that the speed cubists are very, very good. On another subject, my Cube Theory 101 article said that the apostrophe was used in E-mail to denote complements, when of course it is used to denote inverses -- not the same thing as complements at all. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From dik@cwi.nl Mon Oct 31 18:14:47 1994 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA20716; Mon, 31 Oct 94 18:14:47 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Tue, 1 Nov 1994 00:14:46 +0100 Received: by boring.cwi.nl id AA06573 (5.65b/3.8/CWI-Amsterdam); Tue, 1 Nov 1994 00:14:45 +0100 Date: Tue, 1 Nov 1994 00:14:45 +0100 From: Dik.Winter@cwi.nl Message-Id: <9410312314.AA06573=dik@boring.cwi.nl> To: Cube-Lovers@ai.mit.edu Subject: Re: Speed Cubing Path Lengths > I have received several private E-mail messages indicating that > the algorithms used by speed cubists solve the cube in 50 or > 60 moves. On the one hand, that seems astonishingly good to me, > being fairly close to the solutions from early Thistlethwaite > programs. On the other hand, it is roughly double (depending, I > suppose on whether H-turns are counted or not) what is probably > the true God's Algorithm. Hence, it doesn't tell us much about > God's Algorithm except that the speed cubists are very, very > good. The best current algorithm has a proven upperbound of 37 turns (q and h). God's Algorithm is probably much shorter. In fact the program that implements Kociemba's algorithms has not yet found a configuration (out of many thousands random configurations tested) that could not be solved in 20 turns or less. If we look at distributions for similar puzzles it is expected that more than one in three configurations requires the maximum number of turns minus 1 or 2. So I expect God's Algorithm to be at most 22 turns. Still a long way to go. dik From devo@vnet.ibm.com Tue Nov 1 13:20:25 1994 Return-Path: Received: from VNET.IBM.COM by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17856; Tue, 1 Nov 94 13:20:25 EST Message-Id: <9411011820.AA17856@life.ai.mit.edu> Received: from GDLVM7 by VNET.IBM.COM (IBM VM SMTP V2R2) with BSMTP id 2446; Tue, 01 Nov 94 12:33:01 EST Date: Tue, 1 Nov 94 12:33:54 EST From: "Dave Eaton" To: cube-lovers@life.ai.mit.edu Subject: Is there a symbolic cube program? Is there a program that allows you to type in Singmaster-style moves and then prints out the resultant state, something like this (not actual results): INPUT: (R U2 R3 U2)2 OUTPUT: (fur,drb,rdf) (fr,dr) This is what I tried to write long ago, but I never had all the tricks needed to get the program to work. If no program like this exists, is there something similar? I guess I would be looking for nicely-portable C or a DOS binary. Thanks to you all for sharing cube information. ......Dave Eaton, N2NOQ, Owego NY, devo@vnet.ibm.com From MALONEY9146@a12t.cc.fredonia.edu Wed Nov 2 12:56:09 1994 Return-Path: Received: from a12t.cc.fredonia.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA06258; Wed, 2 Nov 94 12:56:09 EST Date: Wed, 2 Nov 1994 12:35 pm EST (17:35:07 UT) From: "Daniel P. Maloney" Organization: State University of New York - College at Fredonia To: cube-lovers@ai.mit.edu Subject: Help ma, please! Message-Id: <28373110294123506@FREDONIA> I hate posting this message to the entire list, but how do you unsubscribe from this list? Dan From alan@curry.epilogue.com Wed Nov 2 14:57:30 1994 Return-Path: Received: from curry.epilogue.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AB14077; Wed, 2 Nov 94 14:57:30 EST Received: (from alan@localhost) by curry.epilogue.com (8.6.8/8.6.6) id OAA01177; Wed, 2 Nov 1994 14:59:04 -0500 Date: Wed, 2 Nov 1994 14:59:04 -0500 Message-Id: <2Nov1994.145313.Alan@LCS.MIT.EDU> From: Alan Bawden Sender: Cube-Lovers-Request@ai.mit.edu To: MALONEY9146@fredonia.edu Cc: cube-lovers@ai.mit.edu In-Reply-To: "Daniel P. Maloney"'s message of Wed, 2 Nov 1994 12:35 pm EST (17:35:07 UT) <28373110294123506@FREDONIA> Subject: Help ma, please! Date: Wed, 2 Nov 1994 12:35 pm EST (17:35:07 UT) From: "Daniel P. Maloney" I hate posting this message to the entire list, but how do you unsubscribe from this list? Dan As I reminded everybody just last weekend, so you can't say you didn't see it: Please note that Cube-Lovers-Request is processed by a human being, not a computer program (such as LISTSERV or Majordomo). If your request is not instantly processed, it is because I don't spend my entire life reading my electronic mail. I do know how to interpret many of the commands typically sent to such programs, but I would prefer it if instead you can remember to address me in complete sentences. Your request to unsubscribe was sent to me less than 24 hours ago. I'm sorry I didn't drop everything just to deal with it. How about if I do it later on this evening? Can you wait that long? From hoey@aic.nrl.navy.mil Fri Nov 4 11:46:53 1994 Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA24797; Fri, 4 Nov 94 11:46:53 EST Received: from sun13.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA10296; Fri, 4 Nov 94 11:46:51 EST Return-Path: Received: by sun13.aic.nrl.navy.mil; Fri, 4 Nov 94 11:46:50 EST Date: Fri, 4 Nov 94 11:46:50 EST From: hoey@aic.nrl.navy.mil Message-Id: <9411041646.AA21659@sun13.aic.nrl.navy.mil> To: Cube-Lovers@life.ai.mit.edu Subject: The real size of cube space In January of this year, Jerry Bryan and I wrote of counting the number of M-conjugacy classes of Rubik's cube. In the sense that (for instance) there is really only one position 1 QT from start, even though that QT may be applied in twelve different ways, this task amounts to counting the true number of positions of the cube. The earlier discussion centered on calculations involving computer analysis of large numbers of positions. However, a look in Paul B. Yale's book _Geometry and Symmetry_ gave me a clue: the Polya-Burnside theorem is a tool that allows us to perform this calculation by hand. The Polya-Burnside theorem describes a relation between a finite group J and a _representation_ of the group. For our purposes, a represen- tation is a homomorphism of J into a permutation group, R: J -> S[X]. Here, S[X] refers to the group of all permutations of a set X; the image of J, called R(J), need not be the whole of S[X], but R(J) will be a subgroup of S[X]. The _orbits_ of R(J) are the equivalence classes of X under the relation x~y, said to be true if there is some permutation p in R(J) for which p(x)=y. The _fixed points_ of a permutation p in R(J) are the elements x of X for which p(x)=x. The Polya-Burnside theorem states that the average number of fixed points of permutations in R(J) is equal to the number of orbits of R(J). That is, |R(J)| |Orbits(R(J))| = Sum[p in R(J)] |FixedPoints(p)|. The average may also be taken over J: |J| |Orbits(R(J))| = Sum[j in J] |FixedPoints(R(j))|, a nontrivial distinction, since R may not be one-to-one (though it is for our application). The Polya-Burnside theorem is not very inaccessible nor hard to prove, but I will not prove it here. For our purpose, we take the group J to be M, the 48-element group of symmetries of the cube. X will be the set of all cube positions, which we usually call Gx (for GE, GC, or G, depending on whether we consider edges, corners, or both; we are considering the positions relative to fixed face centers in all three cases). And the repre- sentation R is the operation of M-conjugation: (R(m))(g) = m' g m. Verifying that R is a homomorphism is an exercise in associativity that Jim Saxe and I carried out in the Symmetry and Local Maxima paper, in the archives [cube-mail-1, 14 December 1980]. R has been so chosen because we wish to calculate the number of M-conjugacy classes of Gx, |Gx\Conj(M)|, which is be the number of orbits of R(M). To apply the Polya-Burnside theorem for this, we need to calculate, for each element of m of M, the number of fixed points of R(m). That is the number of elements g of Gx for which m' g m = g. Multiplying by m, this becomes g m = m g: the fixed points we wish to count are just those elements g of Gx that commute with m. There are several tools to make the counting easier. First, I'll note that just as there are M-conjugacy classes of Gx, there are M-conjugacy classes of M itself. The number of fixed points of R(m) is the same for any m in a given conjugacy class. So to calculate the total number of fixed points over R(M), we need only calculate the number of g in Gx commuting with each of the ten classes of cube symmetry and multiply by the size of the class. The fundamental principle we use in finding whether g commutes with m can be found by examining the cycles of m. Suppose m permutes a cycle (c1,c2,...,ck), so that c2=m(c1), c3=m(c2),...,ck=m(c[k-1]),c1=m(ck). For g to commute with m, we have g(c2)=m(g(c1)), g(c3)=m(g(c2)), ..., g(ck)=m(g(c[k-1]), and g(c1)=m(g(ck)). So (g(c1),g(c2),...,g(ck)) is also a cycle of m. Thus g must map each k-cycle of m to another k-cycle of m, and in the same order. Conversely, if g acts thus on cycles, then g will commute with m, and so g is a fixed point of R(m). Suppose that m has j different k-cycles of cubies. There are j! k^j possibilities for g's action on the cubies in those k-cycles: j! permutations of cycles, and for each g:(c1,c2,...,ck)->(d1,d2,...,dk), k choices for g(c1) among {d1,...,dk}. It turns out to be a fairly easy exercise to show that half of those possibilities are even permutations and half odd, though the partition by parity is surprisingly different depending on whether k is even or odd. This will allow us to combine the results for GE and GC simply by multiplying together and dividing by two. Now consider orientation of cubies. This is similar to the case of permutation, in that the orientation that g imposes on a cubie is a constant for all cubies in a cycle. I will first discuss the edge orientation, which is fairly straightforward, and continue to corner orientation, which has some surprising features. For edge orientation, if all the cycles have even length, then g's orientation parity is zero over each cycle, and so zero over the entire cube. So we can choose the orientation of imposed by c1->g(c1) for each cycle (c1,...,ck) in 2^j ways. If there are odd-length cycles, then half of the orientations will have nonzero orientation parity, and only 2^(j-1) possible orientations can be achieved. For corners, we might expect there to be 3^(j-1) orientations, except 3^j for cycles of length a multiple of three, and this is often so. But there are two important exceptions. First, if m is a reflection (i.e., not a proper rotation in C) then alternate cubies in each cycle must be given the opposite orientation by g. If the cycle has even length, this conserves orientation, so there will be 3^j possibili- ties. If the cycle has odd length, this implies that the orientation of each cubie must be its own opposite (i.e., zero twist). Thus, there there is only one possible orientation of the 1-cycles in the diagonal reflections. The second exception, an even bigger surprise, occurs when m is either the 120-degree rotation or the 60-degree in- verted rotation. It turns out that the orientation constraint forbids any permutation that exchanges the two 1-cycles in these positions. (This constraint on permutations would throw off the equality between even and odd permutations, except that these classes of m have other corner cycles that restore the balance.) The impossibility of m commuting with an exchange of the two corners can be verified by examining the possible orientations, but I haven't got any good way of characterizing when it would be be a problem in general. In fact, I did not notice it until I investigated discrepancies with the exhaustive computer analysis. Using the above analysis, we may carry out the calculation as in the three tables below. The first two tables count the number of fixed points of R(m) for an element m of each class, multiply by the class size, and divide by |J|=48 to get the number of orbits as in the Polya-Burnside theorem. The third table calculates the number of fixed points by combining the results of the first two tables, divided by the class size (which was multiplied in both for edges and for corners), and divided by 2 (because only half the combined positions have matching permutation parity). Counting M-conjugacy classes of the edges of Rubik's cube. M class Cycles Total F.P. Numeric (class size) of m Perms Oris in class Total/48 ============== =========== ====== ====== ========== =========== Identity (1) 12 1-cycles 12! 2^12/2 12! 2^11 20437401600 Axis Rot/2 (3) 6 2-cycles 6! 2^6 2^6 6! 3 2^12 184320 Rot/3 (8) 4 3-cycles 4! 3^4 2^4/2 4! 3^4 2^6 2592 Diag Rot/2 (6) 5 2-cycles 5! 2^5 2^5 2 1-cycles 2 2^2/2 5! 3 2^13 61440 Rot/4 (6) 3 4-cycles 3! 4^3 2^3 3! 3 2^10 384 Inv Rot/4 (6) 3 4-cycles 3! 4^3 2^3 3! 3 2^10 384 Diag Ref (6) 5 2-cycles 5! 2^5 2^5 2 1-cycles 2 2^2/2 5! 3 2^13 61440 Inv Rot/6 (8) 2 6-cycles 2! 6^2 2^2 2! 3^2 2^7 48 Axis Ref (3) 4 2-cycles 4! 2^4 2^4 4 1-cycles 4! 2^4/2 4! 3^2 2^14 73728 Inversion (1) 6 2-cycles 6! 2^6 2^6 6! 2^12 61440 ----------- | GE\Conj(M) | = 20437847376 Counting M-conjugacy classes of the corners of Rubik's cube. M class Cycles Total F.P. Numeric (class size) of m Perms Oris in class Total/48 =============== ========== ====== ===== =========== ======= Identity (1) 8 1-cycles 8! 3^8/3 8! 3^7 1837080 Axis Rot/2 (3) 4 2-cycles 4! 2^4 3^4/3 4! 3^4 2^4 648 Rot/3 (8) 2 3-cycles 2! 3^2 3^2 2 1-cycles 1 3^2/3 3^5 2^4 81 Diag Rot/2 (6) 4 2-cycles 4! 2^4 3^4/3 4! 3^4 2^5 1296 Rot/4 (6) 2 4-cycles 2! 4^2 3^2/3 3^2 2^6 12 Inv Rot/4 (6) 2 4-cycles 2! 4^2 3^2 3^3 2^6 36 Diag Ref (6) 2 2-cycles 2! 2^2 3^2 4 1-cycles 4! 1 4! 3^3 2^4 216 Inv Rot/6 (8) 1 6-cycle 6 3 1 2-cycle 1 3 3^3 2^4 9 Axis Ref (3) 4 2-cycles 4! 2^4 3^4 4! 3^5 2^4 1944 Inversion (1) 4 2-cycles 4! 2^4 3^4 4! 3^4 2^4 648 ------- | GC\Conj(M) | = 1841970 Counting M-conjugacy classes of the entire Rubik's cube M class Edge Corner Corner times edge (class size) F.P. F.P. / (96*class size) =============== ========== ========= ======================= Identity (1) 12! 2^11 8! 3^7 901,083,401,551,872,000 Axis Rot/2 (3) 6! 3 2^12 4! 3^4 2^4 955,514,880 Rot/3 (8) 4! 3^4 2^6 3^5 2^4 629,856 Diag Rot/2 (6) 5! 3 2^13 4! 3^4 2^5 318,504,960 Rot/4 (6) 3! 3 2^10 3^2 2^6 18,432 Inv Rot/4 (6) 3! 3 2^10 3^3 2^6 55,296 Diag Ref (6) 5! 3 2^13 4! 3^3 2^4 53,084,160 Inv Rot/6 (8) 2! 3^2 2^7 3^3 2^4 1,296 Axis Ref (3) 4! 3^2 2^14 4! 3^5 2^4 1,146,617,856 Inversion (1) 6! 2^12 4! 3^4 2^4 955,514,880 ----------------------- | G\Conj(M) | = 901,083,404,981,813,616 These results have been corroborated and expanded by use of combinatorial computer programs, to be described in a later message. Dan Hoey Hoey@AIC.NRL.Navy.Mil From @mail.uunet.ca:mark.longridge@canrem.com Sat Nov 5 23:49:54 1994 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 AA02464; Sat, 5 Nov 94 23:49:54 EST Received: from portnoy.canrem.com ([198.133.42.251]) by mail.uunet.ca with SMTP id <91122-1>; Sat, 5 Nov 1994 23:50:20 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA17381; Sat, 5 Nov 94 23:47:01 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1BB9FA; Sat, 5 Nov 94 23:24:55 -0400 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Shifty Invariance From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.846.5834.0C1BB9FA@canrem.com> Date: Sat, 5 Nov 1994 22:16:00 -0500 Organization: CRS Online (Toronto, Ontario) ---------------------------------------- Even more thoughts on "Shift Invariance" ---------------------------------------- >>Mark continues >> >> Equivalent to (U1 R1)^35= (R1 U1)^35 & Shift Invariant >> UR11 = U2 R1 U1 R1 U1 R3 U1 R3 U1 R3 U2 R1 U1 R1 U1 R3 U1 R3 U1 R3 >> (22 q or 20 h moves) >> Martin asks: >Is UR11 the shortest process effecting the ``odd'' element in ? After a bit of computer cubing I found: p183 6 Twist R1 U3 R2 U3 R1 D3 U3 R1 U3 R3 D2 R3 U3 R1 D3 U3 (18 q or 16 h moves) This requires using the larger group of , although I expected a 16 turn process. Note the fact this larger group has face index 3 (rather than 2). But now the process is NOT shift invariant and we see the route itself can determine whether it will be shift invariant! I welcome any mathematical explanation! With even more contemplation I noticed that the process for the edge 3-cycle UR1 = U3 R1 U2 (R1 U1)^2 R2 U3 R3 U3 R2 U1 (16 q, 13 h) ...was reducible to UR1a= F1 U2 (F1 U1)^2 F2 U3 F3 U3 F2 (14 q, 11 h)] Of course, now we are using rather than . -> Mark <- Email: mark.longridge@canrem.com From BRYAN@wvnvm.wvnet.edu Sun Nov 6 09:15:57 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA15035; Sun, 6 Nov 94 09:15:57 EST Message-Id: <9411061415.AA15035@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 3785; Sun, 06 Nov 94 09:15:38 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 2152; Sun, 6 Nov 1994 09:15:38 -0500 X-Acknowledge-To: Date: Sun, 6 Nov 1994 09:15:37 -0500 (EST) From: "Jerry Bryan" To: Subject: Re: Shifty Invariance In-Reply-To: Message of 11/05/94 at 22:16:00 from mark.longridge@canrem.com On 11/05/94 at 22:16:00 mark.longridge@canrem.com said: >p183 6 Twist R1 U3 R2 U3 R1 D3 U3 R1 U3 R3 D2 R3 U3 R1 D3 U3 > (18 q or 16 h moves) ^^^^^^^^^^^^^^^^^^^^^ This is not a shift invariance question, but rather two questions about your searches. One question is, do you perform separate searches for q-turns and h-turns, or only for h-turns? The reason I ask is the obvious fact that optimal processes in q-turns need not contain h-turns. The second question is, how on earth do you keep track of all those processes in your searches? I have been asked how I search so many positions. I have answered the question before, but I guess another part of the answer that I haven't mentioned is that I don't keep up with processes at all, only positions. If I am asked to provide processes, I can do so, but it is a very painful task. I have thought about keeping up with processes, but I am quite sure that if I did so it would reduce the number of positions I could search. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From mschoene@math.rwth-aachen.de Sun Nov 6 17:31:30 1994 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 AA04624; Sun, 6 Nov 94 17:31:30 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0r4G5I-000MP6C; Sun, 6 Nov 94 23:29 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0r4G5I-0000R9C; Sun, 6 Nov 94 23:29 PST Message-Id: Date: Sun, 6 Nov 94 23:29 PST From: Martin.Schoenert@math.rwth-aachen.de To: cube-lovers@life.ai.mit.edu Cc: CRSO.Cube@canrem.com In-Reply-To: Mark Longridge's message of Sat, 5 Nov 1994 22:16:00 -0500 <60.846.5834.0C1BB9FA@canrem.com> Subject: Re: Shifty Invariance Mark writes in his e-mail message of 1994/11/05 After a bit of computer cubing I found: p183 6 Twist R1 U3 R2 U3 R1 D3 U3 R1 U3 R3 D2 R3 U3 R1 D3 U3 (18 q or 16 h moves) This requires using the larger group of , although I expected a 16 turn process. Note the fact this larger group has face index 3 (rather than 2). But now the process is NOT shift invariant and we see the route itself can determine whether it will be shift invariant! I welcome any mathematical explanation! As I tried to explain in my first e-mail message, a shift invariant process is a process in a subgroup X of G corresponding to an element x in the centre *of this subgroup*. The ``odd'' element is an element in the centre of the subgroup < U, R >. Thus any process effecting this element written in U and R is a shift invariant process. UR11 is one such process. However, the ``odd'' element does not lie in the centre of the subgroup < U, R, D > (in fact this subgroup has trivial centre). Thus a process effecting this element *involving D*, will *not* be shift invariant. Some shift invariant processes are in fact in the centre of multiple subgroups. For example the square elements, except for the ``diagonal square'' element, have this property. For such elements one has some choice which generators to use. For example the ``single square'' elements (U2 R2)^3 lies in the centre of < U2, R2 > and < U2, D, R2, L > (and all subgroups inbetween), so every process effecting this element involving any subset of U2, D, D2, R2, L, and L2, will be a shift invariant process. For the ``odd'' element, one has now choice. It lies in the centre of < U, R >, but not in the centre of any larger group. Thus a shift invariant process effecting the ``odd'' element must involve U and R, and cannot involve more generators. 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 Mon Nov 7 19:20:36 1994 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 AA13091; Mon, 7 Nov 94 19:20:36 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0r4eGO-000MP6C; Tue, 8 Nov 94 01:18 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0r4eGN-0000R9C; Tue, 8 Nov 94 01:18 PST Message-Id: Date: Tue, 8 Nov 94 01:18 PST From: Martin.Schoenert@math.rwth-aachen.de To: Cube-Lovers@life.ai.mit.edu Cc: hoey@aic.nrl.navy.mil In-Reply-To: hoey@aic.nrl.navy.mil's message of Fri, 4 Nov 94 11:46:50 EST <9411041646.AA21659@sun13.aic.nrl.navy.mil> Subject: Re: The real size of cube space Dan Hoey writes in his e-mail message of 1994/11/04 In January of this year, Jerry Bryan and I wrote of counting the number of M-conjugacy classes of Rubik's cube. In the sense that (for instance) there is really only one position 1 QT from start, even though that QT may be applied in twelve different ways, this task amounts to counting the true number of positions of the cube. The earlier discussion centered on calculations involving computer analysis of large numbers of positions. However, a look in Paul B. Yale's book _Geometry and Symmetry_ gave me a clue: the Polya-Burnside theorem is a tool that allows us to perform this calculation by hand. ...a very nice application of the Polya-Burnside theorem, to compute the number of M-conjugacy classes in G... Yes, a little bit of group theory can answer many questions arising from the cube. In fact I have noticed that quite a few of well known results in group theory have been rediscovered in this forum. Note that I don't think this is a bad thing. At least for me results that I ``knew'' are now, that they have been demonstrated for the cube, much easier to grasp than they were before (grasp is certainly an appropriate term in connection with the cube). Dan continues For our purpose, we take the group J to be M, the 48-element group of symmetries of the cube. X will be the set of all cube positions, which we usually call Gx (for GE, GC, or G, depending on whether we consider edges, corners, or both; we are considering the positions relative to fixed face centers in all three cases). And the repre- sentation R is the operation of M-conjugation: (R(m))(g) = m' g m. Verifying that R is a homomorphism is an exercise in associativity that Jim Saxe and I carried out in the Symmetry and Local Maxima paper, in the archives [cube-mail-1, 14 December 1980]. The way I view this is as follows. The entire cube group C is a permutation group group on 6*9 points, generated by the six face turns U, D, L, R, F, B; the three middle slice turns M_U, M_L, M_F; and the reflection S. This group has a subgroup M of symmetries of the cube (of order 48), generated by U M_U D', L M_L R', F M_F B', and S. Another subgroup is G, generated by the six face turns, which has index 48 in G. G is a normal divisor of C, G is the semidirect product of M and G. The same is true for GE and GC. Obviously M operates by conjugation on G, and this implies that the mapping R is a homomorphisms. Another way to say this is that M is a subgroup of the outer autmorphism group of G (which in this case can be easily represented as a supplement of G). Note that the elements of M are also a autmorphisms of the Cayley graph. That means that elements of M respects the length of operations. That is if g_1 and g_2 are elements of G that are in one conjugacy class under M, then the lenght of the shortest process effecting them is equal. This follows from the fact that M fixes the set of the generators of G and their inverses. M is fact the largest subgroup of the outer autmorphism group with this property, which makes it rather important. Dan continues R has been so chosen because we wish to calculate the number of M-conjugacy classes of Gx, |Gx\Conj(M)|, which is be the number of orbits of R(M). To apply the Polya-Burnside theorem for this, we need to calculate, for each element of m of M, the number of fixed points of R(m). That is the number of elements g of Gx for which m' g m = g. Multiplying by m, this becomes g m = m g: the fixed points we wish to count are just those elements g of Gx that commute with m. This set is called the *centralizer* of m in Gx. Usually the centralizer in a group X is only defined for elements in X, but it is obvious how to extend this definition. Dan continues The fundamental principle we use in finding whether g commutes with m can be found by examining the cycles of m. Suppose m permutes a cycle (c1,c2,...,ck), so that c2=m(c1), c3=m(c2),...,ck=m(c[k-1]),c1=m(ck). ...nice discussion of what must happen to cycles if two permutations commute... This can be used directly to compute the centralizer of an element in the full symmetric group. Since G's structure is very similar to a symmetric group (or more accurately the direct product of two symmetric groups), it allows to describe the centralizer of an element in G. The more a group differs from a symmetric group the less this analysis helps (for those that know what I'm talking about: the more a group differs from the symmetric group, the worse a backtrack computation using cycle structure analysis is). Dan continues Counting M-conjugacy classes of the entire Rubik's cube M class Edge Corner Corner times edge (class size) F.P. F.P. / (96*class size) =============== ========== ========= ======================= Minor typo. You don't mean ``Corner times edge / (96 * class size)'' but ``Corner times edge / 96 * class size'', which is in fact what you computed for the following table. Dan continues | G\Conj(M) | = 901,083,404,981,813,616 Here is how you compute this value in GAP (excuse me the plug). gap-3.4 -b -g 4m gap> Sum( ConjugacyClasses( M ), > c -> Size( Centralizer(G,Representative(c)) ) / 48 * Size(c) ); 901083404981813616 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 hoey@aic.nrl.navy.mil Tue Nov 8 17:59:34 1994 Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA04820; Tue, 8 Nov 94 17:59:34 EST Received: from sun13.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA02972; Tue, 8 Nov 94 17:59:32 EST Return-Path: Received: by sun13.aic.nrl.navy.mil; Tue, 8 Nov 94 17:59:31 EST Date: Tue, 8 Nov 94 17:59:31 EST From: hoey@aic.nrl.navy.mil Message-Id: <9411082259.AA05868@sun13.aic.nrl.navy.mil> To: Martin.Schoenert@math.rwth-aachen.de Subject: Re: The real size of cube space Cc: Cube-Lovers@life.ai.mit.edu Wow, I didn't realize this sort of calculation had been automated. Martin.Schoenert@math.rwth-aachen.de writes: The way I view this is as follows. The entire cube group C is a permutation group group on 6*9 points, generated by the six face turns U, D, L, R, F, B; the three middle slice turns M_U, M_L, M_F; and the reflection S. This group has a subgroup M of symmetries of the cube (of order 48), generated by U M_U D', L M_L R', F M_F B', and S. Another subgroup is G, generated by the six face turns, which has index 48 in G. G is a normal ^ divisor of C, G is the semidirect product of M and G. The same is ^ true for GE and GC. I think two of those G's are supposed to be C's, right? What is the difference between a direct product and a semidirect product? ... [conjugation by] M fixes the set of the generators of G and their inverses. M is fact the largest subgroup of the outer autmorphism group with this property, which makes it rather important. In a 1983 Cubic Circular article (of which I know only Stan Isaacs's summary) David Singmaster observed that the group is larger for larger cubes, provided we work what I call the ``theoretical invisible group''. That is, we solve not only the surface of the cube, but the hypothetical interior (n-2)^3 cube, and all the smaller (n-2k)^3 cubes as well. I blithered at length about this in my article of 1 June 1983 archived (I think I've got it right this time) at . The idea is that a mapping called evisceration allows us to permute the layers of the cube. On the 4x4x4 cube, this for instance allows us to exchange each inner slab with its adjacent outer slab. It also allows us to conjugate each inner slab move by central inversion, while leaving the outer slab moves alone. In general, evisceration of a d-dimensional cube by f maps each feature (cubie, colortab, or face-center arrow) at coordinates (x[1],x[2],...,x[d]) to (f(x[1]),f(x[2]),...,f(x[d])), where f is a permutation of the intervals between the cleavage coordinates of the cube. I believe that if f commutes with the central inversion, then conjugation by evisceration is an outer automorphism of the Rubik's cube group. (I think I have proved this for d=3, and I think the proof in higher dimensions should not be difficult given the right notation.) The group of all eviscerations includes the central inversion; we can of course augment it by the rotation group in d-space. Is this the maximum outer automorphism group that respects generators of the Rubik's cube? For this we take the generators to be turns of slabs between adjacent cleavage planes. (Turns are direct d-1-dimensional isometries.) I was already familiar with this augmented symmetry group because it also induces automorphisms on d-dimensional tic-tac-toe. (In fact, it may be the maximal automorphism group on all tic-tac-toe boards of side greater than two. I know it's been proven for 4^3, but I don't know of any larger results). Do you know anything more about this group, like whether it has been named or studied? Since G's structure is very similar to a symmetric group (or more accurately the direct product of two symmetric groups), it allows to describe the centralizer of an element in G. The more a group differs from a symmetric group the less this analysis helps (for those that know what I'm talking about: the more a group differs from the symmetric group, the worse a backtrack computation using cycle structure analysis is). But no, G's structure is actually similar to the direct product of two _wreathed_ symmetric groups. Does this interfere with the backtracking as much as it interferes with my manual analysis? Do you know of any good treatments of finding centralizers of outer automorphisms of wreath products? In particular, I would very much like to know under what conditions the centralizer of the wreath product fails to cover the centralizer of the permutation factor, as we saw with the corners. As for when I wrote M class Edge Corner Corner times edge (class size) F.P. F.P. / (96*class size) ^^^^^^^^^^^^^^^^^^^^^^ That's not a typo. I was just saying that column 4 is equal to column 2 times column 3, divided by column 1, divided by 96. Perhaps I should have factored column 1 out of columns 2 and 3 first to avoid this confusion. gap-3.4 -b -g 4m gap> Sum( ConjugacyClasses( M ), > c -> Size( Centralizer(G,Representative(c)) ) / 48 * Size(c) ); 901083404981813616 Well, call me John Henry. Say, do you have gap libraries for other magic polyhedra? For higher-dimensional magic? Dan Hoey Hoey@AIC.NRL.Navy.MIl From BRYAN@wvnvm.wvnet.edu Tue Nov 8 21:23:01 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA18863; Tue, 8 Nov 94 21:23:01 EST Message-Id: <9411090223.AA18863@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5643; Tue, 08 Nov 94 21:22:42 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 1945; Tue, 8 Nov 1994 21:22:42 -0500 X-Acknowledge-To: Date: Tue, 8 Nov 1994 21:22:37 -0500 (EST) From: "Jerry Bryan" To: Subject: Re: The real size of cube space In-Reply-To: Message of 11/08/94 at 01:18:00 from , Martin.Schoenert@math.rwth-aachen.de On 11/08/94 at 01:18:00 Martin.Schoenert@math.rwth-aachen.de said: >The way I view this is as follows. The entire cube group C is a >permutation group group on 6*9 points, generated by the six face turns U, >D, L, R, F, B; the three middle slice turns M_U, M_L, M_F; and the >reflection S. This group has a subgroup M of symmetries of the cube (of >order 48), generated by U M_U D', L M_L R', F M_F B', and S. Another >subgroup is G, generated by the six face turns, which has index 48 in G. >G is a normal divisor of C, G is the semidirect product of M and G. The >same is true for GE and GC. I have discussed a similar view of things recently, except that I was not brave enough to include a reflection in the generators. C is normally used to denote the set of twenty-four rotations of the cube (a sub-group of M), so let's call your "entire cube group" big_G instead. My version of big_G was generated by Q plus the slice moves (like yours without the reflection), or alternatively by Q plus C. Your version of big_G is hence the same as the one I discussed except that you added a reflection. C (the rotations C, that is) is a sub-group of both versions of big_G. M is a sub-group of your version of big_G, but not of mine. Your big_G has the obvious advantage of including M as a sub-group. Mine has the advantage (?) of being physically realizable on a real cube. That is, for X in your big_G, rX or Xr (r is a reflection) is also in your big_G. For X in my big_G, rX or Xr is not in big_G, and correspondingly a single reflection is not physically realizable on a real cube. Of course, r'Xr is in big_G in either case, r being in M. Also, cX and Xc are in either version of big_G for all c in C. I tend to think that Singmaster's standard G= is not what people think of when they hold a real cube in their hand. Rather, they tend to think of big_G/C. That is, the cosets of C in big_G are common sensically considered to be equivalent because rotating a real cube in space is "doing nothing". Also, for my version of big_G we have |big_G/C| = |G|. For either version of big_G, we have to re-interpret parity arguments slightly. In Singmaster's G=, we say that even corners occur only with even edges and vice versa. In big_G, a face quarter-turn is odd on the corners and edges, and a slice quarter-turn is odd on the edges and on the centers. Hence, you can have odd corners with even edges and vice versa, but only if the centers are simultaneously odd. Therefore, the rules concerning which configurations of edges and corners can occur together are really preserved, even in big_G. Finally, neither version of big_G is as big as you can go. That is, neither of them includes Singmaster's Supergroup, where different orientations of the otherwise fixed face centers are considered. Also, neither one of them considers Dan Hoey's Eccentric Slabism, wherein invisible inner cubes are considered. > Note that the elements of M are also a autmorphisms of the Cayley >graph. That means that elements of M respects the length of operations. >That is if g_1 and g_2 are elements of G that are in one conjugacy class >under M, then the lenght of the shortest process effecting them is equal. >This follows from the fact that M fixes the set of the generators of G >and their inverses. M is fact the largest subgroup of the outer >autmorphism group with this property, which makes it rather important. This of course is the basis for the large searches I have been able to perform using M-conjugate classes. The only trouble is, I don't even know what a Cayley graph is (but I am working on it), the last course I took in group theory being 25 years ago. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From devo@vnet.ibm.com Wed Nov 9 13:42:09 1994 Return-Path: Received: from VNET.IBM.COM by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA08633; Wed, 9 Nov 94 13:42:09 EST Message-Id: <9411091842.AA08633@life.ai.mit.edu> Received: from GDLVM7 by VNET.IBM.COM (IBM VM SMTP V2R2) with BSMTP id 1936; Wed, 09 Nov 94 13:18:09 EST Date: Wed, 9 Nov 94 13:18:13 EST From: "Dave Eaton" To: cube-lovers@life.ai.mit.edu Subject: Re: Is there a symbolic cube program? In response to my request for a algebraic cube simulator, I have found out about the following: Rubik Algebra, a $10 shareware DOS program that displays a color picture of the cube on the left and a list of choices (rotate a face, library of moves, scramble) on the right. It accepts a text string of moves similar to Singmaster notation and displays the resulting cube in 3D. There is an option that will tell you the cycle decomposition of the current state. So, this program provides the function I requested and I will have to play with it to see if the graphical cube and menus make this too hard to use. Nonetheless, my brief trial of the program suggests that this is a good, straightforward tool to fiddle with and analyze the cube. This was mentioned by Warut Roonguthai . Maple and X-Maple were suggested as symbolic algebra programs that could handle this type of task, but I have no further understanding of these to know how slick they would be. This was mentioned by Brett Stevens . There are surely other symbolic algebra programs, but I don't know of them. Roll-your-own, the approach I (we all?) should use. I think we could build a suite of text-based tools written in "standard" portable C, that allows for: - input of move sequences - display of cyclical decomposition - definition of compound moves that can be used just like a standard move - one-shot execution from the commandline or running move mode - find solution(s) from current state - randomize/scramble - other analysis of current state, like some of the mathematics and numbers that have been discussed in this newsgroup - other size and shape cubes? If folks want to do this, then I suggest that the eager and capable coders who dive in first ought to try real hard to make a system that can be driven from other programs (such as a windowing GUI display program with graphical cube). If for example the current state of the cube was stored in a file current.cub, then a program called cube could be called like "cube r2u3r2u" or "cube r2xr2" where 'x' is a defined move--defined by "cube define x rfr3f3" and that got stored in a file library.cub. The other functions could be separate programs (which read the same files): cubehome cuberand cubesolv If I wrote this, I would have a hard time using C instead of REXX. In the absence of finding exactly what I want, I will be experimenting with Rubik Algebra and deciding whether I ought to start writing something like the roll-your-own described above. Reply to this group if you know anything more. Thanks. Thanks for the pointers to this information and the encouragement to give it a shot myself. Maybe this would be a good task for my holidays and my little remaining vacation. If I do something, I'll let you know. ......Dave Eaton, N2NOQ, Owego NY, devo@vnet.ibm.com From bosch@smiteo.esd.sgi.com Wed Nov 9 14:16:56 1994 Return-Path: Received: from sgigate.sgi.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10908; Wed, 9 Nov 94 14:16:56 EST Received: from sgihub.corp.sgi.com by sgigate.sgi.com via ESMTP (940627.SGI.8.6.9/911001.SGI) id LAA17814; Wed, 9 Nov 1994 11:16:51 -0800 Received: from smiteo.esd.sgi.com by sgihub.corp.sgi.com via SMTP (940519.SGI.8.6.9/911001.SGI) id LAA07516; Wed, 9 Nov 1994 11:16:47 -0800 Received: by smiteo.esd.sgi.com (931110.SGI/940406.SGI.AUTO) for @sgihub.corp.sgi.com:cube-lovers@life.ai.mit.edu id AA05815; Wed, 9 Nov 94 11:16:32 -0800 From: "Derek Bosch" Message-Id: <9411091116.ZM5813@smiteo.esd.sgi.com> Date: Wed, 9 Nov 1994 11:16:32 -0800 In-Reply-To: "Dave Eaton" "Re: Is there a symbolic cube program?" (Nov 9, 1:18pm) References: <9411091842.AA08633@life.ai.mit.edu> X-Mailer: Z-Mail-SGI (3.0S.1026 26oct93 MediaMail) To: "Dave Eaton" , cube-lovers@life.ai.mit.edu Subject: Re: Is there a symbolic cube program? Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 I have a symbolic cube program, which I didn't write (written by raymond@cps.msu.edu). It does pretty much what you want, although I'm not too sure how portable it is. It was written in C, using yacc and flex (lex doesn't work on it tho, go figure.) I could post it to the group, or send it to individuals that wanted it. Derek -- Derek Bosch "Time flies like an arrow, (415) 390-2115 but fruit flies like bananas" bosch@sgi.com J. Blaylock From raymond@cps.msu.edu Wed Nov 9 15:28:24 1994 Return-Path: Received: from student3.cl.msu.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA15697; Wed, 9 Nov 94 15:28:24 EST Received: from via-annex2-45.cl.msu.edu by student3.cl.msu.edu (AIX 3.2/UCB 5.64/MSU-2.10) id AA33037; Wed, 9 Nov 1994 15:28:23 -0500 Date: Wed, 9 Nov 1994 15:28:23 -0500 Message-Id: <9411092028.AA33037@student3.cl.msu.edu> X-Sender: raymond1@studentr.msu.edu (Unverified) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: cube-lovers@ai.mit.edu From: raymond@cps.msu.edu (Carl Raymond) Subject: Re: Is there a symbolic cube program? X-Mailer: >I have a symbolic cube program, which I didn't write (written by >raymond@cps.msu.edu). It does pretty much what you want, although I'm >not too sure how portable it is. It was written in C, using yacc and flex (lex >doesn't work on it tho, go figure.) > >I could post it to the group, or send it to individuals that wanted it. > >Derek > > >-- >Derek Bosch "Time flies like an arrow, >(415) 390-2115 but fruit flies like bananas" >bosch@sgi.com J. Blaylock > I'd like a copy, please. I wrote it a while back, and now I can't find it anywhere! Maybe the Internet is turning into the ultimate backup system :-) Thanks, Carl From bosch@smiteo.esd.sgi.com Wed Nov 9 15:53:26 1994 Return-Path: Received: from sgigate.sgi.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA16494; Wed, 9 Nov 94 15:53:26 EST Received: from sgihub.corp.sgi.com by sgigate.sgi.com via ESMTP (940627.SGI.8.6.9/911001.SGI) for <@sgigate.sgi.com:cube-lovers@ai.mit.edu> id MAA02361; Wed, 9 Nov 1994 12:53:25 -0800 Received: from smiteo.esd.sgi.com by sgihub.corp.sgi.com via SMTP (940519.SGI.8.6.9/911001.SGI) for <@sgihub.corp.sgi.com:cube-lovers@ai.mit.edu> id MAA13262; Wed, 9 Nov 1994 12:53:23 -0800 Received: by smiteo.esd.sgi.com (931110.SGI/940406.SGI.AUTO) for @sgihub.corp.sgi.com:cube-lovers@ai.mit.edu id AA06009; Wed, 9 Nov 94 12:53:14 -0800 From: "Derek Bosch" Message-Id: <9411091253.ZM6007@smiteo.esd.sgi.com> Date: Wed, 9 Nov 1994 12:53:14 -0800 X-Mailer: Z-Mail-SGI (3.0S.1026 26oct93 MediaMail) To: cube-lovers@ai.mit.edu Subject: Symbolic cube program Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 Since I received many requests for it, here it is. It is a uuencoded, compressed, tar file. Derek -- cut here begin 644 cube.tar.Z M'YV03<*L*6,F#9LR`!(J7,BPH<.'$"-*G$@1`(R+-BZ"L!A#1HV,&R]>[!A2 MI$D:,FZ`@/&QADL8-&[4@+$RQHR+-0"LK,BSI\^?0`'4F4,GC!R+,,2\F3,& M35"';NK4&0/G:4.3&I&:W&BUJ]>O8,,&/8C'19X\+L:`T`&":1@W;LK(49#` M#-FV8][&G0L"A`*T1<6D70L"CM$YS38^J(*;.:<.[=GV4[5ON; MMVD%Q7WKYKW9=F_2JT$[WIR\>&_GFZ%O;L'DQ5`Y+^"4>0/GX`NE3-&\8)-& M3&0V=D\KZ#O?[]<'M43!``!D%16'$B@40$,7("&1``I!H-``"AG@B!^\X(&( M`;T0@`@*"Y#3X(,13M@+*X_TP`P\(8[(H80$*(''B1=F6"(\B`Q`!@Z(?,`` M+C&2`<0B;`C#08XXX%,""QXD-"`B,K0!`"(";,".6/AQP,$?_[B"BH(EP$*E ME0IN4A40.E#2DW5CB&7FF0Z)9`,--(34T4O:`" M"$3(D88=10]I<%^4 M]-33<4<:1&6_/5W>^Z`^^W1L(?[D(*"@.P\D_<`[82B800N*(KD2@&`&:OM= M7_2VP+V!``IR6=7U!&VN**NC@QA\ MIS4)YF]XRNL<\J*8!N8Y[VG0(QSEOF M;NN'*MC=[=RP0U;:\)6HDYT068>R5L80=7-((A.?ID(XY.$+Y$&!"9*PNMDA M\H/D.68R=V>".210:W=`@T%\A0(W^``&5^R+[:3F01.L!`]S"J?6:@=-#"ZE M#"C0(0BJN3H3T.&:Z\QG,:4)!V72H9GXS&<#!=I.%L*3GO,,YCSO^4RM[1.9 M_;1G/:W9T*=Y$&G>]$$,*JI(!C9R5$,@3QK*(+@.^NJ7K7K#WP;GAK%=+'8G MQ%D*HPG15?;REJ:#)0UMZK_$0I2G` MIR(_^L"N2;)PUZLD!SV(JP_F05>^:FGB%M\M,Y;"7BM'1K;Z:0USO,-<-H@%;*Q`!2R$C@A:(H*Q!7,)QA"X5ZG]9NQX;5N<%X?6D8$SAV M!HNM+H. MY36OO./,7W&/J[W)(6V]"?M9`L1I7O3V%VG]^A?WEBLU\K!1C2%`6AKZP@<^ M],7!<\QC?R.\$@'G,VARZ]C71(""$LQ!!,X-PU#=E\`$)$`-Y.,>'.'K8C;T M8*-T24`VMYD_%,`8P^#;@AJZ(#D.IT'``V9GB.FF6!.C&`1N4'$9A$QD&3?Q MO,<=,OX2W-X<:XT.*^@!AN?7OB%;^6EL8-Z9]>;B)8\X!7C+,9C%#`<\EOF- M"8A:_M0@2"03F`X]H$,)9'!FJ$G-8QP&IY?7">*NC9@*V&IQDO/)!A7T@-"+ M3N2BV9R`MKW-Q7\.=`EF4.C.'1H$B?8SHV,[MZ\!^L8@\)\($DN8QL89U`*M M=`](G>FG<;J!;78TV"(M8SUWT[\=7O1%129C3Y=!V?CKI@K8(+D7@.`,8R`# M"IH+Y1;GD\T#7:.IT,]B2T*N.;3`/=PLH")Q=7G4K=@LE($,7 M[N9!VV-;V+%=WNS;TEHAR6-MPI=8&'[A!G4&30P_:4(+GEKA!RLL[ M;A#L^"#Y:[FB/PP"F;NA!&VHZ'N3?G.AZIRCO]L8'>K`UV[ZFZI3@)@<2#B8M0S*4BYK$BBVJCJX@0RKDSK5W2!)N&50XZWJ5N?HH':* MB15X;H?[X*!@7QS41\-V?`E1MP=0:+PRWB8D_JVP=_]XZE M2N\;[)S@Y,[7,I#!!:XU&4_-[C(5%.3M7V`]"IIBE%E%>:B[Y"'K9P4'E6NM M84DXK:_$/F\,LM9_F6-P_EA?M(@A6VE,@_GA6];\HQ'^#K$'6K(P)%(`52\`12P!9#\!8GX#%AH(9%R"V!91ACH%:H4W;C MYP+QIG3SA@<;A`(M$`/GQTC*9U,'$7XN*#D^``+)HTXNB%PQT`7X147UU3GD170,2!XN$&0'UCF:>(QPD!ITI$Y'54!W8>0WROQ3EB5X7V MJ`([*()/TUT;B(,THX&HEHUY"%T;&(,?*'WV9F+X\V0=V'W-*%NT M!5:W90*YZ`.\%8KUP4@-,P5A@"KBZ(2"TU41YX*041!`UXZ0,0<;60;PV#*W M17NQ4T>)5UO$#%7=946)S1O(`9N9??E9=45(P3"#WO&9]P$)>0D6]/9@*_.4]Y8)YQ:6*&, M"8T:!HM($YQ-%V[Y1)#8Z(0VV'3\:'TWJ6E--)E7XY;^1IM;:)LS69.Z.5R\ MN3H1*J(.A86M6+U>9]FI9_\B5'^.7XV%:#R M-:!2I)?VI4[/HRII*I^"Z:#U%*$F,*$;6HT=BJ%(HZ$CBJC(Z)C2Z*,?M!S% M`BJ6ZA-JPB9NXA$@(2=TDBD7<0,Q0!,LP2=^DA*!,@.$0@,W@2B7^JI`X2A& M@122XA1@42E4$1:;4B=Q`JN^^JN@HCFPM3,]@T()=$I+-ENU15)PB%,XI`*\ M53.GY#ER`3I/I5LS5)^YA4NQXTS"RCG8I4K7RJVI0W)$1$N\M*T^U:W'"EL/ ME4SCNJ[EFJZ^A*TYU*ZI2B@V$+6N^K-4NQ"R"BE)L123UYYT`(RX`(Y(#ETP3E!$`0=00,Y0`/&@[>"Y[=Z MR[>)"[B"6P."FRVV-&`9X4!IM%;=S6[>=^[F5 M>[F9F[V<:P=I0#A3T`14``7Y@[JJZP)^^P*Q.[NU"QFWBQ,QL%%W:WJK`[Q[ MZT'#J[S%*[@TD;S+NS",Z[BH$KVJ,KUO.P?WFQ;9*[=U0+=D8+>>2[WG=;T0 M#+<23,%VBP(TX+XO(`=PH`8M@+K@9#RV&P2!@@,XP+OY^[M_V[\@,+SW*[@Q MH`.L:E:%V[P(#+G=^T%MY<`QL,':.\'<"\(B',*@.+\@4+\Q<`,XD`.]J[]] M.\/".R@W/"T%L83IL^W9` M\+9'[,$*T`0DA9)IU0+LQA8\D+ASXK62P=\5[?- MI+5H``2C*[X7Q`)--Q#0`@1ZD!=RX`)A,`>G-P>15[IM<%V-.%0D3,O<@@:K M836O7,$[U!2C2P9T<`9`$,S.0BQP,`;`#!NWW'1TH`9J``1H"Q_%XFFXL@9I MX`(%D41O@#B+S,&?I0!3H!MJT+AT@(C+T183HSY&X2L\:QI3D#A#P1:&>!I) MT!:JB8Z[X<]F`-!OU55E5P95`XE"MDWB$\RA(`1E)*!4)(71-)HJQM`1U>AA5EWP35O<`:F MPW`=)%2?NS--03`MT`+W=P8IJ0"$TU)TQS&(X7-&,7FFF=01QYGRDA=P(1=/ MEH05Y$'8IA9W$,]L0`99ZC'Z:KD'H0"8)X.9,1@E+3(R^$$;`XFGUQ=3L!D+ M/11Y:Q=[G=1M\+E0,`2:!W$7XT&FXP9TC84>8S$]?0:'E=8^9UCN5S$]#9J\ M<1I4@%E7"5@Z4!\!,1"<25!9!Q\M((/E\1:PTUI]028S6RJ/^\M]@03!/#AJ M>%F^0DECA=AOP59U<%Z*8YHT'=H:6!FMTI=9$`1#,`29!0)"D`13\`1.0!E6 MDRKQY%(^QRIK0#OOV5<32)-84-U&@-YXH1?>G=@@P-Y-\08#\=>DTD%:N@8M M97C9-*'UH0+%,K-/8P1N]T*71-3=PEKBH5`\I"^3MU4*58'>7!]'2!0NL#(3 M:`0\-C%^M1DBV5.P,P?R4=!&4=F81=1&K6)!K."41R[+\5A],=K!C;8ISG") MAW>,H3BH4E9"T#:;)'I4[4$RJ&+E<5(4DTVCE0?Q_$%\R[-E=064G;-+KN"^ MDGB")5>=\W:JE;<8IP"5RQ@D558AU09#U3'F"-Q9#@>(LUBD@SAJ[C'=]'YZ M]]!4;GZ#,]$>U#"T0AEI8#6G71]2`%T-0P5S5W1I@-EC!^:#%P=U4.*?5^B3 M.09K,$:^DCDH0'6=VRIDT"J2*SF7+@<40W7NL>FC#NJ2`P);0`.PV#!MDG@1 MQRJ;U9D1)]R6E-294Q]5$.A/TS!54#&%OBJ.R$F0<<%2X.M\Y7&7'NHNHQN9 M#@*;OL`@0'6>3G7*KNRE7NIFD`)0_>FSLP)]L06C6@-=0%4R#@+>GH10_7!I M8(2^,@17P.;3_>XJ5'IY]U=Q1U+B8>"HP@:?>^M]D>LHD.LI4(O1-2JYGCLM M0X3"'L34VMV=F>L>QVZJ]6[IYYK.)P(5SG$?CE*"DSEJ M\`:^LD>8+@::SNGVF3_4'NUR<.W.;NK?KNH*H!3NH?+*'NWNL?(MO\#3;NK> M?NGP$>UL\/,S7_/8KNW?'N[C/N@OY2O91=)K#>(R])%$]-7;!%PHS^8Z7U;^ M#@(G[RLZW_'W/7AEC_#!GK<73#@ZC^QUT//,CNF;[NF2F^E#3S&DCO36+O-- M_^TW,>[U8012(`1-HP#)+O,^C_3FA?>:SOQSP0' M!+R*LX21`=7K\]L/+0:,L0:#HS*/XC&9(_'NQEH5CY(YM_MH?P2/.W@NV'"[ M[W'2'VUSS_AU[S)V`?G.+OF=ZS)D8/DMG_F>O_I&W^VAW^WEE?J@[NQ)S_2H MK_J@C^JT[_JK211H;PH,%M_F,D8>MBIY)D/%\3SP]_/$'[71+Y'/_IV_RM?L M[E[H`CQNC0_HU3RA=P$UX-';@#"P[Y4^IX?JH%[T2TG8(N/%KHT7 M`)&@]/-Z9:"Q=:[/E.4J!DFA`TN07G@:1@Q,$5;\[9L0]? M5M-.`P3)*L.-[MRYP")#\E9O(QS)(X@-"J,@Q\I*N2L(T*SH_+C(PY&`FP)H M0FNHUGD0#@X@+64Y8L#OA8U[8B@)`'8[IWB&W MZZ=W9MVS&`-LI1$9D4DDZS#+*00KEO#$_4*V,M=T!S'D<(3C&`*=Q/.\*DC> MP2R]#G54'&<8!4W-X(`#Y6'=O8946-TB#A.XA:VBV''#LH("LHZO0`(3@RA$ MC",D!PS.G5,<$*D*?@$]5A1V1N3)"RY#QNV,.?`%,HL]HSP#D1[:PR_P!2U+ M4I,"NB$-K`%[&!#^H:M8#E_`!9RZ'BSBLL&TI`+1E>)XB9J&$:ZNL&`'4,>_V@D*QAAB# M;STTP@$#]M?J0!TR8'7,NY:60=X.Y:%K'L[QT)'5X>[\"OV0@O'.+EJXO@#E M5AK)6X3MI"3&!;@SV=0*>V@K;,XQ`1;%PWBDX,:H8)-(9[P!R#`H4$<:A`PS M(*E($J1('DP%)+)I"ZVOL0>F$@9-7.(9:'6@S"5"H9A37DI;&`ATH"D$)V^H MY.P6%D(5+"4/*(`V2!06AT))`B?@MSF+SZ5WWL()JHU8C(D#MLEBYJ6,&VL5I2$1R@`W(A],PXY)%,`2)SY!B;)"6 MN--@(C+L:!2#;_DKG"CB^);I22N%P2=V0[`H%`D'401)5Y$S*D4PR!2=XL59 MA8U+*E+%8N@KL"):Z`M;L55T150&%.5"6/0@8W$EF,7JEA:A26JJ7&WK+>J= MEJ(7_XFK>'>Y$-[51PX`2TP[@O"^-4.HR39/(H1,$:,QLCF'N-4 MR%N74155MR"9&0?'9B1J`S*T*8#0"#%&(TF+^'`^O><],:-*%O]85!<4#@ M1MZS"Q/P\JV3-@$"_A8(R!,@X`;`#3)@_M+?#EPG.*`OY("^11/N%]R(>9P/ MZ2D]]T`2;$+?:A-^:U?6/]5G_VA>(>M;*B$&!,O#E7IPP\JJ6%,F>8"HH"(" MYMZ3*9=LX%SJ!G5)G7"9UA`!DNMO"#)S+3;8OQ<"^O)?O MDMJI2_@P,/UE(!)U*`9?EKY]23`#T28SF-B"U.&51>([&@81&!BP\`^VF]7B M%.U5YAA8J&.A]8"@$C3*8M]:'1VR2-*`U5$#5H<-6!TW8'7@@-61`_:7R;Q? M^ZM#VH3]M3*OV/YZF=AR?\W,OI4#^H"[Q"(:,FF:S*6Y.IBFTFR:JR-I2DV3 M.36C)M6\FE;3:G84E6,Q,>:3]!5Y@AN^2`3HY?J5O>IU(Y/`!(T8@#)71Y$T MF3VS9=Y*F"DS::;-W%]LLV\5R1C0,_U6SOR9^RMF]JVA>;@6R=$D,$XS<4+- MI\DXJV9?P)J/,VM&SLDY-='/`O$=(+-55)RTR4Y*YH9,F:LC;KI,NMFW\N;0 MK)G$\F_J39Y9QO87ZBQD@5-H&L[?X3D9I^)LG+?3<>I.R+D[+2?%/`V9,[Y- M#I*9-.4FZ`0!/?-UDLZA"31'%=Y4G5%L?^U-N0D[!R?K))I&DW8FS;QY._,F M]UR<>7-W1LT.>3(I)]4,G^03!O0!OW`Y@:?9)%?%CG,&C=J9-SNDX"R2V MION,0O[*"`Q/M>D_R^?Q')HF$V@*3KGY.F^F]VR>.K-O4D\"NC<)9]$\G.SD M=LK0Q=E`*2CYA*`4%'U24/5YD3#G^Y170F"#=L[M.3H/2.ADF7=3%=7-&D8Z M<6;?TIDM]'I6S^A)-,O8`46:,Q1WTM`M:CYMZ`/=H5]T55I0^MDVW)1!KHXB6A?P*&44X*"T3]J M0KCL:0[EH%LV= M$32,ZDX=:CX+:?`,HBA%3E9*-%$G-Q6%'PJT#[Z/1UG^`2D4E.0=E%":DT-J;K"(8F4>#)2)6I$0<`C M3:.1E(GV3RD/Q2%!M&H@ MAJ.P3!5%*[V3K]13#0I>!0-V*4S0$Z;*:0D*0O$19(`O;:F,(IAFK?30*(OI MUQ);DA*H*E5+50+V`%4I`KL"&)(!2"0X:)UO)!T>!"*6Q(DH.(9`/\L<#6,( M*(%B=^O0A;5@%L%B6$B+=W%6L44J-1=L=5R(@')Q+I)%6Y47EPBN*H!K)!<\ MRTG](55@=1"!U<$$5H<46!U&8'4(`=]1`C#2J)!DNHS-6;4!8CAPA3"D\S040`GH%I&U"GP!*E`V M2,5LK:U,X+8N`1`@!71KP?"M0L"W,@'L1@5\ZQ0(`E:@"`C7)Q`$B(!OC0)5 M(`D45]JZ!%PK;.48/.!4-*)4E`2@1TJP,1&VZ`LEX/R^HR,*O'>:UY0#S\"O*0BL0F;`M2 M;-"!'(',-([J4:TP,@!RQ:85N+BBV0;;63MDA*)%'+F.90O7E*"`EI/!ENZ[%* MU+&%2,HDU,:`4;MLH^QP+5R^M=IJSY`U?N11F66VR%6YHMC")07H:[PEMMKS M9*DDD15J94"[1;/QC;F>V-K*;_TMBI6W?8H(18R457#/#[T=&O:6SIY9"P-= MI>N_M;8$AANEL%B+WY4KL:@;_>V+QRJLOEK58O@8`L- M0ZQH$].$@B:0A9&'1T@U"@Z@2U142Z,"`;Z#,[$%HBMTM>R$K;`?AXBX7+3% M:!C6*]Y\W)_62:Z2`K@(`D.<1MHUVT#LEC?=FXH*W2[;M\=0+U]>$"W#XE<"FNH#VX-%;A^MU^ M"W@_[KQ]38;7X%:4N\N2\J[&M;/E32XL5;'P4H=63#4)L13TUH`;H*IJJ4XM MO7_"(_S4S6LFA&JM*JI>"U(>TZ3*>FOOFLQUV85;GJ'/3JM]N%9&<@6F`*H#`5R`#IR-+K`"%$!T M]:ZH#@:T@!S`?>W9>76VJ&YZZ($NL`74K_@EORK@Z9Z&7D=08DX/JCH9MFQD M6050<>KO>?)!"W<)[%_>YW^YT;/=O\6N`-_?\--;J>O^U:`*&#W!/MVZ?X-H M!/9!P=4!&]G+T'Y6C0$FKA1X`PM:+;J%0@'C;,PA.\%AD,:$2LV+>$FS%".[O^M.ECX M`!\J1L(%1,`6\`)M>/NJ@#9,8!"0,;$IP(D)7Z,5`(H.53X14ER8NL"N\2&+ M:)$?7B=<.+5Z86?!?YS%(?X^+;CA-EX-;(:K\!ZHOD"X3P&?,]!2WLJ>J[/T MH:P(%/LK@<\"&=X",*#*H!_76F'A;0QF)"/X!OL@$QR"5[$*)L$M^`4WUUJ< MB4\#H[/!?8H;Y6!>S(-]<"9F)XDX^=HJV_L4.N^;Z%2@=Z:"JCFQ4TVOH$2] M-R%YK%YF[!5<[S#]"KCJ47J%2'E,N;$Y#A6C`NN:H1I"=2I=K3"H<6C\!)7A MU(KNA''J"YZU1=$KE5&//!`(LJ;T`0V?WTY+B?L2&W;#<%@$R&$ZS$[L\%$Y M&7F8#/-A"B50`+$0%L0R@!#/HEI4B9]&(B;")Z,1[QP!!XDEL"0.O"BX(S.2 M2SP%CC&!V<2=V!U#V76B`$0Q+B[%>O@#H6)5S$@HK#W3P2(8"?%I MN,5#.?SHX@"\@^D##0;&2%,81U>@+(.=<@_.L\=X"PMA.W".N[)7_LI@.2R+ MY;%,ELNR63[+:#DMJ^6US);;LEM^RW`Y+LOEN4R7Z[)=OLMX.2_KY;W,E_NR M7_[+@#DP"^;!3)@+LV$^S(@Y,2OFQ Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA03006; Thu, 10 Nov 94 08:43:46 EST Received: by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA22346; Thu, 10 Nov 94 08:43:35 EST Date: Thu, 10 Nov 94 08:43:35 EST From: hoey@aic.nrl.navy.mil (Dan Hoey) Message-Id: <9411101343.AA22346@Sun0.AIC.NRL.Navy.Mil> To: "Derek Bosch" Cc: cube-lovers@life.ai.mit.edu Subject: Re: Symbolic cube program > Since I received many requests for it, here it is. It is a > uuencoded, compressed, tar file. The cube lovers archives contain over two megabytes of readable discussions on the cube. In the interests of keeping them readable, I ask that binary files and programs be distributed using some other channel: private email, ftp, web, or whatever. Please let Cube-Lovers remain a _discussion_ list for cube topics. I am aware that alternative distribution methods are not supplied by Alan Bawden in his maintenance of the Cube-Lovers list and archives. Please consider that encouragement to provide such methods, rather than an excuse to use this list for the purpose. I am also aware that the recent program was not much larger than some of the discussion articles on the list. Nonetheless, it does not contribute to the discussion, and imposes a burden on those of us who subscribe for the discussion. The revised versions and larger programs to follow would impose a growing burden on the list. Dan Hoey Hoey@AIC.NRL.Navy.Mil From @mail.uunet.ca:mark.longridge@canrem.com Fri Nov 11 16:55:11 1994 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 AA08434; Fri, 11 Nov 94 16:55:11 EST Received: from portnoy.canrem.com ([198.133.42.251]) by mail.uunet.ca with SMTP id <86964-5>; Fri, 11 Nov 1994 16:54:37 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA18346; Fri, 11 Nov 94 16:51:10 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1BE0A3; Fri, 11 Nov 94 16:43:17 -0400 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Searches From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.858.5834.0C1BE0A3@canrem.com> Date: Fri, 11 Nov 1994 15:36:00 -0500 Organization: CRS Online (Toronto, Ontario) Jerry asks, in his message of Sun, 6 Nov 1994 09:15:37 (EST): >This is not a shift invariance question, but rather two >questions about your searches. One question is, do you perform >separate searches for q-turns and h-turns, or only for h-turns? The group searches are q-turns only, but if I see a way to compress it a bit by eye I do so. For example: UR2 = U3 R3 U3 R2 U1 R1 U1 R3 U3 R1 U1 (R1 U3)^2 R3 U3 ...was reduced to UR2 = U2 R3 U3 R2 U1 R1 U1 R3 U3 R1 U1 (R1 U3)^2 R3 > The second question is, how on earth do you keep track > of all those processes in your searches? With the computer hardware I'm using (486-DX40 with 4 megs) and my current algorithm I created a file "ur.dat" which is a flat ascii file. It contains all the processes which generate distinct positions up to 12 q turns. I also have the file "ursum.is" which contains all the `cubesums' for each element of . My program "x3bin.exe" loads the "ursum.is" database into memory and it does a binary search on the cubesums to try and find a match for the current position. If not found, it turns the current cube and tries again, with longer and longer sequences until a match is found. Using this method I have found a process for all positions with the longest being 22 q turns (so far). The hardest positions can take as long as a couple of hours. I have no idea what the antipodes look like at this time, but I'll probably try the random approach soon. Jerry continues: >p183 6 Twist R1 U3 R2 U3 R1 D3 U3 R1 U3 R3 D2 R3 U3 R1 D3 U3 > (18 q or 16 h moves) ^^^^^^^^^^^^^^^^^^^^^ This process was found using the Kociemba algorithm in a program written by Dik Winter, which I ran on a Sun4. This program uses h turns in it's searches and uses all 6 generators. After inspecting the original process found by the program, I was able to manually reduce it somewhat, resulting in p183 above. The original process.... Solution (13+ 4=17): R1 U1 D1 R3 U1 R1 D2 R1 U1 R3 U1 D1 R3 U1 R2 U1 R2 That is (or as Dan would say i.e.) 13 h turns in phase 1 and 4 turns in phase 2. Hmmm, looks like I used the inverse of the original. Jerry Continues: >I have been asked how I search >so many positions. I have answered the question before, but I guess >another part of the answer that I haven't mentioned is that I don't >keep up with processes at all, only positions. If I am asked to provide >processes, I can do so, but it is a very painful task. I have thought >about keeping up with processes, but I am quite sure that if I did >so it would reduce the number of positions I could search. Well, that explains the fact you counted the number of antipodes but had no processes for them, but do you know what they look like? If you can tell me what one of the 87 positions at 25 q turns looks like, I should be able to generate a sequence for it. -> Mark <- Email: mark.longridge@canrem.com From BRYAN@wvnvm.wvnet.edu Sat Nov 12 00:59:49 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA27349; Sat, 12 Nov 94 00:59:49 EST Message-Id: <9411120559.AA27349@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 3454; Fri, 11 Nov 94 21:04:46 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 0011; Fri, 11 Nov 1994 21:04:46 -0500 X-Acknowledge-To: Date: Fri, 11 Nov 1994 21:04:45 -0500 (EST) From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: Searches In-Reply-To: Message of 11/11/94 at 15:36:00 from mark.longridge@canrem.com On 11/11/94 at 15:36:00 mark.longridge@canrem.com said: > Well, that explains the fact you counted the number of antipodes but >had no processes for them, but do you know what they look like? >If you can tell me what one of the 87 positions at 25 q turns >looks like, I should be able to generate a sequence for it. The 87 positions correspond to 27 antipodes which are unique up to W-conjugacy. Here they are: ----------------------------------------------------- BRL BRL BRU BBU BBU BBF LBF RBF LBR UDR FDU UBD BUU BUU DUU FUB FUR UUF FRD RFR DRU URD RFB URL FRB LFD RLB LLL FFF RRB LLL FFF RRB LLL FFU RRR LLL FFB RLU LLL FFD RLU LLL FFF UBR DDU DDB DDR DDU DDU DDU DDB DDB DDB ----------------------------------------------------------- BRU BRR BBU BBF BBU BBF DBR BBB FBD FDU RDL LUB UUB FUB UUU BUR RUL LUF RBR DFB URF URU FFF URU ULU BFD RRR LLL FFU LRR LLL FFU LRR LLL FFB RRR LLL FFL BRL LLL FFR BBF LLL FFU RRR DDU DDD DDF DDU DDU DDD DDF DDD DDB -------------------------------------------------------- BRR BLU BRB BBU BBU BBU LBD RBF FBF UDB DUR UFD UUF FUD DUU UUR BUU UUR FRB LFF DRR FRR DFR BRU RRL FLB URR LLL FFB RRB LLL FFB RRR LLL FFU FRB LLL FFU RLB LLL FFU LBL LLL FFB URR DDF DDB DDL DDU DDU DDB DDU DDF DDD -------------------------------------------------------- BFR BRR BRL BBF BBU BBU FBR UBU DBF LUB FFF FFR UUU DUU DUU RBR BBB DBR ULD BRU FRU LRL URU RRR RRB RRB URU LLL FFU BRR LLL FFU BRF LLL FFU BRF LLL FFB URF LLL FFR BLF LLL FFU LLF DDL DDD DDB DDD DDU DDU DDD DDD DDU -------------------------------------------------------- BRR BRF BRF BBU BBU BBU UBU FBF FBF FFF RDR RDR UUU FUU FUU BBB DBR BBR LRL URU RLR DRB RRB URU DRR DRB URU LLL FFU BRF LLL FFU BRL LLL FFU BRL LLL FFR BRF LLL FFU LFU LLL FFL BFU DDD DDB DDU DDD DDU DDU DDD DDL DDL -------------------------------------------------------- BRF BRR BRR BBU BBU BBU DBL UBR FBD RFU FFB RDB UUD DUU FUU RBR RBF UBL BRF DRB URB LRD BRR UBU DRB LRF URR LLL FFU BRL LLL FFU RRL LLL FFU FRB LLL FFU RFU LLL FFB UFF LLL FFR ULU DDF DDL DDB DDU DDU DDU DDL DDD DDF -------------------------------------------------------- BRB BRU BRU BBU BBU BBU FBL RBF BBR RDF BFR UUU FUU DUU DUF UBB FBU UBD DRF RRL URU DRD RRL FLU LRL FRR FRF LLL FFU FRB LLL FFU FRB LLL FFU FRB LLL FFD RLU LLL FFB URR LLL FFD RLR DDB DDL DDB DDU DDU DDU DDR DDB DDB -------------------------------------------------------- BRB BFB BRD BBU BBF BBU UBU UBD LBF BUF RUR UBR DUF DUU DUU UBU UBR UFR RRB LRL FRR FRL FRB URF FRB LRB URU LLL FFU FRB LLL FFU LRR LLL FFU FRB LLL FFF RLR LLL FFB UBR LLL FFD RLR DDD DDL DDB DDU DDU DDU DDD DDD DDF -------------------------------------------------------- BFD BFF BFR BBF BBF BBF BBB UBF LBR RUL FUR UUD UUU UUU UUU RUL BUR UUD URU FBF ULU LRL UBB ULU FRB LBR FLB LLL FFB RRR LLL FFB RRR LLL FFB RRR LLL FFD RRR LLL FFB DRD LLL FFR FRB DDB DDR DDU DDD DDD DDD DDF DDR DDU = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From BRYAN@wvnvm.wvnet.edu Sat Nov 12 01:48:27 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA28036; Sat, 12 Nov 94 01:48:27 EST Message-Id: <9411120648.AA28036@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 3576; Fri, 11 Nov 94 22:06:56 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 0554; Fri, 11 Nov 1994 22:06:55 -0500 X-Acknowledge-To: Date: Fri, 11 Nov 1994 22:06:49 -0500 (EST) From: "Jerry Bryan" To: Subject: Re: Searches In-Reply-To: Message of 11/11/94 at 15:36:00 from mark.longridge@canrem.com On 11/11/94 at 15:36:00 mark.longridge@canrem.com said: > With the computer hardware I'm using (486-DX40 with 4 megs) and >my current algorithm I created a file "ur.dat" which is a flat >ascii file. It contains all the processes which generate distinct >positions up to 12 q turns. I also have the file "ursum.is" which >contains all the `cubesums' for each element of . I have considered keeping a file of processes, either in parallel with my file of positions, or together in the same file. However, I have always rejected the idea because it would take too much storage for the very large searches I want to accomplish. Also, since I only store representative elements of equivalent classes in my data base, it is hard to know what a "process" means (see below). > Using this method I have found a process for all positions >with the longest being 22 q turns (so far). The hardest positions >can take as long as a couple of hours. I have no idea what the >antipodes look like at this time, but I'll probably try the >random approach soon. Interesting approach, and very different than what I do. I simply do a "game theory" type tree search of positions (*not* processes) with Start at the root of the tree. I have to search the whole depth of the tree rather than half the depth of the tree, as you do. (I could obviously verify the depth of one particular position with two half-depth searches, but I confess I have never been very interested in "particular positions". I want to search the whole tree.) I tend to think of the processing required for whole tree searches as "global" because you cannot determine anything about one particular position except in the context of the other positions down to the same level of the tree. By contrast, there is some interesting processing that you can do that is "local"; e.g., conjugate class sizes, symmetry group determination, etc. can be determined on a position by position basis without regard to any other position. Such "local" processing is generally much easier than the "global" processing. "Local" processing is O( N ) and requires essentially no memory. "Global" processing is O( N log(N) ) if you are efficient, maybe O(N^2) if you are not, and is very consumptive of memory. As I have said before, I solve the memory problem by externalizing the data to files and sorting the files. Saying that I have a hard time converting positions into processes doesn't mean that I cannot do so. The process for a given position can be extracted from a data base of positions by backtracking from the position back to Start. However, I have two difficulties. One is that I store only representative elements of equivalence classes (of the form {m'Xmc} for centerless cubes, or M-conjugate classes of the form {m'Xm} for cubes with centers)}. That means that as you backtrack, the process you are determining (backwards) will rotate and reflect out from under you. For example, suppose we have Repr{m'Xm}=f'Xf for some fixed f in M. If Xq for some q in Q is a neighbor of X which is one move closer to Start than X, then we might have Repr{m'(Xq)m}=g'(Xq)g for some fixed g in M. But f and g need not be, and usually aren't, the same. It might be noted in passing that there is duality between the symmetry of a position X and a process P=p1 p2 ... pn which produces X. That is, if f is a fixed element of M, then we have f'Xf = f'Pf = f'(p1)f f'(p2)f ... f'(pn)f. The second problem is that my files are so large that I have to keep them on magnetic tape. If I need to find a process, I first find a sequence of positions (really, a sequence of representative elements) on the tapes (hard to search tapes!), and copy the positions to a small disk file. From that point, it is not especially hard to run a program to display the positions in sequence and determine the process. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From BECK@vax88a.pica.army.mil Mon Nov 14 08:36:10 1994 Return-Path: Received: from VAX88A.PICA.ARMY.MIL by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AB08495; Mon, 14 Nov 94 08:36:10 EST Date: Mon, 14 Nov 1994 8:03:53 -0500 (EST) From: BECK@vax88a.pica.army.mil To: Cube-Lovers@ai.mit.edu Message-Id: <941114080353.20200253@LCSS.PICA.ARMY.MIL> Subject: SYMBOLIC PROGRAMS I have an article that discusses a Rubik's cube learning program written in GPS. I do not have the program. ref: A PROGRAM THAT LEARNS TO SOLVE RUBIK'S CUBE RICHARD KORF DEPT OF COMPUTER SCIENCE CARNEGIE-MELLON PITT, PA 15213 DTIS : ARPA ORDER 3597 AF AVIONICS LAB CONTRACT F33615-81-K-1539 From devo@vnet.ibm.com Mon Nov 14 09:03:16 1994 Return-Path: Received: from VNET.IBM.COM by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AB08937; Mon, 14 Nov 94 09:03:16 EST Message-Id: <9411141403.AB08937@life.ai.mit.edu> Received: from GDLVM7 by VNET.IBM.COM (IBM VM SMTP V2R2) with BSMTP id 7026; Mon, 14 Nov 94 09:02:35 EST Date: Mon, 14 Nov 94 08:48:00 EST From: "Dave Eaton" To: cube-lovers@life.ai.mit.edu Subject: SYMBOLIC PROGRAMS I couldn't quickly get a LEX or FLEX working to process the source of the symbolic cube program written by Carl Raymond (raymond@cps.msu.edu). Carl's note said "do what you want...", so, I did. I managed to convert his C-and-LEX cube program into REXX. You type in a move sequence and it displays the resulting cycle structure. Exactly what I have always wanted. I am still testing it and working the bugs out, but now I can return to my "cube research" (that is, playing around). If anyone else needs such a straightforward text-mode cube program in REXX (instead of C), let me know and I will share it with you... after a little more testing. (Contact me directly, not in this group.) Interpreted REXX is built in on OS/2, VM, MVS, and is available (somewhere) for Unix systems, Amiga, and probably others. A million thanks to Carl. ......Dave Eaton, N2NOQ, Owego NY, devo@vnet.ibm.com From @mail.uunet.ca:mark.longridge@canrem.com Mon Nov 14 13:19:32 1994 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 AB22888; Mon, 14 Nov 94 13:19:32 EST Received: from portnoy.canrem.com ([198.133.42.251]) by mail.uunet.ca with SMTP id <86597-3>; Mon, 14 Nov 1994 13:19:59 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA27347; Mon, 14 Nov 94 13:15:56 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1BE7A7; Mon, 14 Nov 94 13:09:23 -0400 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Antipode! From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.864.5834.0C1BE7A7@canrem.com> Date: Mon, 14 Nov 1994 11:59:00 -0500 Organization: CRS Online (Toronto, Ontario) With Jerry's help I have found a process for one of the antipodes! Note the number of turns required in the h turn metric. I applied the turn R1 to the position so the program only needed to search 24 q turns deep. First Antipodal Process (25 q, 20 q) UR13 = U2 R1 U3 R2 U3 R2 U3 R1 U2 R3 U1 R3 U3 R1 U1 R2 U1 R3 U1 R3 Also.... UR13 ^ 2 = I Using current techniques, this required a run of about 11 hours. It remains to be seen how the Kociemba algorithm resolves this position, and I will try this next. Although somewhat unrelated, I found a square's group process for 6 X order 2 (the pons asinorum) by hand, which does not move the centres: U2 B2 L2 U2 D2 L2 F2 T2 F2 U2 L2 F2 B2 L2 D2 F2 (16 h, 32 q) -> Mark <- email: mark.longridge@canrem.com From BRYAN@wvnvm.wvnet.edu Mon Nov 14 15:28:55 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA00620; Mon, 14 Nov 94 15:28:55 EST Message-Id: <9411142028.AA00620@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 1855; Mon, 14 Nov 94 15:05:14 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 9387; Mon, 14 Nov 1994 15:05:13 -0500 X-Acknowledge-To: Date: Mon, 14 Nov 1994 15:05:12 -0500 (EST) From: "Jerry Bryan" To: Subject: Re: Antipode! In-Reply-To: Message of 11/14/94 at 11:59:00 from mark.longridge@canrem.com Of the 54 antipodes under Q+H processing, only 16 are unique up to W-conjugacy, with all 16 antipodes being 20 q+h moves from Start. Also, there is only one cube position which is both one of the 27 antipodes under Q (25 moves from Start) and also one of the 16 antipodes under Q+H (20 moves from Start). Just for completeness, here are the 16 Q+H antipodes. BBR BBB BBL BBB BBB BBB FBU LBD RBU RUR BUB BUR UUU UUU UUU RUU RUU DUF DLU FFL FRB ULU FFL FRR DLR FFR URB LLL FFF RRR LLL FFF RRR LLL FFF RRR LLL FFU LRD LLL FFD FRU LLL FFL URU DDB DDR DDF DDD DDD DDD DDB DDR DDB ---------------------------------------------------- BBD BBU BBR BBB BBB BBB LBR LBR RBB UUF UUB UUL UUU UUU UUU BUR BUR LUR FLL UFU FRD FLL UFD BRU BLF UFF DRU LLL FFF RRR LLL FFF RRR LLL FFF RRR LLL FFR URB LLL FFR DRF LLL FFU RRD DDB DDF DDF DDD DDD DDD DDR DDR DDB ---------------------------------------------------- BBL BBR BBU BBB BBB BBB RBR LBU FBB BUU BUR RUR UUU UUU UUU LUB LUF FUR DLF UFU RRF ULF UFR URB DLU LFU FRD LLL FFF RRR LLL FFF RRR LLL FFF RRR LLL FFD FRU LLL FFD FRD LLL FFL BRR DDR DDR DDU DDD DDD DDD DDB DDB DDB ---------------------------------------------------- BBF BFU BRB BBF BBD BBU FBR LBR BBR LUU UUD UFB UUU UUB DUU UUR LUF UBF ULB LFB URF FBU BLD RRB LRL FRR ULU LLL FFB RRR LLL FFU RRR LLL FFU BRF LLL FFR BRD LLL FFR FRR LLL FFF RRR DDD DDU DDD DDD DDF DDU DDR DDB DDD ---------------------------------------------------- BRL BRB BFB BBU BBU BBU DBF FBF FBD FFR RDR RUB DUU FUU UUF DBR UBB FDU RRB RRB URU DRL FRL URU DLU LRF RRR LLL FFU BRF LLL FFU FRB LLL FFB RRR LLL FFU LLF LLL FFR ULR LLL FFU LBU DDB DDB DDB DDU DDU DDU DDU DDD DDR --------------------------------------------------------- BFF BBU UBB LUU UUF BDR BLR DRF DRR LLL FFB RRR LLL FFU RBU DDF DDU DDL = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From dik@cwi.nl Mon Nov 14 17:41:11 1994 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA08291; Mon, 14 Nov 94 17:41:11 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Mon, 14 Nov 1994 23:41:02 +0100 Received: by boring.cwi.nl id AA02504 (5.65b/3.8/CWI-Amsterdam); Mon, 14 Nov 1994 23:41:00 +0100 Date: Mon, 14 Nov 1994 23:41:00 +0100 From: Dik.Winter@cwi.nl Message-Id: <9411142241.AA02504=dik@boring.cwi.nl> To: CRSO.Cube@canrem.com, cube-lovers@life.ai.mit.edu Subject: Re: Antipode! > First Antipodal Process (25 q, 20 q) > UR13 = U2 R1 U3 R2 U3 R2 U3 R1 U2 R3 U1 R3 U3 R1 U1 R2 U1 R3 U1 R3 > Also.... UR13 ^ 2 = I > Using current techniques, this required a run of about 11 hours. > It remains to be seen how the Kociemba algorithm resolves this > position, and I will try this next. You mean: F2 U3 D2 L3 D3 R1 U2 B2 R1 B2 R3 D1 L1 D3 R2 U1 D3 (or rather its inverse)? Took Kociemba's algorithm 10 minutes. I do not yet know whether this is minimal. From BRYAN@wvnvm.wvnet.edu Tue Nov 15 08:47:23 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA18861; Tue, 15 Nov 94 08:47:23 EST Message-Id: <9411151347.AA18861@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5519; Tue, 15 Nov 94 08:46:59 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 9202; Tue, 15 Nov 1994 08:47:00 -0500 X-Acknowledge-To: Date: Tue, 15 Nov 1994 08:46:59 -0500 (EST) From: "Jerry Bryan" To: Subject: Re: Antipode! In-Reply-To: Message of 11/14/94 at 23:41:00 from Dik.Winter@cwi.nl On 11/14/94 at 23:41:00 Dik.Winter@cwi.nl said: >You mean: F2 U3 D2 L3 D3 R1 U2 B2 R1 B2 R3 D1 L1 D3 R2 U1 D3 (or rather >its inverse)? Took Kociemba's algorithm 10 minutes. I do not yet >know whether this is minimal. Are you applying Kociemba's algorithm to the antipodal positions in the context of or in the context of G? The lengths of these antipodal positions are already known to be minimal in . However (and obviously), the length in can only be claimed to be an upper bound for the length in G without further testing in G. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From dik@cwi.nl Tue Nov 15 09:33:44 1994 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA20597; Tue, 15 Nov 94 09:33:44 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Tue, 15 Nov 1994 15:33:39 +0100 Received: by boring.cwi.nl id AA04373 (5.65b/3.8/CWI-Amsterdam); Tue, 15 Nov 1994 15:33:38 +0100 Date: Tue, 15 Nov 1994 15:33:38 +0100 From: Dik.Winter@cwi.nl Message-Id: <9411151433.AA04373=dik@boring.cwi.nl> To: BRYAN@wvnvm.wvnet.edu, cube-lovers@life.ai.mit.edu Subject: Re: Antipode! > On 11/14/94 at 23:41:00 Dik.Winter@cwi.nl said: > >You mean: F2 U3 D2 L3 D3 R1 U2 B2 R1 B2 R3 D1 L1 D3 R2 U1 D3 (or rather > >its inverse)? Took Kociemba's algorithm 10 minutes. I do not yet > >know whether this is minimal. > Are you applying Kociemba's algorithm to the antipodal positions > in the context of or in the context of G? In the context of G. I have no idea what Kociemba's algorithm in the context of should be; hence my question. dik From BRYAN@wvnvm.wvnet.edu Sun Nov 20 12:56:36 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA13248; Sun, 20 Nov 94 12:56:36 EST Message-Id: <9411201756.AA13248@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 2796; Sun, 20 Nov 94 12:56:30 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 7514; Sun, 20 Nov 1994 12:56:30 -0500 X-Acknowledge-To: Date: Sun, 20 Nov 1994 12:56:26 -0500 (EST) From: "Jerry Bryan" To: Cc: "Cube Lovers List" Subject: Re: Antipode In-Reply-To: Message of 11/14/94 at 13:54:31 from dlitwin@geoworks.com On 11/14/94 at 13:54:31 dlitwin@geoworks.com said: > Despite having read all of the archives, I still don't know what an >antipode is. I suspect I'd have to know more about group theory, but can >you briefly describe what one is (you may want to CC the cube-lovers list >as well, in case more don't understand the term). I guess the most limited definition is two points on the opposite sides of a sphere, at the ends of a diameter -- e.g., the north pole and the south pole. However, the definition need not be limited to three dimensions (points on the opposite ends of a diameter of a circle are sometimes referred to as antipodes, I think) nor to circles and spheres (I have seen opposite corners of a square referred to as antipodes). Generalizing further, antipodes are "opposite" or "maximally distant" points of any sort of structure, depending on what "opposite" or "maximally distant" mean in the context at hand. With respect to Rubik's cube, antipodes of Start are states which are maximally distant from Start, and it is a matter of great interest what that maximal distance might be. I have to admit to a certain discomforture with one aspect of the way we tend to refer to antipodes in the Rubik's cube. Most Rubik structures that have been investigated do not have a single point which is maximally distant from Start; rather, they have several or many maximally distant points, and all the maximally distant points are called antipodes. I would be more comfortable using "antipode" only when the maximally distant point is unique. One example where the maximally distant point is unique is the subgroup consisting of edges only (no corners or centers) where only Q-turns are allowed. In this case, the maximally distant point has been called the "unique antipode". The description "unique antipode" seems redundant somehow -- "antipode" ought to imply "unique", but that has not been the custom on Cube-Lovers. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From BRYAN@wvnvm.wvnet.edu Tue Nov 22 13:30:15 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA16031; Tue, 22 Nov 94 13:30:15 EST Message-Id: <9411221830.AA16031@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 2090; Tue, 22 Nov 94 13:07:07 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 3806; Tue, 22 Nov 1994 13:07:07 -0500 X-Acknowledge-To: Date: Tue, 22 Nov 1994 13:07:05 -0500 (EST) From: "Jerry Bryan" To: "Cube Lovers List" Subject: Q vs. Q+H Distances from Start The fact that there is only one position in which is antipodal for both Q moves and Q+H moves got me to thinking more generally about the Q distance from Start as compared to the Q+H distance from Start for any position. Here follows a cross-tabulation table giving the number of positions in unique up to W-conjugacy which are m moves from Start under Q and n moves from Start under Q+H. The table has some interesting features. The main diagonal contains powers of 2 for distances from zero to nine. Other entries in the upper left portion of the table (close to Start) are often small primes times powers of 2. There are positions where allowing Q+H moves saves nine moves (from nineteen down to ten), which is a substantial savings in moves. There is one "discontinuity" in the table; a position which is 25 moves from Start under Q may be 20, 19, 18, 17, or 15 moves from Start under Q+H, but not 16 moves from Start. The longest "common distance" is nineteen; there are positions which are nineteen moves from Start under both Q and Q+H, but for twenty moves and above there are no positions which are a common distance from Start. Q+H Distance from Start 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 Q 1 1 2 1 2 D 3 2 4 i 4 1 6 8 s 5 3 16 16 t 6 1 12 40 32 a 7 4 40 96 64 n 8 1 20 120 224 128 c 9 5 80 336 512 256 e 10 1 30 280 896 1148 508 11 6 140 888 2292 2532 1004 f 12 1 42 558 2632 5688 5455 1948 r 13 5 220 1976 7433 13656 11585 3675 o 14 50 976 6475 20158 32064 24082 6387 m 15 4 297 3810 19993 52672 73401 46779 16 47 1475 13603 58642 134127 160373 S 17 3 320 6291 45381 165993 327673 t 18 39 1799 24125 141267 447893 a 19 2 268 7822 80316 403413 r 20 16 1297 26988 225778 t 21 74 4300 67328 22 1 148 8034 23 198 24 2 25 Q+H Distance from Start 15 16 17 18 19 20 0 Q 1 2 D 3 i 4 s 5 t 6 a 7 n 8 c 9 e 10 11 f 12 r 13 o 14 m 15 9942 16 82146 12480 S 17 321647 116231 8729 t 18 740143 517578 98299 2066 a 19 1083499 1319438 493690 26824 42 r 20 961774 1957300 1304102 140670 566 t 21 470457 1531160 1733845 337599 2685 22 101326 545579 1018042 332435 4875 9 23 5760 58037 194963 115863 3286 3 24 23 680 4661 6032 493 3 25 1 3 15 7 1 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From BRYAN@wvnvm.wvnet.edu Wed Nov 23 17:02:19 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07588; Wed, 23 Nov 94 17:02:19 EST Message-Id: <9411232202.AA07588@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 8645; Wed, 23 Nov 94 17:02:27 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 4727; Wed, 23 Nov 1994 17:02:27 -0500 X-Acknowledge-To: Date: Wed, 23 Nov 1994 17:02:26 -0500 (EST) From: "Jerry Bryan" To: "Cube Lovers List" Subject: Q vs. Q+H Distance to Start -- All Positions This is the same chart as before except that it is in terms of all cube positions in rather than in terms of W-conjugacy classes. At the same time, I will take the opportunity to correct an error in the previous posting. Permitting Q+H moves rather than just Q moves can save up to 10 moves (e.g., 25 moves with Q and 15 moves with Q+H, 24 moves with Q and 14 moves with Q+H, and 22 moves with Q and 12 moves with Q+H). My thanks to Dan Hoey for spotting this error. Q+H Distance from Start 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 1 4 2 2 8 Q 3 8 16 4 2 24 32 D 5 12 64 64 i 6 2 48 160 128 s 7 16 160 384 256 t 8 2 80 480 896 512 a 9 20 320 1344 2048 1024 n 10 2 120 1120 3584 4590 2032 c 11 24 560 3552 9168 10128 4016 e 12 1 164 2232 10519 22736 21820 7788 13 20 880 7904 29732 54624 46332 14700 f 14 192 3904 25890 80606 128248 96324 25528 r 15 16 1184 15238 79970 210684 293572 187112 o 16 177 5900 54398 234536 536474 641412 m 17 12 1280 25164 181514 663960 1310584 18 150 7192 96478 564998 1791466 S 19 8 1072 31288 321242 1613572 t 20 58 5186 107919 902990 a 21 296 17192 269272 r 22 1 592 32122 t 23 782 24 8 25 Q+H Distance from Start 15 16 17 18 19 20 0 1 2 Q 3 4 D 5 i 6 s 7 t 8 a 9 n 10 c 11 e 12 13 f 14 r 15 39764 o 16 328532 49916 m 17 1286534 464878 34914 18 2960340 2069994 393142 8230 S 19 4333614 5277159 1974444 107256 166 t 20 3846819 7828346 5215618 562494 2252 a 21 1881664 6123940 6933978 1349768 10712 r 22 405221 2181984 4071140 1328952 19411 32 t 23 23010 232088 779418 462831 12969 12 24 92 2714 18612 23981 1936 8 25 2 8 56 19 2 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 If you don't have time to do it right today, what makes you think you are going to have time to do it over again tomorrow? From BRYAN@wvnvm.wvnet.edu Tue Nov 29 14:24:02 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA04706; Tue, 29 Nov 94 14:24:02 EST Message-Id: <9411291924.AA04706@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5515; Tue, 29 Nov 94 14:00:58 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 7319; Tue, 29 Nov 1994 14:00:59 -0500 X-Acknowledge-To: Date: Tue, 29 Nov 1994 14:00:58 -0500 (EST) From: "Jerry Bryan" To: "Cube Lovers List" Subject: Antipodes Revisited I received the following from David Singmaster, forwarded with permission. > I thought I remembered that antipodes is actually singular! In fact >it is singular in Greek but English recognizes both antipodes and antipode. >But the Antipodes means the region on the earth opposite to where one is and >is construed as a plural though its sense is singular. So antipodes is >actually not too bad a word for all the points which are maximally far away >and antipode should be reserved for the case where there is a unique >maximally distant point. Prior to my first post on this subject, I consulted a mathematics dictionary. This time, I consulted an English dictionary as well. It indicates that "antipode" is a back formation from the Greek "antipodes", and that the pronunciation is anglicized as "AN-ti-POHD". There is a separate entry for "antipodes". (It seems unusual for a dictionary to have a separate entry for a plural form.) The plural pronunciation retains its Greek form as "an-TIP-uh-DEEZ". = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET illegitimati (304) 293-5540 fax 837 Chestnut Ridge Road nil BRYAN@WVNVM Morgantown, WV 26505 carborundum BRYAN@WVNVM.WVNET.EDU From ivan@antares.aero.org Wed Dec 7 00:30:43 1994 Return-Path: Received: from aero.org by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA24372; Wed, 7 Dec 94 00:30:43 EST Received: from antares.aero.org ([130.221.192.46]) by aero.org with SMTP id <111151-1>; Tue, 6 Dec 1994 21:30:37 -0800 Received: from armadillo.aero.org by antares.aero.org (4.1/AMS-1.0) id AA11907 for cube-lovers@life.ai.mit.edu; Tue, 6 Dec 94 21:30:32 PST To: cube-lovers@life.ai.mit.edu Cc: ivan@aero.org Subject: Rubik's Cube, natch Date: Tue, 6 Dec 1994 21:30:30 -0800 Message-Id: <22790.786778230@armadillo.aero.org> From: Ivan Filippenko Is this a mailing list that I can join ? I'm a "cube lover", too. Thanks, -- Ivan ------------------------------------ Ivan V. Filippenko, Ph.D. Senior Member of the Technical Staff Computer Systems Division The Aerospace Corporation M/S M1-055 P.O. Box 92957 Los Angeles, CA 90009-2957 Internet: ivan@aero.org Phone: 310-336-1808 FAX: 310-336-5833 ------------------------------------ From mschoene@math.rwth-aachen.de Wed Dec 7 16:25:08 1994 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 AA05684; Wed, 7 Dec 94 16:25:08 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rFSE6-000MPIC; Wed, 7 Dec 94 20:40 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rFSE6-0000PsC; Wed, 7 Dec 94 20:40 PST Message-Id: Date: Wed, 7 Dec 94 20:40 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu Subject: Group Slang in Cube Lovers Dan Hoey and Jerry Bryan remind me, that not everybody reading my messages does group theory everyday. So the technical slang in my messages will not be intelligable to everybody (or in the worst case it will not be intelligable to anybody, including myself ;-). If this happens, please *do ask*. Almost everthing I write is simple. If you don't understand it, it is not your fault, it is mine, since I wasn't clear enough. If you do ask, I will try to explain everything. However, I must ask you to understand that my work and my family leave very little free time for such leisures. So it may take me some time to answer your questions. 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 Dec 7 16:29:15 1994 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 AA05846; Wed, 7 Dec 94 16:29:15 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rFSFF-000MPJC; Wed, 7 Dec 94 20:41 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rFSFF-0000PsC; Wed, 7 Dec 94 20:41 PST Message-Id: Date: Wed, 7 Dec 94 20:41 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu Subject: Cube Lovers on the World Wide Web I have converted the Cube-Lovers archives into HTML. You can now read all old e-mail messages using your favorite WWW Browser. Check out http://www.math.rwth-aachen.de:8000/~mschoene/Cube-Lovers/ I shall try to keep this reasonably up to date. The conversion is done automatically with an AWK script. It is certainly not perfect. If you have comments or suggestions, please write me. Looking at this long list of e-mail messages got me wondering. Should we try to condense the information into a few documents? I am thinking of documents describing what is known about God's algorithm, where those bounds come from, for which other groups God's algorithm is known, processes for pretty patterns, etc. The reason is I don't have the time to read all 1382 e-mail message carefully, and I believe that this is true for others too. I feel that there are many interesting things in Cube Lovers that I would like to know, but won't read. Any takers? 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 Dec 7 16:30:24 1994 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 AA05937; Wed, 7 Dec 94 16:30:24 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rFSGg-000MPPC; Wed, 7 Dec 94 20:43 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rFSGg-0000PsC; Wed, 7 Dec 94 20:43 PST Message-Id: Date: Wed, 7 Dec 94 20:43 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu Subject: Corrections Dan Hoey writes in his e-mail message of 1994/11/08 Martin.Schoenert@math.rwth-aachen.de writes: The way I view this is as follows. The entire cube group C is a permutation group group on 6*9 points, generated by the six face turns U, D, L, R, F, B; the three middle slice turns M_U, M_L, M_F; and the reflection S. This group has a subgroup M of symmetries of the cube (of order 48), generated by U M_U D', L M_L R', F M_F B', and S. Another subgroup is G, generated by the six face turns, which has index 48 in G. G is a normal ^ divisor of C, G is the semidirect product of M and G. The same is ^ true for GE and GC. I think two of those G's are supposed to be C's, right? Correct (wouldn't make any sense for a group G to be a subgroup in itself of index 48 ;-). Dan Hoey continues As for when I wrote M class Edge Corner Corner times edge (class size) F.P. F.P. / (96*class size) ^^^^^^^^^^^^^^^^^^^^^^ That's not a typo. I was just saying that column 4 is equal to column 2 times column 3, divided by column 1, divided by 96. Perhaps I should have factored column 1 out of columns 2 and 3 first to avoid this confusion. Again you are correct. But it was confusing, at least to me. 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 Dec 7 16:31:35 1994 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 AA05994; Wed, 7 Dec 94 16:31:35 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rFSHJ-000MPOC; Wed, 7 Dec 94 20:43 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rFSHJ-0000PsC; Wed, 7 Dec 94 20:43 PST Message-Id: Date: Wed, 7 Dec 94 20:43 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu Subject: A lemma that is *not* Burnside's Dan Hoey writes his e-mail message of 1994/11/04 In January of this year, Jerry Bryan and I wrote of counting the number of M-conjugacy classes of Rubik's cube. In the sense that (for instance) there is really only one position 1 QT from start, even though that QT may be applied in twelve different ways, this task amounts to counting the true number of positions of the cube. The earlier discussion centered on calculations involving computer analysis of large numbers of positions. However, a look in Paul B. Yale's book _Geometry and Symmetry_ gave me a clue: the Polya-Burnside theorem is a tool that allows us to perform this calculation by hand. The lemma used is indeed often referred to as ``Burnside's lemma'', or if used to count combinatorical objects as ``Polya-Burnside lemma''. However Peter M. Neumann in his paper ``A lemma that is not Burnside's'' (1979) pointed out that this lemma was known long befor Burnside rediscovered it. The first appearance seems to be Cauchy's work ``Memoire sur diverses proprietes remarquables des substitutions regulieres ou irregulieres, et des systemes de substitutiones conjugees (suite)'' of 1845. But it appears in a rather obscure form. It appears in more explicit form in Frobenius' paper ``"Uber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul'' in 1887. This is well befor Burnside's paper ``On some properties of groups of odd order'' in 1900. Polya refined it in his paper ``Kombinatorische Anzahlbestimmungen f"ur Gruppen, Graphen und chemische Verbindungen'' in 1937, for use in the part of combinatorics which deals with counting problems. Peter M. Neumann thus proposed to call this lemma ``Cauchy-Frobenius lemma''. But this was somehow not accepted, and it is now usually called ``A lemma that is not Burnside's''. 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 Dec 7 18:55:27 1994 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 AB15276; Wed, 7 Dec 94 18:55:27 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rFSIx-000MPUC; Wed, 7 Dec 94 20:45 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rFSIx-0000PsC; Wed, 7 Dec 94 20:45 PST Message-Id: Date: Wed, 7 Dec 94 20:45 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu Subject: Models for the Cube I wrote in my e-mail message of 1994/11/08 The way I view this is as follows. The entire cube group C is a permutation group group on 6*9 points, generated by the six face turns U, D, L, R, F, B; the three middle slice turns M_U, M_L, M_F; and the reflection S. This group has a subgroup M of symmetries of the cube (of order 48), generated by U M_U D', L M_L R', F M_F B', and S. Another subgroup is G, generated by the six face turns, which has index 48 in G. G is a normal divisor of C, G is the semidirect product of M and G. The same is true for GE and GC. Jerry Bryan writes in his e-mail message of 1994/11/08 I have discussed a similar view of things recently, except that I was not brave enough to include a reflection in the generators. C is normally used to denote the set of twenty-four rotations of the cube (a sub-group of M), so let's call your "entire cube group" big_G instead. My version of big_G was generated by Q plus the slice moves (like yours without the reflection), or alternatively by Q plus C. Your version of big_G is hence the same as the one I discussed except that you added a reflection. C (the rotations C, that is) is a sub-group of both versions of big_G. M is a sub-group of your version of big_G, but not of mine. Your big_G has the obvious advantage of including M as a sub-group. Mine has the advantage (?) of being physically realizable on a real cube. That is, for X in your big_G, rX or Xr (r is a reflection) is also in your big_G. For X in my big_G, rX or Xr is not in big_G, and correspondingly a single reflection is not physically realizable on a real cube. Of course, r'Xr is in big_G in either case, r being in M. Also, cX and Xc are in either version of big_G for all c in C. OK, I guess I have to be a little bit more precise and also to adapt my terminology to common usage. First a picture. MG (48*|G|) /| / CG (24*|G|) / /| / / | / / | / / G (|G| = 8!*3^7 * 12!*2^11 / 2) / / | / / | / / | / / | / / | / / / / / / / / / (48) M / / |/ / (24) C / \ / \ / \ / <1> The maximal cube group *MG* is a permutation group on 6*9 points. It is generated by the six face turns < U, D, L, R, F, B >, the three rotations of the entire cube < u, l, f >, and the reflection < x >. The complete cube group *CG*, generated by < U, D, L, R, F, B > and < u, l, f >, is a subgroup of MG of index 2. The cube group *G*, generated by < U, D, L, R, F, B >, is a subgroup of index 24 in CG. G can be viewed as a permutation group on 48 points, since it fixes the 6 center cubies. The group *M* of symmetries of the entire cube, generated by < u, l, f > and < x >, is a subgroup of MG of size 48. The group *C* of rotations of the entire cube, generated by < u, l, f >, is a subgroup of CG of size 24. (I would have preferred S instead of M and R instead of C, but M and C are too widely used to change that notation. Of course MG is not called MG because it is the maximal cube group, but as a reminder that it is the product of M and G. Likewise for CG.) Jerry continues I tend to think that Singmaster's standard G= is not what people think of when they hold a real cube in their hand. Rather, they tend to think of big_G/C. That is, the cosets of C in big_G are common sensically considered to be equivalent because rotating a real cube in space is "doing nothing". Also, for my version of big_G we have |big_G/C| = |G|. True, what people really see is the complete cube group CG (what you call big_C). That is, patterns corresponding to two different elements of CG are distinct. Now if two patterns can be made equal by rotations of the entire cube, they ``look alike'' and most people feel that they are equivalent since rotations ``cost nothing''. Especially they feel that any pattern corresponding to an element in C is solved. Mathematically we describe this equivalence by saying that all 24 elements in each coset of C are equivalent. Unfortunately C is *not* a normal subgroup of CG, and therefore CG/C is *not* a group. If we want to apply group theory, we need a better model. I argue that G is indeed a good model for the 3x3x3 cube. First note that for each coset of C in CG, there is exactly one element of G in this coset. This follows since C and G together generate CG and have trivial intersection. We call this element the representative in G of the coset. Thus G is a set of representatives for the cosets of C in CG. In group theory terminology G is a *supplement* for C (if C was a normal subgroup, then G would be called a complement of C). An immediate consequence is that |G| = |CG| / |C|. Next note that, if we assume that rotations ``cost nothing'' and middle slice turns cost (at least) twice as much as face turns, then any two elements in a coset of C have the same *cost*, i.e., distance from the solved cube, and this is equal to the cost of the representative in G. This is a simple consequence of the fact that we can transform each process p_1 p_2 ... p_l, where each p_i is either a face turn or a rotation of the entire cube, into one which has a single rotation of the entire cube first and then only face turns afterwards. This can be done using the rule => , which obviously doesn't change the cost of the process (remember rotations cost nothing). Finally note that G's structure as a group is in a certain sense CG without C. Namely G is a normal subgroup of CG, and the factor group CG/G is isomorphic to C. Ideally we would like to have G be isomorphic to CG modulo C, but this is not well defined, as C is not a normal subgroup. Put another way, CG is the semidirekt product of G with C. Unfortunately the existence of this model is particular to the 3x3x3 cube. It does not work as well for other cubes. First take the 2x2x2 cube group CG_2 (I use a _2 to distinguish the 2x2x2 subgroups from their 3x3x3 counterparts). Again we have a subgroup C_2, generated by the rotations, of size 24. But the subgroup G_2, generated by the six face turns, is in fact equal to CG_2. In particular it is not a supplement to C_2. But we can make a similar construction. Namely in the case of the 3x3x3 we can view CG as generated by the six face turns and the three middle slice turns < M_U, M_D, M_F > (instead of the six face turns and the three rotations < u, d, f >). And our supplement G was the subgroup of CG generated by 6 of those 9 generators, were the 3 removed ones are pairwise perpendicular. In the case of the 2x2x2 cube we can take the subgroup H_2 that is generated by three turns < U, L, F >. Using the transformations => and D => u' U, R => l' L, B => f' F, we can again transform any process into one which has a single rotation first and then only < U, L, F > turns afterwards, without changing the cost of the process (again rotations cost nothing). Thus H_2, of size 7!*3^6, is a good model to use when one is looking for God's algorithm for the 2x2x2 cube. Nothing of this is really new, I have just casted it into a different language. For example see 'http://www.math.rwth-aachen.de:8000/~mschoene/Cube-Lovers/ Jerry_Bryan__God's_Algorithm_for_the_2x2x2_Pocket_Cube.html'. But H_2 is *not* normal, and is not CG_2 without C_2 (in the sense in which G was CG without C). For example CG_2 has a factor group isomorphic to S8, but there is no such factor in H_2. Things get worse when we look at the nxnxn cube groups CG_n. We can find again find a supplement H_n for C_n, if we leave out three pairwise perpendicular slice turns. If n is odd and if we leave out the three middle slice turns, then H_n is again a normal subgroup (and in the same sense as above, it is again CG_n without C_n). On the other hand if n is even then H_n is never a normal subgroup. Moreover if 3 < n, then the transformation rules tell us to replace one of the removed slice turns by a rotation and the product of the n-1 parallel slice turns. Thus the transformation would only respect the cost, if we assume that the removed three slice turns have cost n-1. While this is arguably true for n = 3, where most people feel that the middle slice turns have cost 2, I don't think anybody feels that for the 4x4x4 cube nine of the slice turns have cost 1 and 3 have cost 3. And now for something completely different (no, not really ;-). I have argued that G is a good model for the 3x3x3 cube assuming that rotations of the entire cube cost nothing, and that middle slice turns have cost 2 (or higher). In a certain sense, we got rid of C. That doesn't mean we can't use C anymore. In fact, C is still very useful. Namely let c be any element of C, and g be any element of G. Then c' g c is another element of G, because G is a normal subgroup. Moreover the cost of c' g c is the same as the cost of g. This is trivial because each process effecting g can be turned into a process effecting c' g c, by replacing each generator x in this process by c' x c. But C is not the largest such group. The largest such group is M, i.e., the full group of symmetries of the entire cube. This is the reason why I prefer to view G as a subgroup of MG, which is the semidirekt product of M and G, even though I realize that MG is not physically realizable. 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 Dec 7 19:36:43 1994 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 AA17629; Wed, 7 Dec 94 19:36:43 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rFSJi-000MPVC; Wed, 7 Dec 94 20:46 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rFSJi-0000PsC; Wed, 7 Dec 94 20:46 PST Message-Id: Date: Wed, 7 Dec 94 20:46 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu Subject: Cayley Graphs I wrote in my e-mail message of 1994/11/08 Note that the elements of M are also a autmorphisms of the Cayley graph. That means that elements of M respects the length of operations. That is if g_1 and g_2 are elements of G that are in one conjugacy class under M, then the lenght of the shortest process effecting them is equal. This follows from the fact that M fixes the set of the generators of G and their inverses. M is fact the largest subgroup of the outer autmorphism group with this property, which makes it rather important. Jerry Bryan answered in his e-mail message of 1994/11/08 This of course is the basis for the large searches I have been able to perform using M-conjugate classes. The only trouble is, I don't even know what a Cayley graph is (but I am working on it), the last course I took in group theory being 25 years ago. The Cayley graph Gamma for a group G generated by a certain system of generators < g_1, g_2, ... > is defined as follows. The vertices of Gamma correspond to the elements of G. From vertex v_1 draw an edge to v_2 labelled with g_i, if and only if v_1 g_i = v_2. Also draw an edge from v_2 to v_2 labelled g_i^-1 (or g_i'). So the Cayley graph depends on the group *and* on the generating system. Simple, isn't it. In this terminology God's number for the cube is simply the diameter of the Cayley graph of the cube group generated by the quarter face turns (or quarter face turns and half face turns). In general an autmorphism alpha of G maps the Cayley graph of G w.r.t. the generating system < g_1, g_2, ... > to a new Cayley graph of G w.r.t. the generating system < g_1^alpha, g_2^alpha, ... >. But in this case, i.e., for the autmorphism of G induced by elements of M, the sets { g_1, g_2, ... } and { g_1^alpha, g_2^alpha, ... } are equal. So the elements of M induce autmorphism of the unlabelled Cayley graph. And as I said, M is the largest subgroup of the outer autmorphism group of G with this property. 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 Dec 7 19:49:39 1994 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 AA17943; Wed, 7 Dec 94 19:49:39 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rFSLJ-000MPZC; Wed, 7 Dec 94 20:48 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rFSLI-0000PsC; Wed, 7 Dec 94 20:48 PST Message-Id: Date: Wed, 7 Dec 94 20:48 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu Subject: Permutation Representations for Magic Polyhedra Dan Hoey writes in his e-mail message of 1994/11/08 Wow, I didn't realize this sort of calculation had been automated. Hey, we do this stuff every day. Really. Well at least with a loose interpretation of ``this sort of''. Dan Hoey continues gap-3.4 -b -g 4m gap> Sum( ConjugacyClasses( M ), > c -> Size( Centralizer(G,Representative(c)) ) / 48 * Size(c) ); 901083404981813616 Well, call me John Henry. Say, do you have gap libraries for other magic polyhedra? For higher-dimensional magic? I also have a permutation representation for the 2x2x2 and the 4x4x4 cube. I must confess that I was never interested in other magic polyhedra. I once started writing a GAP function that creates a premutation representation for any (hyper-)cube, i.e., 'Cube( 3, 3, 3, 2 )' would create a 4-dimensional magic domino. The largest problem was to define what the ``faces'' and ``slices'' are, i.e., are they 2 or n-1 dimensional? If there is interest, I would finish this project and also collect permutation representations for other magic polyhedra and distribute them together with future versions of GAP. 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 Dec 7 19:55:00 1994 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 AA18723; Wed, 7 Dec 94 19:55:00 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rFSM4-000MPbC; Wed, 7 Dec 94 20:48 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rFSM3-0000PsC; Wed, 7 Dec 94 20:48 PST Message-Id: Date: Wed, 7 Dec 94 20:48 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu Subject: Distance Respecting Automorphisms Dan Hoey writes in his e-mail message of 1994/11/08 ... [conjugation by] M fixes the set of the generators of G and their inverses. M is fact the largest subgroup of the outer autmorphism group with this property, which makes it rather important. In a 1983 Cubic Circular article (of which I know only Stan Isaacs's summary) David Singmaster observed that the group is larger for larger cubes, provided we work what I call the ``theoretical invisible group''. That is, we solve not only the surface of the cube, but the hypothetical interior (n-2)^3 cube, and all the smaller (n-2k)^3 cubes as well. I blithered at length about this in my article of 1 June 1983 archived (I think I've got it right this time) at . Try http://www.math.rwth-aachen.de:8000/~mschoene/Cube-Lovers/ Dan_Hoey__Eccentric_Slabism,_Qubic,_and_S&LM.html instead (must be on a single line). Dan continues The idea is that a mapping called evisceration allows us to permute the layers of the cube. On the 4x4x4 cube, this for instance allows us to exchange each inner slab with its adjacent outer slab. It also allows us to conjugate each inner slab move by central inversion, while leaving the outer slab moves alone. In general, evisceration of a d-dimensional cube by f maps each feature (cubie, colortab, or face-center arrow) at coordinates (x[1],x[2],...,x[d]) to (f(x[1]),f(x[2]),...,f(x[d])), where f is a permutation of the intervals between the cleavage coordinates of the cube. I believe that if f commutes with the central inversion, then conjugation by evisceration is an outer automorphism of the Rubik's cube group. (I think I have proved this for d=3, and I think the proof in higher dimensions should not be difficult given the right notation.) The group of all eviscerations includes the central inversion; we can of course augment it by the rotation group in d-space. Is this the maximum outer automorphism group that respects generators of the Rubik's cube? For this we take the generators to be turns of slabs between adjacent cleavage planes. (Turns are direct d-1-dimensional isometries.) Allow me to reformulate your description again slightly. Let P be a d-dimensional n*n*...*n cube. Let m be (n-1)/2 if n is odd and n/2 if n is even. The position of each cubie is described by its position vector (p_1,p_2,...,p_d). If n is odd, then each p_i comes from [-m..m]. If n is even, then each p_i comes from [-m..-1,1..m] (no middle slice in this case). The orientation of a cubie is described by its orientation vector (o_1,o_2,...,o_d), where each o_i comes from the set [-1,1]. I consider the puzzle solved, if each cubie is in its original position and in its original orientation (this is stronger than we usually require for the 3x3x3 Rubik's cube, where we ignore the orientation of the centre cubies, but remember, we *see* the usually invisible faces). If F is a bijection on [-m..m] (n odd) or [-m..-1,1..m] (n even), then F induces a permutation of the cubies (ignoring orientation) via F( (p_1,p_2,...,p_d) ) = (F(p_1),F(p_2),...,F(p_d)). Let I_k be defined by I_k(k) = -k, I_k(-k) = k, and I_k(l) = l for l <> k. The permutation of the cubies induced by I_k is the inversion of the k-th slab of the cube. If A is a permutation on [1..m], we write l^A for the image of l under A, and we define (-l)^A := -(l^A) (you enforce the condition (-l)^A = -(l^A) by requiring that the permutation commutes with the central inversion). The permutation induced by A permutes the slabs of the cube. The group of all eviscerations is generated by all the I_k and all permutations A of [1..m]. Each evisceration first inverts certain slabs, and then permutes the slabs. Put differently, the group of all eviscerations is the wreath product of {-1,1} and S_m. Repeating the definition of the wreath product, this means that the group of all eviscerations is the semidirect product of the normal subgroup generated by the I_k and the symmetric group generated by the A. This group, together with the group C of symmetries of the d-dimensional cube P, is a subgroup of the automorphism group of P, which fixes the set of generators (with any reasonable definition of what the generators of P are), and thus respects the distance of elements in the Cayley graph. Is this the largest such group? In the case that d = 3, this is true. In the case of larger d, I am quite certain it is true if the generators are rotations of 2 dimensional subsets of P. If we choose the generators to be symmetries of d-1 dimensional subsets of P, then I still believe it is true. But I have been fooled often enough in such situations, to not trust my intuition without a proof. If we can agree on a precise definition of what the generators of the d dimensional cube are, I would be happy to compute the largest subgroup of the automorphism group that respects the distance of elements in the Cayley graph. 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 Dec 7 21:30:12 1994 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 AA23783; Wed, 7 Dec 94 21:30:12 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rFSKQ-000MPYC; Wed, 7 Dec 94 20:47 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rFSKQ-0000PsC; Wed, 7 Dec 94 20:47 PST Message-Id: Date: Wed, 7 Dec 94 20:47 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu Subject: Group Products Dan Hoey writes in his e-mail message of 1994/11/08 What is the difference between a direct product and a semidirect product? Allow to answer this in greater detail, and describe all the important products of groups. It is one of the marvels of Rubik's cube that all these products arise in a very natural fashion when one investigates it. Direct Product -------------- We say that a group D is the *direct product* of its two subgroups M and N, if M and N together generate the whole group D, M and N have trivial intersection, and M and N are both normal subgroups. This implies that D is isomorphic to the group of pairs (m,n), where the multiplication is defined componentwise, i.e., (m_1,n_1) * (m_2,n_2) = (m_1 * n_2, m_1 * n_2). Here is a little picture to describe the situation. D / \ / \ M \ \ N \ / \ / 1 M and N are the factors, D is their direct product. Note that D/N ~ M and D/M ~ N (X ~ Y means that X and Y are isomorphic). So M and N appear both as subgroups and quotients of the direct product. Direct products are very simple. They are fully described by their to factors M and N. Also many properties follow easily from the corresponding properties of the factors, e.g.., |M*N| = |M| * |M|. For an example lets take a group G+ that is a little bit larger than the group G of Rubik's cube, namely we also allow to exchange two edges *without* exchanging two corners simultaneously (don't ask me how this could be realized physically). This group is the direct product of two subgroups GC and GE. GC is the stabilizer of the edges, i.e., the subgroup of those elements that do not permute the edges at all, and thus operates only on the corners. GE is the stabilizer of the corners, i.e., the subgroup of those elements that do not permute the corners, and thus operates only on the edges. G+ is isomorphic to the group of pairs (c,e) with c in GC and e in GE. That means, each element of G+ can be described by describing how it operates on the corners and on the edges (this is trivial). And for any c in GC and any e in GE, there is an element in G+ that operates like c on the corners and like e on the edges. The latter is not true in G, which is a subgroup of index 2 in G+. Semidirect Product ------------------ We say that a group S is the *semidirect product* of its two subgroups H and N, if H and N together generate the whole group S, H and N have trivial intersection, and N is a normal subgroup (but H need not be normal). This implies that S is isomorphic to the group of pairs (h,n), where the multiplication is defined as follows (h_1,n_1) * (h_2,n_2) = (h_1 * h_2, h_2^-1 * n_1 * h_2 * n_2). Note that h^-1 * n * h is usually written as n ^ h. A picture for this situation would be identical to the picture for the direct product, since the only real difference to the direct product is that H need not be normal. Again both H and N appear as subgroups of S, but only H appears as factor of S, namely S/N ~ H. Note that S/H is *not* well defined, since H is not a normal subgroup of S. Semidirect products are almost as simple as direct products. They are described by their factors H and N, and the operation of H on N, by specifying what n^h is for every h in H and n in N (note that n^h is again in N, because N is a normal subgroup). And again many properties of S can be easily calculated from the corresponding properties of H and N. For an example let S be the group generated by the six face turns and rotations of the entire cube (or equivalently the six face turns and the three middle slice turns). Let G be the subgroup of S generated by the six face turns. Let C be the subgroup of S generated by the rotations of the entire cube, which has size 24. Obviously C and G together generate S. C and G have trivial intersection, since every element of G fixes the orientation of entire cube, but only the trivial element in C fixes the entire cube. Finally G is normal, since for each generator (face turn) g of G and each h in H the element g^h is again in G (in fact it is again a generator or an inverse of a generator). Thus S is a semidirect product of C and G. Subdirect Product ----------------- Let M and N be two groups. Let D be the direct product of M and N. Let f: M -> H and g: N -> H be two homomorphisms onto a group H. Then the subgroup S = {(m,n) in D | f(m) = g(n)} of D is called a *subdirect product* of M and N. Again a little picture to describe the situation. D / | \ / | \ / | \ / S \ / | \ / | \ M | \ \ | N \ S- / \ / \ / \ / \ / M- \ / \ N- \ / \ / 1 M and N are the two factors, D is their direct product. S is the subdirect product for the equation f(u) = g(v). M- is the kern of f, and N- is the kern of g. Thus M/M- = M/kern(f) ~ image(f) = H = image(g) ~ N/kern(g) = N/N-. S- is the direct product of M- and N- and is a subgroup of S (namely the subgroup such that f(u) = g(v) = 1). It is easy to see that S/N- ~ M and S/M- ~ N. So M and N appear as quotients of S. But note that M and N *do not* appear as subgroups of S! Also note that S/N- ~ M and S/M- ~ N implies that S/S- ~ H. Thus M and N have a common quotient H, and in the subdirect product we have ``glued'' these two quotients together. For an example lets again look at the direct product G+ of GC and GE. I have already mentioned that G is a subgroup of index 2 in G+. It is in fact a subdirect of GC and GE. Namely H = {-1,1}, f(c) is the parity (sign) of the permutation of the corners by c, and g(e) is the parity (sign) of the permutation of the edges by e. In other words, G is the subdirect product of GC and GE with the condition that whenever we exchange two corners we also exchange two edges. This is in fact no coincidence. Whenever one has a permutation group that has more than one orbit, it is a subdirect product of the operations on the individual orbits. Wreath Product -------------- Let M be an abitrary group. Let H be a permutation group operating on [1..n]. For h in H and i in [1..n], we write the image of i under h as i^h. The *wreath product* W = M wr H, is the semidirect product of the normal subgroup N = M^n (i.e., the direct product of n copies of M), with the subgroup H, where H operates by permuting the components of N, (i.e., (m_1,m_2,...,m_n)^h := (m_{1^h},m_{2^h},...,m_{n^h})). For an example take the following permutation group W: < ( 1, 2, 3), ( 4, 5, 6), ( 7, 8, 9), (10,11,12), (13,14,15), (16,17,18), (19,20,21), (22,23,24), ( 1, 4)( 2, 5)( 3, 6), ( 4, 7,10,13,16,19,22)( 5, 8,11,14,17,20,23)( 6, 9,12,15,18,21,24) >. The first 8 generators generate a direct product N of 8 cyclic groups of size 3, which is a normal subgroup in G. The last 2 generators generate a symmetric group of degree 8, operating on the 8 factors of the direct factors of N. Thus W = C_3 wr S_8. W operates on the set { {1,2,3}, {4,5,6}, ..., {22,23,24} }, called a blocksystem for W. To describe what an element w in W does, we first say how it operates on each block, and then how it permutes the blocks. On the other hand, if we have a permutation group that has a blocksystem, then this permutation group is a subgroup of the wreath product. The group GC, operating only on the corners of the cube, is a subgroup of index 3 in the above group W. For each element of GC, you first say how it changes the orientation of the 8 corners (the C_3^8) and then how it permutes the 8 corners (the S_8). The index 3 comes from the fact that we cannot change the orientation of a single corner in GC; if we turn one corner clockwise, we must turn another corner counterclockwise. 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 BRYAN@wvnvm.wvnet.edu Thu Dec 8 14:00:11 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA11013; Thu, 8 Dec 94 14:00:11 EST Message-Id: <9412081900.AA11013@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5411; Thu, 08 Dec 94 14:00:13 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 2801; Thu, 8 Dec 1994 14:00:12 -0500 X-Acknowledge-To: Date: Thu, 8 Dec 1994 13:59:48 -0500 (EST) From: "Jerry Bryan" To: Subject: Re: Models for the Cube In-Reply-To: Message of 12/07/94 at 20:45:00 from , Martin.Schoenert@math.rwth-aachen.de On 12/07/94 at 20:45:00 Martin Schoenert said: >Unfortunately C is *not* a normal subgroup of CG, and therefore CG/C is >*not* a group. If we want to apply group theory, we need a better model. >I argue that G is indeed a good model for the 3x3x3 cube. Well, with great fear and trepidation, let's see if we can't interpret CG/C in such a way that it is a group. I agree that your statement above is correct, but I believe we are interpreting C, G, and CG somewhat differently. I have discussed this subject before, but armed with some better notation suggested via Dan Hoey, I think I can do it again both more accurately and more succinctly. Dan's suggestion is to carefully distinguish which of the various types of cubies we are talking about. I have done a lot of work with (for example) corners-only-cubes-without-centers, corners-only- cubes-with-centers, etc. When we talk about the set C of rotations, Dan suggests specifying such things as C[C] (Corners-only), C[E] (Edges-only], C[C,F] (Corners-plus-Face-centers), etc. The C[C] thing looks funny, using C in two such different ways, but there are only so many letters. I want to reserve lower case c for elements of C, so I will live with C[C]. I would suggest extending the notation to G and Q, so that (for example) the corners-only with Face-centers group we have called GC could instead be called G[C,F] = , and the 2x2x2 cube could be called GC= because there are no Face-centers. The "standard Singmaster model" (my terminology) would be written as G[C,E,F] = . (Well, I think Singmaster would write it as G[C,E,F] = , since I think he prefers to accept H turns as single moves.) However, I tend to work with G[C,E] = instead. I consider G[C,E] to be equivalent to G[C,E,F] for most purposes because G fixes the Face-centers, as does M-conjugation. I have described this equivalence before as the Face-centers simply providing a frame of reference that can be provided in other ways. However, when you step outside the friendly confines of G=, it does start to matter whether the Face-centers are there or not. As an example important to this discussion, if you consider CG=, then it makes a considerable difference whether you are talking about CGC,E or CGC,E,F. For example, G[C,E] = can be simulated on a real cube by removing the color tabs from the Face-centers, by restricting yourself to Q moves only (no whole cube rotations or slices), and by declaring the cube solved only when the Up color is up and the Front color is Front. Notice that with the Face centers absent, you can make the cube look solved even when it isn't. It will be rotated instead, but it won't be solved. This model may seem a little simple-minded. Why are no rotations allowed, and why don't you count it as solved when it looks solved? But computers are simple-minded. My programs only consider things equal when they are literally equal, and equivalence is something I have to program in. As an example I have used before, consider G[C]=, modeled in the real world by a 2x2x2 pocket cube or by removing both the edge and Face-center color tabs from a 3x3x3 cube. Take a solved cube in GC and perform RL'. The cube will still look solved, but it will be rotated. The memory cells in my program will not be the same for I as for RL', but I want to treat them as equivalent, as would nearly everybody with a real world 2x2x2 cube in their hands. This is where I have claimed before that a model that treats RL' the same as I is G[C]/C[C]. The idea is that G[C]/C[C] is a group with the identity being C[C] itself (i.e., rotating the cube is "doing nothing".) The proof is fairly simple. From each element (coset) of G[C]/C[C], pick the unique permutation that fixes a particular corner, say UFR, and form a new set G[C]* containing the one element chosen from each coset. The elements of G[C]/C[C] are sets (namely cosets), but the elements of G[C]* are permutations which are also in G[C]. In particular, G[C]* = . Hence, G[C]* is a group. Note that the generators of G[C]* are the twists of those faces which are diagonally opposed to the corner fixed by the selection function from G[C]/C[C] to G[C]*. Hence, the generators fix the same corner as the selection function, showing that is really the same set as G[C]*, namely the set of all cubes in G[C] for which the UFR corner is fixed. Finally, there is an obvious isomorphism between G[C]/C[C] and . Namely, to multiply two cosets, map each to via the selection function, perform the multiplication there using standard cube multiplication, and map the product back to a coset. Hence, G[C]/C[C] is a group. A similar argument applies to G[E]/C[E] except that we have to fix an edge cubie instead of a corner cubie. A similar argument applies to G[C,E]/C[C,E] except we have to fix an edge cubie and restrict C to even permutations. Dan calls the set of even rotations E, so let's call it G[C,E]/E[C,E]. (Still wish we had letters whose use did not conflict so blatantly.) But when we started, we were talking about CG/C, not about G/C. However, notice that when our model does not include Face-centers, we have = , = , and = . (I mean that the groups are equal, not that the Cayley graphs are the same.) Hence, speaking generically of the first two cases, we have C is in G, CG=G, and both CG/C and G/C are groups. In the last case, we have to say E is in G, EG=G, and EG/E is a group. But we can go one step further. Since there are no Face-centers, we can admit Slice moves or C as generators (it doesn't matter which), and we no longer have to restrict ourselves to even rotations. We can say G+C,E= and we will have C is in G+, CG+=G+, and CG+/C is a group which is the same size as EG/E. (G+ is twice as big as G, of course.) I guess this must mean that CC, CE, and CC,E are all normal subgroups of their respective CG's, but that CC,F, CE,F, and CC,E,F are not. That should not be surprising. Having the Face-centers there only as a frame of reference and never moving is not the same as having them there and really moving (as when you rotate the entire cube). After joining Cube-Lovers, I discovered that others had solved God's algorithm for the 2x2x2 long before me. I was expecting my solution to be 24*48 times smaller than theirs because I was using cosets of C and M-conjugates. But my solution was only 48 times smaller than theirs. By taking both cosets and M-conjugates I really had reduced by 24*48 times. However, everybody else who worked on the problem had modeled it as something like , fixing a corner. (Any other corner would do as well. There are eight conjugate groups, any of which would do as well as any other.) is 24 times smaller than in the first place, and as I said earlier, is equivalent to for most purposes anyway because of the fixed Face-centers. Hence, everybody else had a 24 times head start on me. (At the time, Dan suggested that I was increasing the size of the problem by 24 and then reducing it by 24*48 for a net reduction of 48. But that would only be true if the model were . Since the model was , there really was a reduction of 24*48. But does not really model the 2x2x2 cube, and is 24 times larger than it needs to be in the first place if you are trying to model the 2x2x2.) Modeling cubes without centers such as the 2x2x2 is trickier than it looks because of the requirement that rotations be treated as equivalent. I did it by using cosets of rotations; everybody else did it by fixing a corner. But before I realized all this, I went on a Quixotic chase for a model which would simultaneously be a true model for a 2x2x2 cube and would retain the cubic symmetry of the problem (whatever that means). There are articles in the archives concerning this subject, with the conclusion that no such model is possible because any true model would be isomorphic to , which does not have "cubic symmetry". I guess the "cubic symmetry of the problem" means that you should use M-conjugate classes. Recall that when I solved I used what Dan calls W-conjugate classes because W is the symmetry group for , and W-conjugate classes reduced the size of the problem by four times. This leads me to a question. The way I modeled the 2x2x2, I used M-conjugate classes of cosets and reduced the size of the problem by 48 times. If I were going to model , I would be very inclined not to use M-conjugate classes, but rather to use a subgroup of M which was the symmetry group of . The subgroup would have less than 48 elements, and I would get less than a 48 times reduction in the size of the problem. But a fixed corner model such as is isomorphic to a coset model such as /CC, and M-conjugates are appropriate to the coset model. Therefore, my analysis of the situation is obviously very flawed. Can anybody see what is wrong? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 Thu Dec 8 15:02:35 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA14755; Thu, 8 Dec 94 15:02:35 EST Message-Id: <9412082002.AA14755@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5833; Thu, 08 Dec 94 15:02:34 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 4852; Thu, 8 Dec 1994 15:02:35 -0500 X-Acknowledge-To: Date: Thu, 8 Dec 1994 15:02:33 -0500 (EST) From: "Jerry Bryan" To: Subject: Re: Models for the Cube In-Reply-To: Message of 12/07/94 at 20:45:00 from , Martin.Schoenert@math.rwth-aachen.de On 12/07/94 at 20:45:00 Martin Schoenert said: >But C is not the largest such group. The largest such group is M, i.e., >the full group of symmetries of the entire cube. This is the reason why >I prefer to view G as a subgroup of MG, which is the semidirekt product >of M and G, even though I realize that MG is not physically realizable. But can't you speak of conjugates such as m'gm without regard to G being a subgroup of MG? I agree that MG seems like a very useful group, and it is a very nice model of what is going on. But doesn't g in G imply m'gm in G whether I ever heard of MG or not? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 Thu Dec 8 15:21:09 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA15457; Thu, 8 Dec 94 15:21:09 EST Message-Id: <9412082021.AA15457@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5969; Thu, 08 Dec 94 15:21:12 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 5408; Thu, 8 Dec 1994 15:21:12 -0500 X-Acknowledge-To: Date: Thu, 8 Dec 1994 15:21:04 -0500 (EST) From: "Jerry Bryan" To: Subject: Re: Cayley Graphs In-Reply-To: Message of 12/07/94 at 20:46:00 from , Martin.Schoenert@math.rwth-aachen.de On 12/07/94 at 20:46:00 Martin Schoenert said: >The Cayley graph Gamma for a group G generated by a certain system of >generators < g_1, g_2, ... > is defined as follows. >The vertices of Gamma correspond to the elements of G. From vertex v_1 >draw an edge to v_2 labelled with g_i, if and only if v_1 g_i = v_2. >Also draw an edge from v_2 to v_2 labelled g_i^-1 (or g_i'). v_1 >So the Cayley graph depends on the group *and* on the generating system. >Simple, isn't it. These are fine points, but they bother me anyway. 1. Suppose I write =. If I mean that the group is equal to the group , then the equation is correct. If I mean that the Cayley graph of is the same as the Cayley graph of , then the equation is incorrect. Which is the conventional meaning? Is the meaning universal, or does it depend on the author and the context? 2. I gather from your note and from things that Dan sent me that one should not list inverses of the generators. For example, is sufficient and one should not write . But people conventionally write which includes six processes and their six inverses. Is this acceptable usage, or should we write instead? As an additional comment, I have frequently written about the Q length of a process in or the Q+H length of a process in . I think we would be better served to talk about the length of a process in or the length of a process in if the generator notation implies a particular Cayley graph. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 acoles@mnsinc.com Thu Dec 8 16:31:30 1994 Return-Path: Received: from news1.mnsinc.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA19212; Thu, 8 Dec 94 16:31:30 EST Received: from localhost (mail@localhost) by news1.mnsinc.com (8.6.5/8.6.5) id QAA06602 for ; Thu, 8 Dec 1994 16:32:57 -0500 Received: from mnsnet.mnsinc.com(199.164.210.10) by news1.mnsinc.com via smap (V1.3) id sma006600; Thu Dec 8 16:32:31 1994 Received: by mnsinc.com (5.65/1.35) id AA13474; Thu, 8 Dec 94 16:30:38 -0500 Date: Thu, 8 Dec 1994 16:30:38 -0500 (EST) From: Aaron Coles To: cube-lovers@life.ai.mit.edu Subject: Cubes Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII I would like to know if there is any place where I can purchase "mind-boggling" cubes from. Also, if anyone knows Peter Beck's internet address, please let me know. Thanks. From mreid@ptc.com Thu Dec 8 16:44:33 1994 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 AA20153; Thu, 8 Dec 94 16:44:33 EST Received: from ducie.ptc.com by PTC.COM (5.0/SMI-SVR4-NN) id AA01843; Thu, 8 Dec 94 16:43:16 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA28255; Thu, 8 Dec 1994 16:53:40 -0500 Date: Thu, 8 Dec 1994 16:53:40 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9412082153.AA28255@ducie.ptc.com> To: cube-lovers%life.ai.mit.edu@ptc.com Subject: Re: Cayley Graphs Content-Length: 2120 jerry says: > On 12/07/94 at 20:46:00 Martin Schoenert said: > > >So the Cayley graph depends on the group *and* on the generating system. > >Simple, isn't it. > > These are fine points, but they bother me anyway. > > 1. Suppose I write =. If I mean that the group is equal > to the group , then the equation is correct. here you're using "" to denote the group. > If I mean that > the Cayley graph of is the same as the Cayley graph of , > then the equation is incorrect. Which is the conventional meaning? but now you're trying to use the same symbol to denote the cayley graph. > Is the meaning universal, or does it depend on the author and the > context? the context should make it clear which object (group or graph) the symbols refer to. as martin notes above, these are quite different objects. > 2. I gather from your note and from things that Dan sent me that > one should not list inverses of the generators. For example, > is sufficient and one should not write . But > people conventionally write which includes six processes and > their six inverses. Is this acceptable usage, or should we write > instead? either is acceptable, whether you're referring to groups or cayley graphs. however, for cayley digraphs (directed graphs), the two meanings are quite different. i don't imagine we'll have anything to do with digraphs until someone complains that they can only turn the faces of their cube clockwise, and wants to know some short processes. in our case, "" is preferred, since it's shorter. > As an additional comment, I have frequently written about the Q length > of a process in or the Q+H length of a process in . I think > we would be better served to talk about the length of a process in > or the length of a process in if the generator > notation implies a particular Cayley graph. yes, this terminology is more precise, but the meaning was already clear. mike From BRYAN@wvnvm.wvnet.edu Thu Dec 8 18:01:48 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA24053; Thu, 8 Dec 94 18:01:48 EST Message-Id: <9412082301.AA24053@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 6114; Thu, 08 Dec 94 15:42:38 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 6039; Thu, 8 Dec 1994 15:42:37 -0500 X-Acknowledge-To: Date: Thu, 8 Dec 1994 15:42:36 -0500 (EST) From: "Jerry Bryan" To: Subject: Re: Models for the Cube In-Reply-To: Message of 12/07/94 at 20:45:00 from , Martin.Schoenert@math.rwth-aachen.de (With apologies, retransmitted to correct square brackets trashed by our mailer.) On 12/07/94 at 20:45:00 Martin Schoenert said: >Unfortunately C is *not* a normal subgroup of CG, and therefore CG/C is >*not* a group. If we want to apply group theory, we need a better model. >I argue that G is indeed a good model for the 3x3x3 cube. Well, with great fear and trepidation, let's see if we can't interpret CG/C in such a way that it is a group. I agree that your statement above is correct, but I believe we are interpreting C, G, and CG somewhat differently. I have discussed this subject before, but armed with some better notation suggested via Dan Hoey, I think I can do it again both more accurately and more succinctly. Dan's suggestion is to carefully distinguish which of the various types of cubies we are talking about. I have done a lot of work with (for example) corners-only-cubes-without-centers, corners-only- cubes-with-centers, etc. When we talk about the set C of rotations, Dan suggests specifying such things as C[C] (Corners-only), C[E] (Edges-only), C[C,F] (Corners-plus-Face-centers), etc. The C[C] thing looks funny, using C in two such different ways, but there are only so many letters. I want to reserve lower case c for elements of C, so I will live with C[C]. I would suggest extending the notation to G and Q, so that (for example) the corners-only with Face-centers group we have called GC could instead be called G[C,F] = , and the 2x2x2 cube could be called G[C]= because there are no Face-centers. The "standard Singmaster model" (my terminology) would be written as G[C,E,F] = . (Well, I think Singmaster would write it as G[C,E,F] = , since I think he prefers to accept H turns as single moves.) However, I tend to work with G[C,E] = instead. I consider G[C,E] to be equivalent to G[C,E,F] for most purposes because G fixes the Face-centers, as does M-conjugation. I have described this equivalence before as the Face-centers simply providing a frame of reference that can be provided in other ways. However, when you step outside the friendly confines of G=, it does start to matter whether the Face-centers are there or not. As an example important to this discussion, if you consider CG=, then it makes a considerable difference whether you are talking about CG[C,E] or CG[C,E,F]. For example, G[C,E] = can be simulated on a real cube by removing the color tabs from the Face-centers, by restricting yourself to Q moves only (no whole cube rotations or slices), and by declaring the cube solved only when the Up color is up and the Front color is Front. Notice that with the Face centers absent, you can make the cube look solved even when it isn't. It will be rotated instead, but it won't be solved. This model may seem a little simple-minded. Why are no rotations allowed, and why don't you count it as solved when it looks solved? But computers are simple-minded. My programs only consider things equal when they are literally equal, and equivalence is something I have to program in. As an example I have used before, consider G[C]=, modeled in the real world by a 2x2x2 pocket cube or by removing both the edge and Face-center color tabs from a 3x3x3 cube. Take a solved cube in G[C] and perform RL'. The cube will still look solved, but it will be rotated. The memory cells in my program will not be the same for I as for RL', but I want to treat them as equivalent, as would nearly everybody with a real world 2x2x2 cube in their hands. This is where I have claimed before that a model that treats RL' the same as I is G[C]/C[C]. The idea is that G[C]/C[C] is a group with the identity being C[C] itself (i.e., rotating the cube is "doing nothing".) The proof is fairly simple. From each element (coset) of G[C]/C[C], pick the unique permutation that fixes a particular corner, say UFR, and form a new set G[C]* containing the one element chosen from each coset. The elements of G[C]/C[C] are sets (namely cosets), but the elements of G[C]* are permutations which are also in G[C]. In particular, G[C]* = . Hence, G[C]* is a group. Note that the generators of G[C]* are the twists of those faces which are diagonally opposed to the corner fixed by the selection function from G[C]/C[C] to G[C]*. Hence, the generators fix the same corner as the selection function, showing that is really the same set as G[C]*, namely the set of all cubes in G[C] for which the UFR corner is fixed. Finally, there is an obvious isomorphism between G[C]/C[C] and . Namely, to multiply two cosets, map each to via the selection function, perform the multiplication there using standard cube multiplication, and map the product back to a coset. Hence, G[C]/C[C] is a group. A similar argument applies to G[E]/C[E] except that we have to fix an edge cubie instead of a corner cubie. A similar argument applies to G[C,E]/C[C,E] except we have to fix an edge cubie and restrict C to even permutations. Dan calls the set of even rotations E, so let's call it G[C,E]/E[C,E]. (Still wish we had letters whose use did not conflict so blatantly.) But when we started, we were talking about CG/C, not about G/C. However, notice that when our model does not include Face-centers, we have = , = , and = . (I mean that the groups are equal, not that the Cayley graphs are the same.) Hence, speaking generically of the first two cases, we have C is in G, CG=G, and both CG/C and G/C are groups. In the last case, we have to say E is in G, EG=G, and EG/E is a group. But we can go one step further. Since there are no Face-centers, we can admit Slice moves or C as generators (it doesn't matter which), and we no longer have to restrict ourselves to even rotations. We can say G+[C,E]= and we will have C is in G+, CG+=G+, and CG+/C is a group which is the same size as EG/E. (G+ is twice as big as G, of course.) I guess this must mean that C[C], C[E], and C[C,E] are all normal subgroups of their respective CG's, but that C[C,F], C[E,F], and C[C,E,F] are not. That should not be surprising. Having the Face-centers there only as a frame of reference and never moving is not the same as having them there and really moving (as when you rotate the entire cube). After joining Cube-Lovers, I discovered that others had solved God's algorithm for the 2x2x2 long before me. I was expecting my solution to be 24*48 times smaller than theirs because I was using cosets of C and M-conjugates. But my solution was only 48 times smaller than theirs. By taking both cosets and M-conjugates I really had reduced by 24*48 times. However, everybody else who worked on the problem had modeled it as something like , fixing a corner. (Any other corner would do as well. There are eight conjugate groups, any of which would do as well as any other.) is 24 times smaller than in the first place, and as I said earlier, is equivalent to for most purposes anyway because of the fixed Face-centers. Hence, everybody else had a 24 times head start on me. (At the time, Dan suggested that I was increasing the size of the problem by 24 and then reducing it by 24*48 for a net reduction of 48. But that would only be true if the model were . Since the model was , there really was a reduction of 24*48. But does not really model the 2x2x2 cube, and is 24 times larger than it needs to be in the first place if you are trying to model the 2x2x2.) Modeling cubes without centers such as the 2x2x2 is trickier than it looks because of the requirement that rotations be treated as equivalent. I did it by using cosets of rotations; everybody else did it by fixing a corner. But before I realized all this, I went on a Quixotic chase for a model which would simultaneously be a true model for a 2x2x2 cube and would retain the cubic symmetry of the problem (whatever that means). There are articles in the archives concerning this subject, with the conclusion that no such model is possible because any true model would be isomorphic to , which does not have "cubic symmetry". I guess the "cubic symmetry of the problem" means that you should use M-conjugate classes. Recall that when I solved I used what Dan calls W-conjugate classes because W is the symmetry group for , and W-conjugate classes reduced the size of the problem by four times. This leads me to a question. The way I modeled the 2x2x2, I used M-conjugate classes of cosets and reduced the size of the problem by 48 times. If I were going to model , I would be very inclined not to use M-conjugate classes, but rather to use a subgroup of M which was the symmetry group of . The subgroup would have less than 48 elements, and I would get less than a 48 times reduction in the size of the problem. But a fixed corner model such as is isomorphic to a coset model such as /C[C], and M-conjugates are appropriate to the coset model. Therefore, my analysis of the situation is obviously very flawed. Can anybody see what is wrong? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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