From news@nntp-server.caltech.edu Fri Dec 9 20:34:59 1994 Return-Path: Received: from piccolo.cco.caltech.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10781; Fri, 9 Dec 94 20:34:59 EST Received: from gap.cco.caltech.edu by piccolo.cco.caltech.edu with ESMTP (8.6.7/DEI:4.41) id RAA03400; Fri, 9 Dec 1994 17:34:54 -0800 Received: by gap.cco.caltech.edu (8.6.7/DEI:4.41) id RAA10180; Fri, 9 Dec 1994 17:34:42 -0800 To: mlist-cube-lovers@nntp-server.caltech.edu Path: whuang From: whuang@cco.caltech.edu (Wei-Hwa Huang) Newsgroups: mlist.cube-lovers Subject: Newbie Date: 10 Dec 1994 01:34:37 GMT Organization: California Institute of Technology, Pasadena Lines: 4 Message-Id: <3cb0jd$9tq@gap.cco.caltech.edu> Nntp-Posting-Host: accord.cco.caltech.edu X-Newsreader: NN version 6.5.0 #12 (NOV) Subscribe me to this list, please. -- Wei-Hwa From BRYAN@wvnvm.wvnet.edu Fri Dec 9 22:20:45 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA14904; Fri, 9 Dec 94 22:20:45 EST Message-Id: <9412100320.AA14904@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 4266; Fri, 09 Dec 94 22:20:47 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 5379; Fri, 9 Dec 1994 22:20:47 -0500 X-Acknowledge-To: Date: Fri, 9 Dec 1994 22:20:42 -0500 (EST) From: "Jerry Bryan" To: "Cube Lovers List" Subject: Normal Subgroup Question 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. I responded at great length, showed a group for CG/C, and concluded as follows. >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). This just *has* to be wrong. I just don't see any way that any of the flavors of C are a normal subgroup of their respective flavors of CG. The presence or absence of the Face-centers can't have anything to do with it. I was jumping to the conclusion that since I found a group for some of the flavors of CG/C, that therefore the respective C's must be normal. I have reread my note, and it still looks to me like I found groups for all the CG/C's I discussed. I would invite instruction and correction from any of you group theory experts out there, but here is the way it looks to me. Using G and H generically for a group and subgroup (not necessarily cubes at all), G/H is a group if H is a normal subgroup of G, under the "natural" operation {Xh} * {Yh} = {(XY)h} (where {Xh} etc. denotes all h in H.) Coset notation would be (xH)(yH)=(xy)H. Under these circumstances, G/H is the factor group of H in G. My group operation on the cosets not the "natural" operation. It gets around the fact that C is not normal by picking specific rather than arbitrary elements of the cosets in order to perform the group operation, namely a picking specific element which fixes the same cubie for all cosets. I guess this means that CG/C is not the factor group of C in CG (such a thing being impossible), but by golly it still looks like a group to me under the "unnatural" operation ?? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From mschoene@math.rwth-aachen.de Sat Dec 10 09:15:04 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 AA08876; Sat, 10 Dec 94 09:15:04 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rGSXF-000MPHC; Sat, 10 Dec 94 15:12 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rGSXE-0000PvC; Sat, 10 Dec 94 15:12 PST Message-Id: Date: Sat, 10 Dec 94 15:12 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu In-Reply-To: "Jerry Bryan"'s message of Thu, 8 Dec 1994 15:42:36 -0500 (EST) <9412082301.AA24053@life.ai.mit.edu> Subject: Re: Re: Models for the Cube Jerry Bryan wrote in his e-mail message of 1994/12/08 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. I think that we agree much more than we actually realize, and that it is mostly a matter of language. So your clarification was most welcome, and I hope mine is too. Jerry continued 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. Let's see whether I understand this correct. Let CG again be the complete cube group generated by the face turns and the rotations, let G be its subgroup of index 24 generated by the face turns, and C the subgroup of size 24 generated by the rotations. CG can be represented as a permutation group on 54 points. On this set it makes three orbits, called C(orners), E(dges), and F(ace-centers), of sizes 24, 24, and 6. [A sidenote. Old e-mails in Cube-Lovers often talk about the 12 ``orbits'' of the cube group G in the group that you get when you are allowed to take the cube apart. This group has structure (S(8) 3) (S(12) 2). Strictly speaking, these are not ``orbits'' but ``cosets'' instead.] We can now look at the operation of CG (and C and G) on the 8 sets [], [C], [E], [C,E], [F], [C,F], [E,F], and [C,E,F] (where [X,Y] here means the (disjoint) union of the orbits X and Y). This gives us 8 groups to look at, together with their respective subgroups induced by C and G. Clearly CG[] is trivial, and CG[C,E,F] = CG. Such a group, e.g., CG[C], is a model for what we get when we remove the color tabs from the other orbits, e.g., for CG[C] we would remove the color tabs from the edges and the faces. A little bit of group theory. Each of those 8 groups CG[] is a homorphic image of CG. That means there is a homomorphism from CG to CG[]. This homomorphism is actually very easy to describe: you get the image of an element by simply forgetting what that element does on the other orbits. The kernel of this homomorphism is the subgroup of elements of CG that do nothing on and only permute the points in the other orbits. What this means is that each CG[] is a factor group of CG. Jerry continued 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]. Correct. Since G fixes the faces, G[C,E,F] and G[C,E] are isomorphic. But CG[C,E,F] and CG[C,E] are not isomorphic, and neither are C[C,E,F] and C[C,E]. Jerry continued 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. Maybe a little convention would help. We could say that a cube is *completely solved* if all the up-color tabs are on the up-face, all the right-color tabs are on the right-face, etc. And a cube is *solved up to rotations* if all the tabs on each face have the same color, i.e., if it can be completely solved with a rotation of the entire cube. Talking about the groups, only the identity is completely solved, but all elements in C[] are solved up to rotations. In this language CG[C] is a model for the complete solution of the 2x2x2 cube, and a supplement for C[C] in CG[C] is a model for the solution up to rotations of the 2x2x2 cube. And of course, most of the time we are interested in solutions up to rotations. Jerry continued 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. I agree mostly but not completely. First I claim that we are interested not in the cosets of C[C] in G[C], but rather in the cosets of C[C] in CG[C]. Now since G[C] = CG[C] this doesn't seem to make any difference. But for a different set of orbits, G[] may be different from CG[], and C[] will then not be a subgroup of G[]. So in those cases it doesn't make sense to speak of the cosets of C[] in G[]. Second your usage of G/H. Many group theory textbooks restrict this notation to the case when H is a normal subgroup of G. Others use G/H in general for the set of cosets of H in G. But whenever they write ``the group G/H'' or ``G/H is a group'', they always mean that H is normal in G, and that G/H is the factor group. I would be happy if you wrote about ``the set G[C]/C[C] with the multiplication defined by ... is a group'' instead of ``G[C]/C[C] is a group''. The reason why I think it is important to be carefull is that many properties carry over from G to a proper factor group G/H, but do not carry over from G to ``the set G/C with the multiplication defined by ...''. I shall return to this point below. I agree that G[C]* is indeed a group. You do exactely the same thing that I did in my message. You pick a set of represtatives that forms a subgroup, which I called a supplement for C[C]. Then you define the multiplication using those representatives. I think that it is easier to work with the supplement instead of the structure G[C]/C[C] with the induced multiplication, but that is clearly a matter of taste. Jerry continued A similar argument applies to G[E]/C[E] except that we have to fix an edge cubie instead of a corner cubie. Almost. But there is a tricky problem here. Again G[E] = CG[E], so it doesn't matter whether we talk about G[E]/C[E] (as you prefer) or about CG[E]/C[E] (as I prefer). Again we can find a supplement for C[E] in CG[E], namely the subgroup of all elements of CG[E] that leave a particular edge cubie fixed. Assume that we fix the upper-right edge cubie, then this supplement is . But this does *not* respect costs. That is take an element e of CG[E]. Let r be its representative in , i.e., c e = r, where c is a rotation of the entire cube. The the costs of the two elements, viewed as elements of CG[E] is clearly the same (remember, rotations cost nothing). But the cost of r, viewed as an element of *with this generating system*, may be higher. For example take R[E] * r[E]' (where r is the rotation of the entire cube). In CG[E] this element has cost 1. And this element lies in , since it fixes the upper-right edge cubie. But the cost of this element *with respect to the generating system L[E],D[E],F[E],B[E]* is not 1. We can repair this by choosing a different generating system for , for example the system L[E],D[E],F[E],B[E],R[E]*r[E]',U[E]*u[E]'. So in general a model for the solution up to rotations for a certain set , is a supplement of C[] in CG[], with a generating system that respects costs. Jerry continued 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.) This is the reason why I think that it is better to talk about CG[C,E]/C[C,E]. As you say G[C,E] <> CG[C,E] (it has index 2), and C[C,E] is not a subgroup of G[C,E]. That your model works depends on the fact that their is a bijection between the set CG[C,E]/C[C,E] and G[C,E]/E[C,E]. This follows by a standard argument from the fact that E[C,E] = Intersection( G[C,E], C[C,E] ). Jerry continued 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). It would be most surprising. In fact C[C], C[E], and C[C,E] are *not* normal in their respective CG's. I don't see what face centers should have to do with it. Jerry continued 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.) Allow me to translate this to a more group theoretic language. You are interested in finding God's algorithm for CG[C]. If e is any element of this group, then clearly it has the same costs as (c * e), where c is any element of C[C]. Thus you need only compute the cost for one representative of each right coset (C[C] * e). All those cosets have size 24, so using cosets reduces the problem by a factor 24. However, (c' * e * c) also has the same cost, so you only need one representative of each conjugacy class (e ^ C[C]). Taking those two approaches together means, that you need only look at one representative of the set { c1 * (c2' * e * c2) | c1, c2 in C[C] }. But we can also write this set as { c1 * e * c2 | c1, c2 in C[C] }. Such a set if usually called a *double coset* and written as (C[C]*e*C[C]). Most of those double cosets have size 576 = 24*24, but some are smaller (but of course all sizes are always multiples of 24, since each double coset is the union of single cosets). Thus using double cosets reduces the problem by a factor almost 576. Finally e has the same cost as (x' e x), where x is the reflection. Thus you only need one representative from each set { y' * c1 * e * c2 * y | c1, c2 in C[C], y in M[C] }. This reduces the problem by an total factor almost 1152. Jerry continued 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. Lets first take a look at the 3x3x3 cube, i.e., CG[C,E,F] = CG. In this case you can use G as a supplement for C, i.e., as a system of representatives for the cosets (C * e). Now G is normal in CG, thus you can conjugate the elemenents of G with elements of C and stay in G. So there is a bijection between the representatives of the conjugacy classes of G under the conjugation by C and the representatives for the double cosets (C * e * C). In fact G is normal in MG, and there is a bijection between the representatives of the conjugacy classes of G under the conjugation by M and the representatives for the sets ((C * e * C)^M). This is the basis for applying the ``Lemma that is not Burnside's'' to count the number of such sets, as the real size of the cube. But in the case of the 2x2x2 cube without centers, i.e., CG[C], this is not possible. Finding such a model would mean finding a supplement of C[C] that is normal in CG[G], i.e., is fixed under conjugation by C[C]. And no such supplement exists. Jerry continued 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? Yes I can ;-). The problem is in the statement ``and M-conjugates are appropriate to the coset model''. I think this problem comes from your unusual usage of the notation G[C]/C[C]. If C[C] was a normal subgroup of G[C] and G[C]/C[C] was the proper factor group, then the operation of M-conjugation would carry over from G[C] to the factor group (any such operation carries over to a factor group, provided that the normal subgroup is fixed, which is certainly the case here). But G[C]/C[C] is not the proper factor group, so there is no reason why the M-conjugation should carry over, and in fact it does not. Finally allow to correct a non-standard language again. In group theory one usually does not speak of the symmetry group of another group, but of the *automorphism group* of another group. Moreover you don't want to know the ``subgroup of M which was *the* automorphism group of '', but the ``subgroup of M which was *also a subgroup of* the automorphism group of '', because the automorphism group of is in fact much larger. In other word, you want to know the subgroup of M that fixes . This is a cyclic group of size 3, namely the rotation along the diagonal axis of the cube that goes through your fixed center and cyclically permutes D[C], B[C], and L[C]. 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 Sat Dec 10 09:21: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 AA09060; Sat, 10 Dec 94 09:21:41 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rGSde-000MPHC; Sat, 10 Dec 94 15:19 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rGSdd-0000PvC; Sat, 10 Dec 94 15:19 PST Message-Id: Date: Sat, 10 Dec 94 15:19 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu In-Reply-To: "Jerry Bryan"'s message of Thu, 8 Dec 1994 15:02:33 -0500 (EST) <9412082002.AA14755@life.ai.mit.edu> Subject: Re: Re: Models for the Cube I wrote in my e-mail message of 1994/12/07 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. Jerry Bryan answered in his e-mail message of 1994/12/07 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? Yes I certainly could. I think it is only a matter of taste. You seem to favor the physical model. There the reflection has no real realization, and it makes sense to distinguish between the rotations and the reflection. I look at the problem more from the computational aspect. I view the whole thing as a permutation group, and then there is no real reason to distinguish between the rotations and the reflection (both being ordinary permutations on 54 points). And when working with those groups in GAP, it is certainly a lot more convenient to work in MG and treat all of M uniformly, then to work in CG and to handle the reflection specially. 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 Sat Dec 10 10:13:39 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10971; Sat, 10 Dec 94 10:13:39 EST Message-Id: <9412101513.AA10971@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5452; Sat, 10 Dec 94 10:13:41 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 1045; Sat, 10 Dec 1994 10:13:42 -0500 X-Acknowledge-To: Date: Sat, 10 Dec 1994 10:13:33 -0500 (EST) From: "Jerry Bryan" To: "Cube Lovers List" Subject: Cubic Symmetry of the 2x2x2 (Again) The argument has been made that the 2x2x2 cube (or really any 2Nx2Nx2N) cube cannot have the "symmetry of the cube". In order for a real 2x2x2 cube to have the "symmetry of the cube", you would have to adopt unreasonable rules, such as no rotations (or if you use rotations they have a cost of at least 2) and the cube is only solved when the colors are oriented properly. But a 2x2x2 cube certainly feels like a real cube when you hold it in your hands. I offer the following interpretation that "sort of" gives the 2x2x2 cube the symmetry of the cube. Since I will only be talking about the 2x2x2, I will simplify the notation by talking about C, G, Q, etc. rather than C[C], G[C], Q[C], etc. As I have discussed several times before, my favorite model for the 2x2x2 is G/C (or CG/C, if you prefer; G=CG for the 2x2x2). The group operation is (xC)(yC)=(uv)C, where u and v are the elements of xC and yC, respectively, which fix a particular corner. (xC)(yC)=(xy)C doesn't work because C is not normal. There is an obvious isomorphism between G/C and , where the three q-turns are those which fix the same corner as the selection function for u and v. There are eight corners, and hence there are eight conjugate selection functions and eight conjugate subgroups G_m of the form which fix a particular corner. If you think of mapping G/C simultaneously and in parallel to the all the elements in the set {G_1, G_2, G_3, G_4, G_5, G_6, G_7, G_8}, then in a loose sense you have preserved the cubic nature of the problem. That is, none of the individual G_m's have the same symmetry as the cube, but in a loose sense the entire collection {G_m} does. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From BRYAN@wvnvm.wvnet.edu Sat Dec 10 10:21:06 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AB11211; Sat, 10 Dec 94 10:21:06 EST Message-Id: <9412101521.AB11211@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5482; Sat, 10 Dec 94 10:21:08 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 1260; Sat, 10 Dec 1994 10:21:08 -0500 X-Acknowledge-To: Date: Sat, 10 Dec 1994 10:21:02 -0500 (EST) From: "Jerry Bryan" To: Subject: Re: Re: Models for the Cube In-Reply-To: Message of 12/10/94 at 15:19:00 from , Martin.Schoenert@math.rwth-aachen.de On 12/10/94 at 15:19:00 Martin Schoenert said: >You seem to favor the physical model. There the reflection has no >real realization, and it makes sense to distinguish between the >rotations and the reflection. That is probably an accurate assessment. However, it should be pointed out that the edges can be reflected on a physical model, even though the corners and Face-centers cannot. Mathematically, this means that generates reflections, but and do 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 @mail.uunet.ca:mark.longridge@canrem.com Fri Dec 16 04:19:31 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 AA29461; Fri, 16 Dec 94 04:19:31 EST Received: from portnoy.canrem.com ([198.133.42.17]) by mail.uunet.ca with SMTP id <87818-4>; Fri, 16 Dec 1994 04:20:19 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA00403; Fri, 16 Dec 94 04:16:34 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1C4371; Fri, 16 Dec 94 01:51:35 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Cyclic Decomposition From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.897.5834.0C1C4371@canrem.com> Date: Fri, 16 Dec 1994 01:32:00 -0500 Organization: CRS Online (Toronto, Ontario) I've been working on a new algorithm to find move sequences to reach certain positions on the 3x3x3 cube. The basic idea is to find a sequence such that: (S1 S2 S3... SX) ^N = Goal State where X is the number of moves in the fragment and N is the number of times the fragment is repeated. I call such a process to be "Cyclicly Decomposable". Certain states, such as the 12-flip, require quite a few moves, in fact more moves than possible to search using brute force even when using high-order computers. The best results using the Kociemba algorithm need 28 q turns or 20 q+h turns for the 12-flip. While the cyclic decomposition algorithm (henceforth the CD algorithm for short) usually requires more moves than the Kociemba algorithm it does have an mnemonic advantage. The following is the best result using the CD algorithm to date: p192 2 Flip in face (F1 B1 L1 T1 D1)^6 (30 q) p195 12 Flip (T1 B3 T1 L1 F3 R3)^6 (36 q) Note that both of these processes use 5 of the 6 generators. Some cube positions are extremely resistant to CD but flip and twist patterns are no problem. In particular, the 6 X order 3 pattern does not yield to CD with values of X up to 7. Naturally with N = 1 we can always find one of the optimal paths but I am more interested in cases where N > 1. One may note that with N > 1 using CD processes we are still free to use any number of q turns except a prime number, for which N must be 1, but this should not be too constraining. By relaxing the conditions somewhat we can conceive of sequences which are near-CD, that is CD with a small suffix or prefix: p169 4 Y's Rot + 2 X (F2 B2 D1 L2 R2) ^2 + T1 (11 q+h) By looking at the best sequence the Kociemba algorithm can find for a position, we can count the number of q turns and use this as a starting point for an attempt with CD... p1 6 X order 3 R2 L3 D1 F2 R3 D3 F1 B3 U1 D3 F1 L1 D2 F3 R1 L2 (20 q) Looking at p1 we can infer that possibly X=5 and N=4 may lead to finding a CD process or X=4, N=5 X=10, N=2 X=20, N=2 etc. At the very least we can discount X * N = odd number. -> Mark <- Email: mark.longridge@canrem.com From Wechsler@world.std.com Fri Dec 16 10:23:44 1994 Return-Path: Received: from europe.std.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10847; Fri, 16 Dec 94 10:23:44 EST Received: from world.std.com by europe.std.com (8.6.8.1/Spike-8-1.0) id KAA03983; Fri, 16 Dec 1994 10:23:37 -0500 Received: by world.std.com (5.65c/Spike-2.0) id AA13703; Fri, 16 Dec 1994 10:23:47 -0500 Date: Fri, 16 Dec 1994 10:23:47 -0500 From: Wechsler@world.std.com (Allan C Wechsler) Message-Id: <199412161523.AA13703@world.std.com> To: CRSO.Cube@canrem.com Cc: cube-lovers@life.ai.mit.edu In-Reply-To: Mark Longridge's message of Fri, 16 Dec 1994 01:32:00 -0500 <60.897.5834.0C1C4371@canrem.com> Subject: Cyclic Decomposition In the corner group, (RFU)^5 exchanges corners fur and bur. I only mention this because of all the tools I use, it is the only one that involves a lot of repetition. It's a fossil from my earliest cube solution, c. 1980, which used _only_ repetitive processes. (RFU)^5 is only useful to me because I solve corners first. One-face-first solvers will find this incomprehensible. From ccw@eql12.caltech.edu Fri Dec 16 13:55:58 1994 Return-Path: Received: from EQL12.Caltech.Edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA22563; Fri, 16 Dec 94 13:55:58 EST Date: Fri, 16 Dec 94 10:54:10 PST From: ccw@eql12.caltech.edu Message-Id: <941216105410.25001944@EQL12.Caltech.Edu> Subject: A comment on Cyclic Decomposition To: cube-lovers@life.ai.mit.edu, mark.longridge@canrem.com X-St-Vmsmail-To: ST%"cube-lovers@life.ai.mit.edu" Mark Longridge proposes looking for processes that can be expressed in the form (S1 S2 S3... SX) ^N = Goal State He calls such a processes "Cyclicly Decomposable". I think that the results would be far richer if there was also allowed to be one cube rotation in the subprocess. I know of 2 examples. I will use a * after a move to represent a full cube move. I am a little rusty on this one, and I don't have a cube here to verify it, but (L' R F*) ^ 6 (12q) is (or should be, if I remember it correctly) the Pons Asinorum. We also know that this pattern takes at best 12q, so it is actually optimum. The existance of this process has always made me wonder how many different ways there are to do the Pons, especially with different face effects in the Supergroup. The other one is my favorite process. (L D L' R' F'*)^4 (16q) This twists 3 corners on one face. I suspect this one is also optimum as I have never heard of a process that twists 3 corners in less than 16q. It has one very interesting feature, L' R' F'* can be done as 1 combined two-hand motion. A casual observer may think you are only turning the cube and not see the face turns involved. This makes the process look magic, achieving a state in far fewer apparant moves then people think is possible. This process is so fast and easy to remember that it is what I use while solving. From news@nntp-server.caltech.edu Fri Dec 16 15:36:21 1994 Return-Path: Received: from piccolo.cco.caltech.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA29220; Fri, 16 Dec 94 15:36:21 EST Received: from gap.cco.caltech.edu by piccolo.cco.caltech.edu with ESMTP (8.6.7/DEI:4.41) id MAA19196; Fri, 16 Dec 1994 12:36:15 -0800 Received: by gap.cco.caltech.edu (8.6.7/DEI:4.41) id MAA02485; Fri, 16 Dec 1994 12:36:07 -0800 To: mlist-cube-lovers@nntp-server.caltech.edu Path: txr From: txr@alumni.caltech.edu (Tim Rentsch) Newsgroups: mlist.cube-lovers Subject: Re: Cyclic Decomposition Date: 16 Dec 1994 20:36:05 GMT Organization: California Institute of Technology, Pasadena Lines: 23 Message-Id: <3cstnl$2dj@gap.cco.caltech.edu> References: <60.897.5834.0C1C4371@canrem.com> Nntp-Posting-Host: alumni.caltech.edu X-Newsreader: NN version 6.5.0 #4 (NOV) mark.longridge@canrem.com (Mark Longridge) writes: > Certain states, such as the 12-flip, require quite a few moves, in >fact more moves than possible to search using brute force even when >using high-order computers. The best results using the Kociemba >algorithm need 28 q turns or 20 q+h turns for the 12-flip. I found Mark's post generally interesting and thought provoking. Without detracting from his ideas I would like to comment on the paragraph above. If a certain state (such as the 12 flip) is known to be reachable in no more than 20 moves, then isn't that state within reach of a brute force search? Start one brute force at the initial state, one at the final state, expand the position trees one move at a time until the trees touch. A state 20 moves from start will require a tree (well, two trees) 10 moves deep, which is about 10 billion states. That seems achievable in a reasonable time on fast computers of today. Doesn't it? regards, Tim Rentsch From mreid@ptc.com Fri Dec 16 17:24:16 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 AA07150; Fri, 16 Dec 94 17:24:16 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA08915; Fri, 16 Dec 94 17:22:51 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA27627; Fri, 16 Dec 1994 17:33:48 -0500 Date: Fri, 16 Dec 1994 17:33:48 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9412162233.AA27627@ducie.ptc.com> To: cube-lovers%life.ai.mit.edu@ptc.com Subject: Re: Cyclic Decomposition Content-Length: 2380 tim writes > If a certain state (such as the 12 flip) is known to be reachable > in no more than 20 moves, then isn't that state within reach of > a brute force search? Start one brute force at the initial state, > one at the final state, expand the position trees one move at a time > until the trees touch. A state 20 moves from start will require a > tree (well, two trees) 10 moves deep, which is about 10 billion states. unfortunately, this estimate is too optimistic. the number of positions within 10 face turns of start is more like 2.6 x 10^11. [ keep in mind that while "billion" means 10^9 in the u.s., it may mean 10^12 elsewhere. ] > That seems achievable in a reasonable time on fast computers of today. > Doesn't it? i don't know, but it would be nice if it were possible. i recall that dik winter was doing some work on this front, although i think he was working on "superfliptwist". also, he was using kociemba's algorithm (first stage only). my impression was that this would take too long. (any results here, dik?) however, there's a method similar to the one tim mentions that hasn't received much attention here. i don't have all the details handy, but here's a sketch: the idea is to start with a list of permutations L and to generate (on the fly!) all products p1 p2 (with p1, p2 in the list L) in (lexicographically) increasing order. this means that while the list itself is stored in memory, the list of products (denoted L L) need not be. also, the technique for doing this (which i don't remember offhand) is easily adapted to generate all products q p1 p2 where q is a fixed permutation and p1 p2 are in the list L (q L L), again in (lexicographically) increasing order, and again, on the fly. now let L be the list of all configurations within 5 face turns of start, and let q be "superflip" or "superfliptwist". now simultaneously generate the products L L and q L L in increasing order, and look for common configurations. a common configuration gives p1 p2 = q p3 p4 ==> q = p1 p2 p4^-1 p3^-1 which gives a manuever of (at most) 20 face turns for q. of course, this technique can be used for quarter turns as well. i don't know much about the practicality of implementing this algorithm, but i'd be happy to hear from anyone who's done it, or even thought about it. mike From ccw@eql12.caltech.edu Fri Dec 16 20:47:12 1994 Return-Path: Received: from EQL12.Caltech.Edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA18801; Fri, 16 Dec 94 20:47:12 EST Date: Fri, 16 Dec 94 17:47:01 PST From: ccw@eql12.caltech.edu (Chris Worrell) Message-Id: <941216174701.25001b45@EQL12.Caltech.Edu> Subject: correction on my previous message. To: cube-lovers@life.ai.mit.edu My memory is indeed faulty. I was incorrct about the repeated process which yields the Pons Asinorum. The process I was actually thinking of does not need a cube rotation to make it have a repeated structure. (L' R U' D)^3 There is however an interpretation of the standard Process for the Poms, which can be decomposed into a repeated process by a cube rotation. Denote by "A", turning by 120 degrees around any diagonal, it doesn't matter which one, nor in which direction. (L^2 R^2 A)^3 yields the Pons. From news@nntp-server.caltech.edu Fri Dec 16 23:24:15 1994 Return-Path: Received: from piccolo.cco.caltech.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA01947; Fri, 16 Dec 94 23:24:15 EST Received: from gap.cco.caltech.edu by piccolo.cco.caltech.edu with ESMTP (8.6.7/DEI:4.41) id UAA19585; Fri, 16 Dec 1994 20:24:06 -0800 Received: by gap.cco.caltech.edu (8.6.7/DEI:4.41) id RAA16788; Fri, 16 Dec 1994 17:06:30 -0800 To: mlist-cube-lovers@nntp-server.caltech.edu Path: txr From: txr@alumni.caltech.edu (Tim Rentsch) Newsgroups: mlist.cube-lovers Subject: Re: Cyclic Decomposition Date: 17 Dec 1994 01:06:24 GMT Organization: California Institute of Technology, Pasadena Lines: 29 Message-Id: <3ctdig$gci@gap.cco.caltech.edu> References: <9412162233.AA27627@ducie.ptc.com> Nntp-Posting-Host: alumni.caltech.edu X-Newsreader: NN version 6.5.0 #4 (NOV) mreid@ptc.com (michael reid) writes: >unfortunately, this estimate is too optimistic. the number of positions >within 10 face turns of start is more like 2.6 x 10^11. An upper bound for number of positions reachable after 10 turns is 18 * 12**9 which is 92,876,046,336. Admittedly this number is closer to 2.6e11 than 1e10, but the number is an upper bound. It seems to me I remember reading that the limiting branching factor (for q+h turns) is about 9.5 and is reached rather quickly. The value of 18 * 12 * 12 * 12 * 9.5**6 is 22,864,298,166.0 (according to 'bc'), which should be within reach of brute force algorithms. Unfortunately this approach requires several hundred gigabytes of disk space but that could be spread out over lots of physical machines (parallelizing could also result in speeding up the computation). Anyone know where we could find 1000 machines with a few hundred megabytes free each? Well, maybe not just yet. But soon. regards, Tim Rentsch From BRYAN@wvnvm.wvnet.edu Sat Dec 17 11:10:56 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17733; Sat, 17 Dec 94 11:10:56 EST Message-Id: <9412171610.AA17733@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5988; Sat, 17 Dec 94 11:10:53 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 3919; Sat, 17 Dec 1994 11:10:54 -0500 X-Acknowledge-To: Date: Sat, 17 Dec 1994 11:10:52 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: How Big is Big? Some of the notes in the last day or two about whether or not ten levels deep is too large to search reminded me of a note I have been meaning to send for a long time. Just how big is 4.3*10^19, and can we ever hope to search it all? First of all, 4.3*10^19 is really about 10^18. That is, we could safely confine ourselves to searching M-conjugate classes, and there are about 0.9*10^18 classes, which we might as well call about 10^18. But how big is that? Suppose were trying to buy enough disk space. I claim that you could store each position in a byte with clever indexing. Actually, you could store each position in 5 bits, or 5/8 of a byte, but leave it as a byte per position. Let's say that you can purchase a gigabyte for about 1,000 U.S. Dollars (10^12 bytes for about 10^3 USD). (We are buying good quality used disks for mainframes for about 1,000 USD per gigabyte; new prices are closer to 4,000 or 5,000 USD per gigabyte. Both SCSI and IDE disks for the desktop, PC or UNIX, are just now down to around 500 USD per gigabyte, and I have seen firesale type prices closer to 300 USD per gigabyte). At 10^3 USD per 10^12 bytes, the cost would be 10^9 USD per 10^18 bytes. Well, 10^9 USD is a lot of money, but it is a lot less than the cost of going to the moon, or the cost of an aircraft carrier. In fact, Bill Gates could afford it if he so chose. There are other ways to think about the problem. The size of chess is about 10^75 states, and Go is about 10^120 states. The standard 3x3x3 Rubik's cube is vastly smaller than either of these. In fact, Go (and maybe chess, I can't remember for sure) is usually described as being bigger than the universe. A handy number in these types of comparisons and in determining "how big is the universe" is Avogadro's number, which is about 6*10^23. Avogadro's number is the number of molecules (or atoms, for substances which occur atomically) in the gram molecular weight of a substance. For example, molecular hydrogen has a molecular weight of 2, so 2 grams of hydrogen contain 6*10^23 molecules. Iron is atomic with an atomic weight of 56, so 56 grams of iron contain about 6*10^23 atoms. If you had 56 grams of iron, and if you could store magnetically each cube position in no more than 6*10^5 iron atoms, then you could store the whole Rubik's cube. By comparison to the size of the universe, the mass of the sun is about 10^30 grams, consisting mostly of atomic hydrogen, so there are about (10^30)*(10^23)=10*53 hydrogen atoms in the sun. I can't remember for sure, but I think there are about 10^11 stars in the Milky Way. If the sun is typical star, that would leave about 10^64 hydrogen atoms in the Milky Way. I don't know how many galaxies there are, but we are clearly getting close to the size of Chess at 10^75 being about the same as the size of the universe, and of Go at 10^120 being much larger than the size of the universe. Rubik's cube is small potatoes. A couple of more items: the human genome is being mapped. I cannot remember the exact size of the problem, but I do remember when I read about it that it was a larger problem than Rubik's cube. Finally, the Chronicle of Higher Education had an article in the last few weeks about particle physicists and the Internet. Traditionally, these people send hundreds or thousands of magnetic tapes to each other via standard mail (snail mail to E-mail folks -- but mailing magnetic tapes can yield tremendous data transfer rates if you actually calculate bytes per second). According to the article, the physicists are already sending gigabytes over the Internet. They are planning soon to start sending petabytes (10^15) over the Internet. 10^15 is getting interesting close to the size of Rubik's cube (never mind that I thought that the proper term for 10^15 bytes was terabytes.) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 mreid@ptc.com Sat Dec 17 14:53:48 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 AB28037; Sat, 17 Dec 94 14:53:48 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA09900; Sat, 17 Dec 94 14:52:32 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA27879; Sat, 17 Dec 1994 15:03:32 -0500 Date: Sat, 17 Dec 1994 15:03:32 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9412172003.AA27879@ducie.ptc.com> To: cube-lovers%life.ai.mit.edu@ptc.com Subject: planning in permutation groups Content-Length: 866 here is some more info on the algorithm i briefly described yesterday. the paper i have is "planning and learning in permutation groups", by fiat, moses, shamir, shimshoni and tardos. it appeared in the 30th annual symposium on foundations of computer science, pp 274-9. the paper mentions that they have calculated all identities of length 16 (they count face turns). this means that the algorithm was successfully implemented for the list L of all configurations within 4 face turns of start! also, alan gives a much more detailed description of this algorithm in the archives. see his message of may 27, 1987 "shamir's talk really was about how to solve the cube!" (cube-mail-6) i encourage people to look up the paper and/or alan's message. this is an exciting development, and the lack of attention this idea has received is a shame. regards, mike From BRYAN@wvnvm.wvnet.edu Sat Dec 17 23:44:44 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17750; Sat, 17 Dec 94 23:44:44 EST Message-Id: <9412180444.AA17750@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 7248; Sat, 17 Dec 94 23:44:42 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 9464; Sat, 17 Dec 1994 23:44:42 -0500 X-Acknowledge-To: Date: Sat, 17 Dec 1994 23:44:36 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: How Big is Big? In-Reply-To: Message of 12/17/94 at 12:55:35 from dlitwin@geoworks.com On 12/17/94 at 12:55:35 dlitwin@geoworks.com said: >"Jerry Bryan" writes: >> I claim that you could store each position in a byte with clever >> indexing. Actually, you could store each position in 5 bits, or 5/8 of a >> byte... > Could you explain what you mean by this? You can't mean each >possible cube position because you only get 256 from a byte. Are you >talking about each type of operation you can perform on a cube? I'd buy >that, but I'd think you could store that in 4 bits (12 possible moves). >I'm clearly missing something here. I have talked about this before, but let's have a go at it again. Previously, I have talked about it in terms of corners only or edges only. This time, let's talk about it in terms of whole cubes. In terminology we have used recently, we will talk about representing G[C,E]=. That is, we will only represent corners and edges. There is no need for the purposes of this paper to include Face centers because |G[C,E]| = |G[C,E,F]|. For each cube position, we only need to store the depth, assuming we have some way to index to the proper cell in a data structure containing the depth for each cube position. As long as the depth does not exceed 31, then 5 bits will suffice for each cell. Start with G[C] and G[E] separately (corners only, and edges only). Partition G[C] into equivalence classes of the form {m'(Xc)m} for each m in M (the set of 48 rotations and reflections), for each c in C (the set of 24 rotations), and for each X in G[C]. Partition G[E] into equivalence classes of the form {m'(Yc)m} for each m in M, for each c in C, and for each Y in G[E]. These tasks have already been accomplished via computer search. For each {m'(Xc)m} choose a representative element V, and for each {m'(Yc)m} choose a representative element W. It is not strictly necessary, but it will prove convenient if each representative element is even, and such a choice is always possible. Denote the sets of representative elements as G*[C] and G*[E]. These sets have already been created via computer search. We have |G*[C]|=77802 and |G*[E]|=851625008. The sets G*[Cl and G*[E] will be used as indices, and will have to be stored. But storing them is between 10^12 and 10^13 bytes, which is a drop in the bucket compared to storing 10^18 depths. We can think of a cube in G[C,E] as XY with X in G[C] and Y in G[E]. That is, X is the corners and Y is the edges. Both X and Y are even, or both X and Y are odd, and the choice of odd or even can be thought of as an index which doesn't have to be stored. V=Repr{m'(Xc)m} can be thought of as an index for XY. V has to be stored, but it only has to be stored once for the whole data structure, not once very every position XY for which V=Repr{m'(Xc)m}. Similarly, W=Repr{m'(Yc)m} can be thought of as an index for XY, and W only has to be stored once for the entire data structure. Given V, we can write X=n'(Vd)n for some fixed n in M and for some fixed d in C. Notice that since V is even, the parity of d is the same as the parity of X, and hence there are 12 rather than 24 choices for d. Notice also that while both n and d will always exist, neither is necessarily unique, depending on how "symmetrical" is V. Hence, a selection procedure is necessary to assure that both n and d are unique. d can be thought of as an index for XY, and d does not need to be stored. As for n being an index, see two paragraphs below. Given W, we can write Y=o'(We)o for some fixed o in M and for some fixed e in C. Notice that since W is even, the parity of e is the same as the parity of Y, and hence there are 12 rather than 24 choices for e. Notice also that while both o and e will always exist, neither is necessarily unique, depending on how "symmetrical" is W. Hence, a selection procedure is necessary to assure that both o and e are unique. e can be thought of as an index for XY, and e does not need to be stored. As for o being an index, see the next paragraph. We could think of n and o as both being indices for XY, with both of them having 48 different values. The indices would not have to be stored. However, we can write XY as (n'(Vd)n)(o'(We)o). Any M-conjugate of XY has the same length as XY. If we conjugate by nn' we have n(n'(Vd)n)(o'(We)o)n'=n(n'(Vd)n)n')(n(o'(We)o)n')=(Vd)(p'(We)p), where p=on', p'=no', and p is in M. Hence, there is only one index into M with 48 different values, not two. Putting this all together, we need a table with 2*77802*851625008*12*12*48 cells, and each cell could be 5 bits. The total number of cells is about .916*10^18. The actual number of M-conjugate classes is about .901*10^18. (I am using a slightly unusual decimal point placement in deference to the total size of the table being "about 10^18".) The reason that the table size is a bit larger than the number of M-conjugate classes is that the table will contain some empty cells due to the non-uniqueness of some of the indexing by C and M. The number of cells that will be non-empty *will* in fact be exactly the same as the number of M-conjugate classes. I have talked about indices that would have to be stored, and indices that would not have to be stored. As an example of indices that would have to be stored, consider a table of names and ages. E.g., Name Age Doe, John 25 Evans, Bill 42 Jones, Jane 33 Smith, Sarah 21 You can think of the names as indices into the ages, and the names do have to be stored. On the other hand, think of storing N floating point numbers in an array X, with I as an index for I in 1..N. You would write this in a program as something like X[I]. The index I would have to be stored once, I suppose, but it would not have to be stored with each X. Similarly, in the proposed structure for storing all of God's Algorithm, the indices V and W would have to be stored, but the parity index 1..2 would not have to be stored, the rotation index 1..12 for V would not have to be stored, the rotation index 1..12 for W would not have to be stored, and the M conjugation index 1..48 for V or W (but not both) would not have to be stored. But even though the indices V and W would have to be stored, they would only have to be stored once for the whole program, not for each cube position. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 Sun Dec 18 10:23: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 AA01444; Sun, 18 Dec 94 10:23:35 EST Message-Id: <9412181523.AA01444@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 8075; Sun, 18 Dec 94 10:23:33 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 2308; Sun, 18 Dec 1994 10:23:33 -0500 X-Acknowledge-To: Date: Sun, 18 Dec 1994 10:23:32 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: How Big is Big? In-Reply-To: Message of 12/17/94 at 22:46:08 from txr@alumni.caltech.edu On 12/17/94 at 22:46:08 txr@alumni.caltech.edu said: >In mlist.cube-lovers you write: >>For each cube position, we only need to store the depth, assuming >>we have some way to index to the proper cell in a data structure >>containing the depth for each cube position. As long as the depth >>does not exceed 31, then 5 bits will suffice for each cell. >I think depth modulo 3 is enough, since depth of adjacent positions >will differ by at most one -- just move in the direction of depth >getting less. So we could get by with 2 bits per cell. >regards, >Tim Rentsch You are certainly correct. And as Dan Hoey pointed out to me via private E-mail once upon a time, for Q turns you can get it down to only one bit by storing (depth modulo 4)/2 because you can infer the state of the low order bit from the parity of cube position. (Parity of the cube position equals the parity of the depth for Q turns, but not for Q+H turns.) But I tend to think that certain kinds of interesting analyses of a data base for the entire God's Algorithm would be greatly assisted by storing the entire depth. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 mouse@collatz.mcrcim.mcgill.edu Sun Dec 18 16:02:19 1994 Return-Path: Received: from Collatz.McRCIM.McGill.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA14014; Sun, 18 Dec 94 16:02:19 EST Received: (root@localhost) by 13839 on Collatz.McRCIM.McGill.EDU (8.6.8.1 Mouse 1.0) id PAA13839 for cube-lovers@ai.mit.edu; Sun, 18 Dec 1994 15:56:10 -0500 Date: Sun, 18 Dec 1994 15:56:10 -0500 From: der Mouse Message-Id: <199412182056.PAA13839@Collatz.McRCIM.McGill.EDU> To: cube-lovers@ai.mit.edu Subject: Re: How Big is Big? > [Physicists] are planning soon to start sending petabytes (10^15) > over the Internet. 10^15 is getting interesting close to the size of > Rubik's cube (never mind that I thought that the proper term for > 10^15 bytes was terabytes.) I thought it was kilo 10^3 mega 10^6 giga 10^9 tera 10^12 peta 10^15 exa 10^18 except, of course, that as applied to quantities that tend to come in powers of two, like bytes, they normally refer to 2^10, 2^20, 2^30, 2^40, 2^50, and 2^60 instead. (This is a common problem when buying disks: manufacturers like to quote capacities in terms of powers of ten, because it makes their disks seem larger than they really are. A "2.1G" disk, for example, typically has a capacity of about 2.1e9 bytes...which is really only about 1.956Gb. The error can be roughly estimated as 2.5% per power of 10^3: 2.5% for K, 5% for M, 7.5% for G, etc. Semiconductor memory manufacturers generally get this right, probably because doing other than powers of two would be hard for them.) It also means that a certain well-known manufacturer of data drives for 8mm videotape is being extremely arrogant with their choice of name. :-) As for the 10^18 bytes of storage estimated (probably only about half that, if we consider that we really need only 5*.9e18 bits, less if we resort to some of the clever coding tricks recently mentioned)...that's about a gig of storage each across a million machines. The net's not quite to the point where it can be done distributed. Yet. :-) Incidentally, someone mentioned that you need only store two bits, or even only one if you don't use H turns, per position, because you don't need to know more than how to get closer to Start...and then said that it would be nice to have the full depth available nevertheless. If you have this enormous database of .9e18 positions available in the compact form, all that's needed to get the full depth for a position is to take the short walk through the tree back to Start. Also note that the Cube database storage size requires the highest prefix we have. Time to get SI to think up some more, I guess :-) der Mouse mouse@collatz.mcrcim.mcgill.edu From dik@cwi.nl Sun Dec 18 16:43:21 1994 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA15510; Sun, 18 Dec 94 16:43:21 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Sun, 18 Dec 1994 22:43:19 +0100 Received: by boring.cwi.nl id ; Sun, 18 Dec 1994 22:43:19 +0100 Date: Sun, 18 Dec 1994 22:43:19 +0100 From: Dik.Winter@cwi.nl Message-Id: <9412182143.AA04820=dik@boring.cwi.nl> To: cube-lovers@ai.mit.edu Subject: Re: How Big is Big? > Also note that the Cube database storage size requires the highest > prefix we have. Time to get SI to think up some more, I guess :-) They did: 10^-24 y yocto 10^-21 z zepto 10^+21 Z zetta 10^+24 Y yotta so now you can talk about yotta bytes. dik From BRYAN@wvnvm.wvnet.edu Sun Dec 18 17:32:44 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17736; Sun, 18 Dec 94 17:32:44 EST Message-Id: <9412182232.AA17736@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 8903; Sun, 18 Dec 94 17:32:41 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 5951; Sun, 18 Dec 1994 17:32:41 -0500 X-Acknowledge-To: Date: Sun, 18 Dec 1994 17:32:40 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: How Big is Big? In-Reply-To: Message of 12/18/94 at 15:56:10 from , mouse@collatz.mcrcim.mcgill.edu On 12/18/94 at 15:56:10 der Mouse said: >> [Physicists] are planning soon to start sending petabytes (10^15) >> over the Internet. 10^15 is getting interesting close to the size of >> Rubik's cube (never mind that I thought that the proper term for >> 10^15 bytes was terabytes.) >I thought it was > kilo 10^3 > mega 10^6 > giga 10^9 > tera 10^12 > peta 10^15 > exa 10^18 You are correct, of course. In retrospect, the aspect of the article in the Chronicle that waylaid me (and which I still find puzzling) is the absence of any mention of "tera". It is a giant jump from "giga" to "peta", skipping "tera" on the way. But "giga" and "peta" were juxtaposed in the article. I have known how big "tera" is for years -- can't believe I screwed it up. It makes me wonder if the article had it right. It is reasonable to jump from gigabytes to petabytes in one fell swoop? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 mouse@collatz.mcrcim.mcgill.edu Mon Dec 19 03:55:27 1994 Return-Path: Received: from Collatz.McRCIM.McGill.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07255; Mon, 19 Dec 94 03:55:27 EST Received: (root@localhost) by 15068 on Collatz.McRCIM.McGill.EDU (8.6.8.1 Mouse 1.0) id DAA15068 for cube-lovers@ai.mit.edu; Mon, 19 Dec 1994 03:49:19 -0500 Date: Mon, 19 Dec 1994 03:49:19 -0500 From: der Mouse Message-Id: <199412190849.DAA15068@Collatz.McRCIM.McGill.EDU> To: cube-lovers@ai.mit.edu Subject: Re: How Big is Big? > In retrospect, the aspect of the article in the Chronicle that > waylaid me (and which I still find puzzling) is the absence of any > mention of "tera". It is a giant jump from "giga" to "peta", > skipping "tera" on the way. But "giga" and "peta" were juxtaposed in > the article. [...] It makes me wonder if the article had it right. > It is reasonable to jump from gigabytes to petabytes in one fell > swoop? IMO it is not. Without seeing it, I can't be sure, but it seems likely that it's Just Another Dumb Reporter. Perhaps someone took notes and wrote down 10^15 instead of 10^12, and then looked up the name for 10^15 and didn't notice the basic inconsistency of jumping from Gb to Pb without stopping at Tb. Hmmm, this is drifting off-topic for cube-lovers.... der Mouse mouse@collatz.mcrcim.mcgill.edu From BRYAN@wvnvm.wvnet.edu Mon Dec 19 08:48:32 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA14147; Mon, 19 Dec 94 08:48:32 EST Message-Id: <9412191348.AA14147@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 0349; Mon, 19 Dec 94 08:48:28 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 2224; Mon, 19 Dec 1994 08:48:29 -0500 X-Acknowledge-To: Date: Mon, 19 Dec 1994 08:48:28 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: How Big is Big? In-Reply-To: Message of 12/17/94 at 11:10:52 from BRYAN@wvnvm.wvnet.edu One more correction to this giga, tera, peta, nonsense. Since 10^9 bytes of disk space cost about 10^3 USD, then 10^18 bytes would cost about 10^12 USD. This is more than Bill Gates could afford, more than going to the moon, more than an aircraft carrier, and indeed is of the same order of magnitude as the entire United States federal budget. Disk prices need to come down several orders of magnitude before we can think about storing 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 From Wechsler@world.std.com Mon Dec 19 09:59:54 1994 Return-Path: Received: from europe.std.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17311; Mon, 19 Dec 94 09:59:54 EST Received: from world.std.com by europe.std.com (8.6.8.1/Spike-8-1.0) id JAA02475; Mon, 19 Dec 1994 09:59:52 -0500 Received: by world.std.com (5.65c/Spike-2.0) id AA05068; Mon, 19 Dec 1994 10:00:04 -0500 Date: Mon, 19 Dec 1994 10:00:04 -0500 From: Wechsler@world.std.com (Allan C Wechsler) Message-Id: <199412191500.AA05068@world.std.com> To: mouse@collatz.mcrcim.mcgill.edu Cc: cube-lovers@ai.mit.edu In-Reply-To: der Mouse's message of Sun, 18 Dec 1994 15:56:10 -0500 <199412182056.PAA13839@Collatz.McRCIM.McGill.EDU> Subject: How Big is Big? Date: Sun, 18 Dec 1994 15:56:10 -0500 From: der Mouse > [Physicists] are planning soon to start sending petabytes (10^15) > over the Internet. 10^15 is getting interesting close to the size of > Rubik's cube (never mind that I thought that the proper term for > 10^15 bytes was terabytes.) I thought it was kilo 10^3 mega 10^6 giga 10^9 tera 10^12 peta 10^15 exa 10^18 [...] Also note that the Cube database storage size requires the highest prefix we have. Time to get SI to think up some more, I guess :-) (Warning to Cube-Lovers: this is off the topic, but it's a digression I can never resist. Alan is going to come over to my house and soap my windows for this, I just know it.) They _have_ thought up some more -- this was in Science News about 18 months ago. But the ones they thought up are absolutely awful, and I want to take this opportunity to advertise my own suggestions. First note the following relationships, which I believe are entirely the result of coincidence: te(t)ra 1000^4 pe(n)ta 1000^5 (h)exa 1000^6 In each case, the prefix for 1000^n looks like the neo-greek prefix for n, with the second-to-last consonant deleted. I merely propose that we continue this scheme: he(p)ta 1000^7 o(c)to 1000^8 (en)nea 1000^9 I admit to a fudge with n=9, but I like neabytes better than eneabytes, and the prefix E was already taken by n=6. I wanted to keep up the unique sequence of prefixes: K, M, G, T, P, E, H, O, N. For those who care, megameters are good for measuring small planets, gigameters for big planets and stars, and terameters for solar systems. A petameter is about a tenth of a light year, and so it's good for measuring near interstellar distances; exameters are good for the 100-ly range, galaxies should be measured with hetameters, and intergalactic distances with otometers. Current theory says the universe is considerably smaller than one neameter. From @mitvma.mit.edu:will4086@UDCVAX.BITNET Wed Dec 21 18:48:20 1994 Return-Path: <@mitvma.mit.edu:will4086@UDCVAX.BITNET> Received: from mitvma.mit.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA05936; Wed, 21 Dec 94 18:48:20 EST Received: from MITVMA.MIT.EDU by mitvma.mit.edu (IBM VM SMTP V2R2) with BSMTP id 2190; Wed, 21 Dec 94 18:48:14 EST Received: from UDCVAX.BITNET (NJE origin MXMAILER@UDCVAX) by MITVMA.MIT.EDU (LMail V1.2a/1.8a) with BSMTP id 3314; Wed, 21 Dec 1994 18:48:15 -0500 Received: by UDCVAX.BITNET (MX V3.3 VAX) id 3192; Wed, 21 Dec 1994 18:50:19 EST Sender: will4086%UDCVAX.BITNET@mitvma.mit.edu Date: Wed, 21 Dec 1994 18:50:19 EST From: will4086%UDCVAX.BITNET@mitvma.mit.edu To: CUBE-LOVERS@life.ai.mit.edu Message-Id: <0098948C.2AA66560.3192@UDCVAX.BITNET> Subject: MAILING LIST I WOULD LIKE TO BE PLACED ON THE MAILING LIST FOR THE SUBJECTS YOUR GROUPS DISCUSS.THIS IS THE FIRST E-MAIL MESSAGE THAT I HAVE SENT,SO PLEASE DON'T LAUGH AT THIS PARAGRAPH. From dik@cwi.nl Wed Dec 21 20:16:25 1994 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA09542; Wed, 21 Dec 94 20:16:25 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Thu, 22 Dec 1994 02:16:04 +0100 Received: by boring.cwi.nl id ; Thu, 22 Dec 1994 02:16:03 +0100 Date: Thu, 22 Dec 1994 02:16:03 +0100 From: Dik.Winter@cwi.nl Message-Id: <9412220116.AA03233=dik@boring.cwi.nl> To: cube-lovers@life.ai.mit.edu Subject: CFF 35 CFF #35 came out, the editors expected it in December and it came out in December! Good for them. Summary of contents. Vic Stok: Paving stones. A new twist to polyominos. Squares are linked in a brick-wall fashion. Lee Sallows: Alphamagic squares. About the construction of magic squares where, if you replace each entry with the value of the word length, the result is magic again. The most surprising for me was one square that was alphamagic in both Welsh and Norwegian. Torsten Sillke and Bernhard Wiezorke: Stacking Identical Polyspheres. Part 1: Tetrahedra. Discusses many possible and impossible tetrahedra that can be packed by polyspheres. Jan de Ruiter: Braiding. An article about a contest problem issued on the Dutch 1992 Cube Day. It involves (amongst others) the number of ways a braid can be made from a varying number of bundles of hair. Joop van der Vaart: IPP 1994 Impressions. Impressions from the 1994 International Puzzle Party in Seattle. Leo Links: Cube Day Impressions. Impressions of the 1994 Dutch Cube Day in Stavoren. Result of contest 24 (CFF 33, Cross Pattern Piling). Anneke Treep: Anti-slide... a winner! A short note about the Hikimi Wooden Puzzle Competition. Wil Strijbos from the Netherlands came second with his puzzle. Start with 15 1x2x2 square pieces and a 4x4x4 box. Pack the pieces in the box so that no piece can slide. Do the same with 14, 13, 12, 11 (actually the article has a typo here). Columns: Mark Peters: Books and Magazines (reviews) Edward Hordern: What's Up? (details some new puzzles and other news) ------ CFF (Cubism For Fun) is the newsletter published by the Nederlands Kubus Club NKC (Dutch Cubists Club). Information can be obtained from one of the editors: Rik van Grol . 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). -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924098 home: bovenover 215, 1025 jn amsterdam, nederland; e-mail: dik@cwi.nl From jkato@tmastb.eec.toshiba.co.jp Wed Dec 21 20:43:59 1994 Received: from inet-tsb.toshiba.co.jp by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA11701; Wed, 21 Dec 94 20:43:59 EST Received: from tis2.tis.toshiba.co.jp (tis2) by inet-tsb.toshiba.co.jp (5.67+1.6W/2.8Wb) id AA22586; Thu, 22 Dec 94 10:43:45 JST Received: from tis10.tis.toshiba.co.jp (tis10) by tis2.tis.toshiba.co.jp (5.67+1.6W/6.4J.6-R05) id AA24598; Thu, 22 Dec 94 10:44:15 JST Received: from eecisa.eec.toshiba.co.jp (eecisa) by tis10.tis.toshiba.co.jp (5.67+1.6W/6.4J.6-MHS-CNTML-R1) id AA10538; Thu, 22 Dec 94 10:44:29 JST Received: from tmastb.eec.toshiba.co.jp by eecisa.eec.toshiba.co.jp (4.1/6.4J.6-R1) id AA15739; Thu, 22 Dec 94 10:35:37 JST Received: by tmastb.eec.toshiba.co.jp (4.0/6.4J.6-R1) id AA02582; Thu, 22 Dec 94 10:42:11 JST Date: Thu, 22 Dec 94 10:42:11 JST From: jkato@tmastb.eec.toshiba.co.jp (Toshi Kato) Return-Path: Message-Id: <9412220142.AA02582@tmastb.eec.toshiba.co.jp> To: cube-lovers@life.ai.mit.edu Subject: IPP #15 To: International Puzzle Collectors Dear Sirs, 15th International Puzzle collectors' Party(15th IPP) will be taken place on April 15-16,1995 in Tokyo,Japan and optional HAKONE tour on April 17. Have you received an invitation letter of 15th IPP from Nob Yoshigahara? And then, you have done to reply to Nob, haven't you? So, thanks. If you did not yet, please answer by express snail mail or fax or e-mail, as soon as possible. We are looking forward you come to Japan. Thank you, Toshi(Junk) Kato --------------------------------------JUNK: jkato@tmastb.eec.toshiba.co.jp (Notice)If you interest in Puzzle KONWAKAI(Academy of recreatinal mathe- matics,Japan), you may attend the meeting on April 22,1995 for a guest. From mmoss@panix.com Thu Dec 22 10:45:49 1994 Return-Path: Received: from panix2.panix.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA14655; Thu, 22 Dec 94 10:45:49 EST Received: by panix2.panix.com id AA13543 (5.67b/IDA-1.5 for cube-lovers@life.ai.mit.edu); Thu, 22 Dec 1994 10:45:48 -0500 From: Matthew Moss Message-Id: <199412221545.AA13543@panix2.panix.com> Subject: UNSUBSCRIBE To: cube-lovers@life.ai.mit.edu (Cube Mailing List) Date: Thu, 22 Dec 1994 10:45:48 -0500 (EST) X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 40 Please unsubscribe me. mmoss@panix.com From magnum@cyberstore.ca Thu Dec 22 13:23:33 1994 Return-Path: Received: from yvr.cyberstore.ca by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA22499; Thu, 22 Dec 94 13:23:33 EST Received: from [198.70.153.8] (ylw-ppp-8.cyberstore.ca [198.70.153.8]) by yvr.cyberstore.ca (8.6.9/8.6.9) with SMTP id KAA23820 for ; Thu, 22 Dec 1994 10:23:24 -0800 X-Sender: ylwm0169@cyberstore.ca Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Thu, 22 Dec 1994 10:23:58 -0800 To: cube-lovers@life.ai.mit.edu (Cube Mailing List) From: magnum@cyberstore.ca (Darryl EJ Ruff) unsubscribe Darryl EJ Ruff, Dir. Magnum Results Corp. PO Box 692, Stn A Kelowna, BC Canada V1Y 7P4 Ring: 604/769-6169 Fax: 604/769-6158 Internet: magnum@cyberstore.ca "..If We Fail To Achieve Superior Results, We Won't Accept Your Money.." From epaytl@epa.ericsson.se Thu Dec 22 16:34:29 1994 Return-Path: Received: from mailgate.ericsson.se by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA02346; Thu, 22 Dec 94 16:34:29 EST Received: from epa.epa.ericsson.se (epa.epa.ericsson.se [146.11.8.1]) by mailgate.ericsson.se (8.6.9/1.0) with SMTP id WAA05712 for ; Thu, 22 Dec 1994 22:34:26 +0100 Received: from brsw006.epa.ericsson.se.epa.ericsson.se by epa.epa.ericsson.se (4.1/SMI-4.1-EPA1.6) id AA14797; Fri, 23 Dec 94 08:34:21 DST Date: Fri, 23 Dec 94 08:34:21 DST From: epaytl@epa.ericsson.se (Y T - T/ZA) Message-Id: <9412222134.AA14797@epa.epa.ericsson.se> To: cube-lovers@life.ai.mit.edu Subject: UNSUBSCRIBE Please unsubscribe me. epaytl@epa.ericsson.se From alan@curry.epilogue.com Thu Dec 22 23:38:49 1994 Return-Path: Received: from curry.epilogue.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA29296; Thu, 22 Dec 94 23:38:49 EST Received: (from alan@localhost) by curry.epilogue.com (8.6.8/8.6.6) id XAA07218; Thu, 22 Dec 1994 23:41:33 -0500 Date: Thu, 22 Dec 1994 23:41:33 -0500 Message-Id: <22Dec1994.232120.Alan@LCS.MIT.EDU> From: Alan Bawden Sender: Cube-Lovers-Request@ai.mit.edu To: mmoss@panix.com, epaytl@epa.ericsson.se, magnum@cyberstore.ca Cc: Cube-Lovers@ai.mit.edu In-Reply-To: Matthew Moss's message of Thu, 22 Dec 1994 10:45:48 -0500 (EST) <199412221545.AA13543@panix2.panix.com> Subject: UNSUBSCRIBE From: Matthew Moss Date: Thu, 22 Dec 1994 10:45:48 -0500 (EST) Please unsubscribe me. mmoss@panix.com Date: Thu, 22 Dec 1994 10:23:58 -0800 From: Darryl EJ Ruff unsubscribe Darryl EJ Ruff, Dir. Magnum Results Corp. PO Box 692, Stn A Kelowna, BC Canada V1Y 7P4 Ring: 604/769-6169 Fax: 604/769-6158 Internet: magnum@cyberstore.ca "..If We Fail To Achieve Superior Results, We Won't Accept Your Money.." Date: Fri, 23 Dec 94 08:34:21 DST From: Y T - T/ZA Please unsubscribe me. epaytl@epa.ericsson.se I have removed all three of you from the Cube-Lovers mailing list. Note, please, that all three of you sent your requests to be removed to Cube-Lovers as a whole. You should have sent them to me, Cube-Lovers-Request@AI.MIT.EDU, instead of bothering the entire list. This was all clearly explained in the introductory note I sent you when you first subscribed (earlier this month for two of you). This is, in fact, a wide-spread Internet convention. If you can remember it, you can often avoid looking like an idiot in front of hundreds of people. I'm sorry to bother everybody else on Cube-Lovers by CC'ing this note to you all, but this way I can perhaps prevent more copy-cat repetitions of the same annoying mistake. REMEMBER: SEND SUBMISSIONS TO: Cube-Lovers@AI.MIT.EDU SEND ADMINISTRATIVE CORRESPONDENCE TO: Cube-Lovers-Request@AI.MIT.EDU GOT IT? From ba05133@bingsuns.cc.binghamton.edu Fri Dec 23 10:24:30 1994 Return-Path: Received: from bingsuns.cc.binghamton.edu (bingnfs1.cc.binghamton.edu) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA19786; Fri, 23 Dec 94 10:24:30 EST Received: from podsun7 by bingsuns.cc.binghamton.edu (5.0/SMI-4.0) id AA02035; Fri, 23 Dec 1994 10:20:35 -0500 From: ba05133@bingsuns.cc.binghamton.edu Received: by podsun7 (5.0/BING1.0) id AA01392; Fri, 23 Dec 1994 10:21:46 -0500 Message-Id: <9412231521.AA01392@podsun7> Subject: "unsubscribe" To: cube-lovers@life.ai.mit.edu Date: Fri, 23 Dec 1994 10:21:44 -0500 (EST) X-Mailer: ELM [version 2.4 PL24] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 25 Please unsubscribe me. From BRYAN@wvnvm.wvnet.edu Fri Dec 23 18:26: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 AA10284; Fri, 23 Dec 94 18:26:02 EST Message-Id: <9412232326.AA10284@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 0778; Fri, 23 Dec 94 18:25:59 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 5031; Fri, 23 Dec 1994 18:25:58 -0500 X-Acknowledge-To: Date: Fri, 23 Dec 1994 18:25:57 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Antipodal Processes With the help of a suggestion from Dan Hoey, I can now provide processes for the 27 antipodal positions of that are unique up to W-conjugancy. (It is the positions that are unique up to W-conjugancy, not necessarily the processes.) Without further ado, here are processes which generate each of the 27 positions. 1 R U U R R U' R U' R U' R U R' U R U R' U' R R U' R' U R U 2 R' U R' U R' U R R U' R' U' R' U' R U' R' R' U' R R U' R' U R U 3 R R U R' U R U' R' U R' R' U R R U' U' R R U R R U R R U' 4 U' R U R' U R U' R' U' R' R' U R' U' R U U R' U R' U' R' U R U' 5 R' R' U U R U R U' R U' U' R' U R R U' R R U' R' U R' U R' U' 6 U' R R U R' U R' R' U' R' U U R U' R' U R R U R R U R' U' R 7 U R' U R' U R U U R' U' R R U R' U' R' U R R U R' U R U' R 8 R' U R' U' U' R U' R U' U' R' U R' U R' R' U' R U R U R U' R U 9 U R U' R U R R U' R U' R' U R U' R' R' U U R' R' U' R U' R R 10 U' R R U R U U R' U' R' U R U' R' R' U' U' R' U' R' U' R' U R U' 11 R' U R U R' U' R U R' U' U' R' U' R R U U R' U R U R U' R' R' 12 R U U R' U U R' U R U' R' U R' U' R U' R' U' R' U R U' R R U 13 R R U R R U' R U' U' R U' R R U' R' R' U' R R U' R U' R R U 14 U' R' U' R' U' R' U R R U' R U' R U' R U' R' U R U' U' R U U R 15 R R U' R' R' U' R U U R' U U R' R' U' R' U' U' R' R' U' R U' U' R 16 U R' U R' R' U' R U' R U U R R U' R U R' U' R U' R' U' R R U' 17 U' R U' U' R' R' U' R U' R U' R U' R R U R' R' U' R' R' U' R' R' U' 18 R U U R U R U' R' U R' U R U' R R U' R' U' R U U R U' U' R' 19 R' U R' U' U' R U' R U' R' R' U U R U' R' U R U' R U R U U R' 20 U R R U' R R U' R' U' R' U U R' U R' U R U U R' U R U' R R 21 R' U R' U' R' U R U U R' U R' U R' U' R U' R' U R U R' U R R 22 U R U U R U' R U R' U' R U U R U' R U' R' R' U R R U R U 23 R' U U R U R' U R' U R U R' U' R R U' R U' U' R' U R R U R 24 R' U R' U' R R U U R' U R U' R' R' U U R' U R' U' U' R U U R 25 U R' R' U U R U R U' U' R U' R U U R' U R' U' U' R' U R R U 26 U' R' U R U' R' U U R R U R' U R' U R' U' U' R R U' R' U' R' R' 27 R U' R' U' U' R R U' R' U' R U' R U' U' R' U' R' R' U' R U' R R U' The 27 processes are in the same order as the 27 positions I posted on 11 November this year. However, I want to repost the 27 positions anyway. I found a formatting inconsistency in that posting. Generally speaking, when you unfold the cube for printing with the Back above, you can choose to print the Back face right-side-up or up-side-down, and up-side-down makes more sense to me. All my screen displays work that way, and it makes the cubies move smoothly under repeated applications of the R or L operators. However, I discovered that the print program I used for the 11 November posting printed the edge facelets of the Back face right-side- up. That wouldn't have been so bad, I suppose, but at the same time I printed the corner facelets correctly as up-side-down. So herewith I reprint the 27 antipodal positions with all the Back faces correctly up-side-down. BBL BBL BBU BBU BBU BBF LRF RRF LRR 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 --------------------------------------------------------------- BBU BBR BBU BBF BBU BBF DRR BRB 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 ---------------------------------------------------------------- BBR BBU BBB BBU BBU BBU LRD RLF FRF 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 ---------------------------------------------------------------- BBR BBR BBL BBF BBU BBU FFR URU DRF 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 ------------------------------------------------------------------ BBR BBF BBF BBU BBU BBU URU FRF FRF 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 -------------------------------------------------------------- BBF BBR BBR BBU BBU BBU DRL URR FRD 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 -------------------------------------------------------------- BBB BBU BBU BBU BBU BBU FRL RRF BRR 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 --------------------------------------------------------------- BBB BBB BBD BBU BBF BBU URU UFD LRF 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 ---------------------------------------------------------------- BBD BBF BBR BBF BBF BBF BFB UFF LFR 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 From BRYAN@wvnvm.wvnet.edu Fri Dec 23 20:55:24 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA15546; Fri, 23 Dec 94 20:55:24 EST Message-Id: <9412240155.AA15546@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 0980; Fri, 23 Dec 94 20:55:21 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 5731; Fri, 23 Dec 1994 20:55:21 -0500 X-Acknowledge-To: Date: Fri, 23 Dec 1994 20:55:19 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Antipodal Processes Here are the 16 antipodal processes for . Also, as in the case of , I am including replacement position diagrams that include a correction for the Back face so that both the corners and edges are up-side-down. Q+H turners will like these processes because of the way turns of the U face alternate with turns of the R face. I have performed a few of the processes on a real cube (as opposed to on a computer screen), and I find the alternating faces to be quite pleasant somehow or other. 1 R' U R2 U R U2 R U R U2 R' U2 R U2 R' U2 R2 U R2 U 2 U' R U' R2 U' R2 U' R U' R2 U2 R U R U' R U R U2 R2 3 U R U2 R U' R U2 R2 U2 R2 U R U R2 U2 R U' R U R2 4 R' U2 R' U R U' R2 U' R2 U' R' U R' U' R' U' R U' R' U2 5 R' U2 R2 U' R U2 R' U' R U R' U2 R' U2 R' U' R' U2 R U 6 R U R U' R U R2 U R2 U R' U' R U2 R U2 R U R' U 7 R2 U' R U2 R U2 R U' R' U' R U2 R U R2 U R' U R U2 8 U' R' U R' U R' U R2 U' R' U' R' U R' U R' U R2 U' R' 9 R U2 R' U R' U R U' R U R' U2 R' U2 R U' R U' R' U2 10 U' R' U2 R2 U2 R' U R' U2 R' U' R U R' U R U' R' U R2 11 U' R' U' R' U2 R2 U2 R2 U R2 U R2 U' R2 U2 R' U' R U2 R' 12 R2 U' R2 U2 R' U' R2 U' R U R2 U2 R2 U R U2 R U' R' U 13 R U2 R' U' R U' R' U' R2 U' R U2 R U R2 U R' U2 R U 14 U2 R' U R2 U' R' U' R2 U' R U R' U2 R' U2 R2 U R' U2 R' 15 U' R U2 R' U2 R U' R U' R U2 R' U' R U2 R2 U R U R2 16 U' R2 U2 R' U R' U2 R U' R2 U2 R' U2 R U R2 U' R2 U2 R2 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 BBU BBB BBF BBD BBU FBR LFR BRR 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 -------------------------------------------------------------- BBL BBB BBB BBU BBU BBU DRF FRF FFD 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 ----------------------------------------------------------- BBF BBU UFB 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 From kotani@cc.tuat.ac.jp Mon Dec 26 05:33:46 1994 Received: from mail01.cc.tuat.ac.jp (mail01.tuat.ac.jp) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA20405; Mon, 26 Dec 94 05:33:46 EST From: kotani@cc.tuat.ac.jp Received: by mail01.cc.tuat.ac.jp (4.1/6.4JAIN-930819) id AA00817; Mon, 26 Dec 94 13:11:23 JST Date: Mon, 26 Dec 94 13:11:23 JST Return-Path: Message-Id: <9412260411.AA00817@mail01.cc.tuat.ac.jp> To: cube-lovers@life.ai.mit.edu Cc: kotani@cc.tuat.ac.jp In-Reply-To: ba05133@bingsuns.cc.binghamton.edu's message of Fri, 23 Dec 1994 10:21:44 -0500 (EST) <9412231521.AA01392@podsun7> Subject: "unsubscribe" Please unsubscribe me. From jkato@tmastb.eec.toshiba.co.jp Mon Dec 26 22:45:54 1994 Received: from inet-tsb.toshiba.co.jp by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA21328; Mon, 26 Dec 94 22:45:54 EST Received: from tis2.tis.toshiba.co.jp (tis2) by inet-tsb.toshiba.co.jp (5.67+1.6W/2.8Wb) id AA03648; Tue, 27 Dec 94 12:45:37 JST Received: from tis10.tis.toshiba.co.jp (tis10) by tis2.tis.toshiba.co.jp (5.67+1.6W/6.4J.6-R05) id AA10356; Tue, 27 Dec 94 12:46:08 JST Received: from eecisa.eec.toshiba.co.jp (eecisa) by tis10.tis.toshiba.co.jp (5.67+1.6W/6.4J.6-MHS-CNTML-R1) id AA27988; Tue, 27 Dec 94 12:46:23 JST Received: from tmastb.eec.toshiba.co.jp by eecisa.eec.toshiba.co.jp (4.1/6.4J.6-R1) id AA14678; Tue, 27 Dec 94 12:36:57 JST Received: by tmastb.eec.toshiba.co.jp (4.0/6.4J.6-R1) id AA00285; Tue, 27 Dec 94 12:44:00 JST Date: Tue, 27 Dec 94 12:44:00 JST From: jkato@tmastb.eec.toshiba.co.jp (Toshi Kato) Return-Path: Message-Id: <9412270344.AA00285@tmastb.eec.toshiba.co.jp> To: cube-lovers@life.ai.mit.edu Subject: GreyhoundBus Puzzle This is a sliding block puzzle that I thought. +---+---+---+---+---+ |[N]|[U]|[S]|[H]|[U]| $@!N(JProblem$@!O(J +---+---+---+---+---+ Left figure is starting condition.$@!!(J |[O]|###| |###|[G]| Make a sequence,"GREYHOUNDBUS",with minimum step. +---+---+---+---+---+$@!!!!(J |[B]|[Y]|[R]|[D]|[E]| Note: Vacant room is only one.$@!!(J +---+---+---+---+---+ ### are not moved. If you can get answer, please write it to me or on Cube-Lovers ML. Toshi(Junk) Kato, Japan --------------------------------------JUNK: jkato@tmastb.eec.toshiba.co.jp From BRYAN@wvnvm.wvnet.edu Tue Dec 27 16:55: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 AA00248; Tue, 27 Dec 94 16:55:19 EST Message-Id: <9412272155.AA00248@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 1728; Tue, 27 Dec 94 11:23:07 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 7330; Tue, 27 Dec 1994 11:23:07 -0500 X-Acknowledge-To: Date: Tue, 27 Dec 1994 11:23:06 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Normal Subgroups of G Recently, there was some discussion of whether the set C of twenty-four rotations is a normal subgroup of the cube group G=. It isn't, but I decided to write up some information about normal subgroups as it relates to the cube. Most of the following is from Frey and Singmaster. Any good stuff is theirs. Any crud that sneaks in is mine. If H is any subgroup of G, a right coset of H in G is a set {hX} for some fixed X in G and for all h in H. Similarly, a left coset of H in G is a set {Xh}. Right cosets may be denoted as Hx, and left cosets by xH. In general, a right coset Hx is not equal to a left coset xH. But if we have Hx=xH for all x in G, then H is a normal subgroup of G. An alternative definition is H is normal if x'Hx=H for every x in G. The definitions are equivalent, and Frey and Singmaster give as a theorem Hx=xH for every x in G if and only if x'Hx=H for every x in G. It should be noted that H normal does not imply that the elements h of H commute with the elements x of G. That is, just because Hx=xH we do not necessarily have hx=xh for every h in H (or even for any h in H other than the identity). However, I think it is fair to characterize a normal subgroup as commuting "globally" with G, even if it does not commute "locally". On the other hand, if a subgroup H does commute "locally" (i.e., if hx=xh for all h in H and all x in G), then H is certainly normal. Normal groups serve a function with respect to finite groups analogous to the function served by prime numbers with respect to natural numbers. First of all, any finite group always has at least two trivial normal subgroups, namely the group itself and the group containing only the identity. Second, a finite group containing normal subgroups may be "factored" in a fashion analogous to prime numbers factoring composite numbers. A finite group containing no normal subgroups is called simple, analogous to numbers with no factors being called prime. The cube group G does not have very many normal subgroups, but it does have a few. The first place to look for normal subgroups is to look for subgroups with index 2. That is, look for subgroups that are half as big a G. Such a subgroup is the subgroup A of even permutations. ("A" stands for "Alternating", I think.) It is easy to see that A is normal. If x is even, then Ax=xA=A. if x is odd, then Ax=xA=Abar, where Abar is the set (not group!) of odd permutations. Similarly, any subgroup H with index 2 is normal. If the index of H in G is 2, then H partitions G into two equal size sets H and Hbar. If x is in H, then Hx=xH=H. If x is in Hbar, then Hx=xH=Hbar. If we may digress briefly to the set M of 48 rotations and reflections, then there are three subgroups of M with index 2. In Dan Hoey's taxonomy, they are called C, A, and H. We may categorize the elements of M as even or odd, and as rotations or reflections. There are 12 even rotations, 12 odd rotations, 12 even reflections, and 12 odd reflections. If we take 12 even rotations and 12 odd rotations, we have C. So C is a normal subgroup of M, even if it is not a normal subgroup of G. If we take 12 even rotations and 12 even reflections, we have A. This A (a subgroup of M) is not to be confused with the A we have already talked about which is a subgroup of G. But I think the name derives from the same source ("Alternating") in either case. If we take 12 even rotations and 12 odd reflections, we have H. Returning to G, the next two normal subgroups are Ac which leaves the set of edges fixed, and Ae which leaves the set of corners fixed. Ac is even on the corners, and Ae is even on the edges, in order to conserve parity. Note that both Ac and Ae are normal subgroups of A as well as of G. I suppose that what is going on with Ac and Ae is obvious enough, but I want to talk about it for a minute anyway. I most typically think of an equation such as X=RLUD'R as meaning something to the effect that "X" is a shorthand *name* for the collection of five processes (in order) R, L, U, D', and R. But I still tend to think of the processes as distinct. However, from the point of view of group theory, X is a single operation which exists in its own right just as do the quarter turns. With a physical cube, you cannot perform an operation in Ac or Ae without making a fairly long sequence of quarter turns. For example, something so simple as performing FF on the corners while leaving the edges fixed is non-trivial. But from the point of view of group theory, we can easily find a single permutation X[C,E] such that X[C]=FF[C] while X[E]=I[E]. Indeed, from the point of view of group theory, you are never more than one move from Start. That is, if you are at X, the one move which will always solve the cube is X'. It is only if you are asked to decompose X' into generators such as quarter-turns that the question of how far from Start you are makes any sense. If a subgroup H of G is normal, the left cosets form a group under the operation (xH)(yH)=(xy)H. This group is called the factor group of H in G or the quotient group of G by H, and is denoted as G/H. Martin Schoenert recently clarified that while there may be more than one way to define an operation on cosets such that they form a group, the notation G/H is usually reserved for the case where the operation is (xH)(yH)=(xy)H. The factor group G/A contains two elements, and is isomorphic to any group containing only two elements. We may write it as ={A,Abar}, where A is the identity of the group. The factor group G/Ac is isomorphic to the set of all permutations on the edges (which we have written as G[E] in the recent past). The factor group G/Ae is isomorphic to the set of all permutations on the corners (which we have written as G[C] in the recent past). Since Ac and Ae are normal subgroups of A, we may write A/Ac and A/Ae which are isomorphic to Ae and Ac, respectively. We can find normal subgroups of Ac and Ae. The set At of all permutations in Ac which leave all corner locations fixed except for twisting some of them is a normal subgroup of Ac. The set Af of all permutations in Ae which leave all edge locations fixed except for flipping some of them is a normal subgroup of Ae. (This twists and flips have to follow the normal rules of conservation of twist and flip, of course.) This completes the list of normal subgroups. I will now give Frey and Singmaster's proof that we are done, while interposing some questions of my own for the cube theory experts out there. My first question is that Frey and Singmaster do not state that At and Af are normal subgroups of G. It seems obvious that they are. However, is the formal argument that (for example) At is a normal subgroup of Ac and Ac is a normal subgroup of G; hence, At is a normal subgroup of G? How analogous is the factoring of groups by normal subgroups to the factoring of composite numbers by prime numbers? Continuing with Frey and Singmaster, we may write Ac/At and Ae/Af, where Ac/At is isomorphic to the group Asc which leaves the corners sane and Ae/Af is isomorphic to the group Ase which leaves the edges sane. "Sane" is a term used by Frey and Singmaster in their proof of conservation of twist and flip. In general, it is easy to see if a cubie is twisted or flipped when it is home, but it is not so easy to see if it is twisted or flipped when it is not home. Their proof (and the others I have seen) define a frame of reference so that you can tell if a cube is twisted or flipped when it is not home. A cubie which is not twisted or flipped in this frame of reference is sane. Asc and Ase are not normal subgroups of Ac and Ae, respectively. (I tend to think that the reason they are not normal is related to the fact that the frame of reference required to define sane positions is not unique.) However, Asc and Ase are isomorphic to well known groups. The group Sn of all permutations of n objects is the n-element symmetric group. The subgroup An of all even permutations of n objects is the n-element alternating group (there is that word "alternating" again!). Asc is isomorphic to A8 (there being eight corner cubies) and Ase is isomorphic to A12 (there being twelve edge cubies). A famous result from Abel and Galois is that An does not have any non-trivial normal subgroups for n >= 5. Hence, we have reduced G to normal subgroups which have no more normal subgroups, and we are done. I guess my questions are as follows: 1) why must we restrict ourselves to alternating groups? 2) For example, just as we found three subgroups of M with index 2, might we not find other subgroups of G with index 2 than the one we found? 3) Might we not find a normal subgroup of G with some index other than 2, e.g., with index 3? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 mreid@ptc.com Tue Dec 27 19:49:45 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 AA06219; Tue, 27 Dec 94 19:49:45 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA18097; Tue, 27 Dec 94 19:48:22 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA16989; Tue, 27 Dec 1994 20:00:04 -0500 Date: Tue, 27 Dec 1994 20:00:04 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9412280100.AA16989@ducie.ptc.com> To: Cube-Lovers%ai.mit.edu@ptc.com Subject: Normal Subgroups of G Content-Length: 3023 jerry writes [ ... ] > My > first question is that Frey and Singmaster do not state that At and > Af are normal subgroups of G. It seems obvious that they are. indeed. > However, is the formal argument that (for example) At is a normal > subgroup of Ac and Ac is a normal subgroup of G; hence, At is a > normal subgroup of G? but this argument is not valid. your question might be rephrased: if H is a normal subgroup of G and K is a normal subgroup of H, does it follow that K is a normal subgroup of G ?? the answer is no. here's an easy counterexample: let G be the alternating group A_4, H the subgroup of order 4 {e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)}, and K the subgroup {e, (1 2)(3 4)}. it is easy to see that H is normal in G and K is normal in H. however, if x is any three cycle (for example), xK != Kx. [ ... ] > "Sane" is a term used by Frey and Singmaster > in their proof of conservation of twist and flip. In general, it > is easy to see if a cubie is twisted or flipped when it is home, > but it is not so easy to see if it is twisted or flipped when it > is not home. Their proof (and the others I have seen) define a > frame of reference so that you can tell if a cube is twisted or > flipped when it is not home. A cubie which is not twisted or > flipped in this frame of reference is sane. here's a completely different proof of "conservation" which doesn't use any frame of reference. instead of thinking of permutations of edge cubies, think of permutations of the facelets of the edges. any quarter turn induces two four cycles of these edge facelets, which is an even permutation. thus, any legal position has an even permutation of the edge facelets. however, a single flipped edge is just a two cycle of edge facelets, an odd permutation, and therefore is not a legal position. my proof for conservation of twist is slightly more sophisticated, but i think it's worthwhile. the group of legal corner states may be viewed as a subgroup of the wreath product S_8 wr C_3. we have a natural homomorphism S_8 wr C_3 ---> C_3 (*) defined by (s, c_1, ... , c_8) |--> c_1 + ... + c_8 (the cyclic group C_3 is written additively). it is easy to see that this is a homomorphism, but it uses the fact that C_3 is abelian. (in general, we have a natural homomorphism G wr H ---> H^ab ( = H / [H, H] ) defined in the same way.) conservation of corner twist is equivalent to saying that all legal corner states are in the kernel of the map given in (*). however, any quarter turn has order 4, so its image in C_3 must be the identity. thus all quarter turns lie in the kernel, and therefore the same is true of all legal positions. (actually, i've cheated slightly here. we actually need a frame of reference in order to view the group of corner states as a subgroup of S_8 wr C_3.) mike From BRYAN@wvnvm.wvnet.edu Tue Dec 27 22:46:45 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA13741; Tue, 27 Dec 94 22:46:45 EST Message-Id: <9412280346.AA13741@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 2172; Tue, 27 Dec 94 14:26:46 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 9642; Tue, 27 Dec 1994 14:26:46 -0500 X-Acknowledge-To: Date: Tue, 27 Dec 1994 14:26:45 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Squares Group On 9 Aug 1994, Mark Longridge posted God's Algorithm results for the squares group consisting entirely of 180 degree turns. Mark invited corroboration. The following will serve to verify Mark's results, and will also provide the same information for the M-conjugacy classes of . Notice that the ratio of cube positions to M-conjugacy classes never gets very close to 48. Hence, there are a significant number of positions in at each level of the search tree that are at least somewhat "symmetrical". M Branching Cube Branching Ratio of Level Conjugate Factor Positions Factor Cubes to Classes M Classes 0 1 1 1 1 1 1 6 6 6 2 2 2 27 4.5 13.5 3 5 2.5 120 4.4444 24 4 18 3.6 519 4.3250 28.8333 5 56 3.1111 1932 3.7225 34.5000 6 162 2.8929 6484 3.3561 40.0247 7 482 2.9753 20310 3.1323 42.1369 8 1258 2.6100 55034 2.7097 43.7472 9 2627 2.0882 113892 2.0695 43.3544 10 4094 1.5584 178495 1.5672 43.5992 11 4137 1.0105 179196 1.0039 43.3154 12 2231 0.5393 89728 0.5007 40.2187 13 548 0.2456 16176 0.1803 29.5182 14 114 0.2080 1488 0.0920 13.0526 15 16 0.1404 144 0.0968 9 Total 15752 663552 42.1249 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From mschoene@math.rwth-aachen.de Fri Dec 30 09:20:21 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 AA05461; Fri, 30 Dec 94 09:20:21 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rNi90-000MPDC; Fri, 30 Dec 94 15:17 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rNi8z-00025fC; Fri, 30 Dec 94 15:17 WET Message-Id: Date: Fri, 30 Dec 94 15:17 WET From: "Martin Schoenert" To: Cube-Lovers@ai.mit.edu In-Reply-To: "Jerry Bryan"'s message of Tue, 27 Dec 1994 11:23:06 EST <9412272155.AA00248@life.ai.mit.edu> Subject: Re: Normal Subgroups of G Jerry Bryan wrote in his e-mail message of 1994/12/27 Recently, there was some discussion of whether the set C of twenty-four rotations is a normal subgroup of the cube group G=. It isn't, but I decided to write up some information about normal subgroups as it relates to the cube. Most of the following is from Frey and Singmaster. Any good stuff is theirs. Any crud that sneaks in is mine. Very good. The lattice of normal subgroups of G is not too complicated and relates nicely to the structure of this group. Allow me to throw in my $0.02. Nitpicking alert! C is not even a subgroup of G=. It is a subgroup of CG. But not a normal one. Jerry continued It should be noted that H normal does not imply that the elements h of H commute with the elements x of G. That is, just because Hx=xH we do not necessarily have hx=xh for every h in H (or even for any h in H other than the identity). However, I think it is fair to characterize a normal subgroup as commuting "globally" with G, even if it does not commute "locally". On the other hand, if a subgroup H does commute "locally" (i.e., if hx=xh for all h in H and all x in G), then H is certainly normal. In group theory there this distinction is made by using the terms *normal* and *central* (even though globally and locally are perhaps more descriptive names). If xH = Hx, then x is said to *normalize* H. The set of all elements that normalize H is called the *normalizer* of H, usually written N_G(H). It is easy to see that N_G(H) is a subgroup of G containing H. If every x of G normalizes H, then H is said to be *normal* in G. Of course H is normal in G, if and only if N_G(H) = G. If xh = hx for every h in H, then x is said to *centralize* H. The set of all elements that centralize H is called the *centralizer* of H, usually written C_G(H). It is easy to see that C_G(H) is again a subgroup of G, but it need not contain H (it contains H if and only if H is abelian). If every x of G centralizes H, then H is said to be *central* in G. Of course H is central in G, if and only if C_G(H) = G. Furthermore it is easy to see that H is central, if and only if H is a subgroup of C_G(G), which is the set of those elements in G that commute with all elements in G. C_G(G) is called the *center* of G. And as you say, a central subgroup is also normal, but a normal subgroup need not be central. If N1 and N2 are two normal subgroups of G, then it is easy to see that the intersection of N1 and N2 and the closure of N1 and N2 are both normal subgroups too. Thus the set of normal subgroups of G is closed w.r.t. intersection and closure. In other words, the set of normal subgroups forms a lattice. I shall draw the lattice of normal subgroups of G below. Jerry continued Normal groups serve a function with respect to finite groups analogous to the function served by prime numbers with respect to natural numbers. First of all, any finite group always has at least two trivial normal subgroups, namely the group itself and the group containing only the identity. Second, a finite group containing normal subgroups may be "factored" in a fashion analogous to prime numbers factoring composite numbers. A finite group containing no normal subgroups is called simple, analogous to numbers with no factors being called prime. This is correct. Allow me a few more remarks. Groups are composed from simple groups, which correspond to primes. The simple groups have been classified. There are several families (the alternating groups A_n are one such family), and 26 sporadic simple groups. This classification is one of the outstanding mathematical achievements. It is estimated that the complete proof is about 10000 pages long (distributed over several papers, books, Ph.D. thesis, etc.). And then there are the ways in which those simple groups can be composed. In the case of natural numbers, this is very simple. The fundamental theorem tells us, that there is, up to the order, just one way in which any natural number is composed from primes. In the case of groups it is much more difficult. There is still a theorem which tells us that the composition factors of a group are determined up to order. But not any order will do. For example the symmetric group S_3 of size 6, has a factor group C_2 over a normal subgroup C_3, but it cannot be decomposed with a factor group C_3 over a normal subgroup C_2. Furthermore given a certain set of composition factors and a certain order, there may be several groups that decompose in this way. For example the cyclic group C_6 can also be decomposed with a factor group C_2 over a normal subgroup C_3. Even in the simplest case, groups of prime power size, which decompose as a sequence of cyclic groups C_p, is so difficult that they have not been classified (and maybe never will). Jerry continued The cube group G does not have very many normal subgroups, but it does have a few. The first place to look for normal subgroups is to look for subgroups with index 2. That is, look for subgroups that are half as big a G. Such a subgroup is the subgroup A of even permutations. ("A" stands for "Alternating", I think.) It is easy to see that A is normal. If x is even, then Ax=xA=A. if x is odd, then Ax=xA=Abar, where Abar is the set (not group!) of odd permutations. Similarly, any subgroup H with index 2 is normal. If the index of H in G is 2, then H partitions G into two equal size sets H and Hbar. If x is in H, then Hx=xH=H. If x is in Hbar, then Hx=xH=Hbar. ... and later on ... The factor group G/A contains two elements, and is isomorphic to any group containing only two elements. We may write it as ={A,Abar}, where A is the identity of the group. This is correct. There is another way to obtain A, which is also very instructive. Let G be any group. Let g1 and g2 be two elements of G. Then the element g1^-1 * g2^-1 * g1 * g2 is called the commutator of g1 and g2, and is usually written as [g1,g2]. Now let g be any element of G. Then g^-1 [g1,g2] g = g^-1 g1^-1 g2^-2 g1 g2 g = (g^-1 g1^-1 g) (g^-1 g2^-1 g) (g^-1 g1 g) (g^-1 g2 g) = (g^-1 g1 g)^-1 (g^-1 g2 g)^-1 (g^-1 g1 g) (g^-1 g2 g) = [ (g^-1 g1 g), (g^-1 g2 g) ]. Thus the conjugate of a commutator is again a commutator. It follows that the subgroup generated by all commutators of all pairs of elements of G is a normal subgroup. This subgroup is called the *commutator subgroup* or *derived subgroup* of G, and is usually written G'. It is the minimal normal subgroup of G, such that the factor group G/G' is an abelian group. Minimal means that for each normal subgroup N of G such that G/N is an abelian group, G' is a subgroup of N. In the case of the cube group G' is A. I shall use G' instead of A. Jerry continued If we may digress briefly to the set M of 48 rotations and reflections, then there are three subgroups of M with index 2. In Dan Hoey's taxonomy, they are called C, A, and H. We may categorize the elements of M as even or odd, and as rotations or reflections. There are 12 even rotations, 12 odd rotations, 12 even reflections, and 12 odd reflections. If we take 12 even rotations and 12 odd rotations, we have C. So C is a normal subgroup of M, even if it is not a normal subgroup of G. If we take 12 even rotations and 12 even reflections, we have A. This A (a subgroup of M) is not to be confused with the A we have already talked about which is a subgroup of G. But I think the name derives from the same source ("Alternating") in either case. If we take 12 even rotations and 12 odd reflections, we have H. In the case of M, M' is a subgroup of index 4. And the factor group M/M' is isomorphic to the group { (), (1,2)(3,4), (1,3)(2,4), (1,4)(2,3) }. This group is usually called C_2^2, because it is the direct product of two cyclic groups of size 2. This group has three (normal) subgroups of index 2, which correspond to the three normal subgroups of M Jerry described. Jerry continued Returning to G, the next two normal subgroups are Ac which leaves the set of edges fixed, and Ae which leaves the set of corners fixed. Ac is even on the corners, and Ae is even on the edges, in order to conserve parity. Note that both Ac and Ae are normal subgroups of A as well as of G. ... and later on ... The factor group G/Ac is isomorphic to the set of all permutations on the edges (which we have written as G[E] in the recent past). The factor group G/Ae is isomorphic to the set of all permutations on the corners (which we have written as G[C] in the recent past). This is again typical. If we have a permutation group G that has more than one orbit, then the stabilizer of each orbit is a normal subgroup of G (which may or may not be trivial). And the group G is a subdirect product of the factor groups over those normal subgroups. Time for the first picture (apologies to all that have no large screen, but I want to add more to it later without cluttering it too much). GCE /|\ 2 X G X / \|/ \ 2 / G' \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ GE ~ G[E] / / \ / 2 / / GE' / / / G[C] ~ GC / / 2 \ / / GC' / \ / \ / \ / \ / \ / 12!/2 2^11 \ / 8!/2 3^7 \ / \ / \ / \ / \ / \ / \ / \ / <1> Let GC be the operation of G on the corners, which is isomorphic to the factor group G/GE' = G[C], and GE be the operation of G on the edges, isomorphic to the factor group G/GC' = G[E] (this distinction between GC and G[C] and GE and G[E] is subtle and not very important). Let GCE be the direct product of GC and GE. G is a subdirect product of GC and GE, so it is a subgroup of GCE. It is a subgroup of index 2. G has a subgroup of index 2, namely G', which Jerry called A above. The two stabilizers are GC' and GE', which Jerry called Ac and Ae above. They are in fact the derived subgroups of GC and GE. Note that GCE has two more (normal) subgroups of index 2, namely and . And G' is the derived subgroup of CGE. So GCE/GCE' is again isomorphic to C_2^2. Jerry continued Since Ac and Ae are normal subgroups of A, we may write A/Ac and A/Ae which are isomorphic to Ae and Ac, respectively. G' (aka A) is in fact the direct product of GC' (aka Ac) and GE' (aka Ae). And the standard isomorphism theorem tells us that G'/GC' ~ GE' and G'/GE' ~ GC'. Jerry continued We can find normal subgroups of Ac and Ae. The set At of all permutations in Ac which leave all corner locations fixed except for twisting some of them is a normal subgroup of Ac. The set Af of all permutations in Ae which leave all edge locations fixed except for flipping some of them is a normal subgroup of Ae. (This twists and flips have to follow the normal rules of conservation of twist and flip, of course.) This completes the list of normal subgroups. I will now give Frey and Singmaster's proof that we are done, while interposing some questions of my own for the cube theory experts out there. I haven't seen what Frey and Singmaster prove. But this is not true. Together with the trivial normal subgroup G and <1> you have listed 7 normal subgroups, but G has indeed 13 normal subgroups. Jerry continued My first question is that Frey and Singmaster do not state that At and Af are normal subgroups of G. It seems obvious that they are. However, is the formal argument that (for example) At is a normal subgroup of Ac and Ac is a normal subgroup of G; hence, At is a normal subgroup of G? How analogous is the factoring of groups by normal subgroups to the factoring of composite numbers by prime numbers? This is not true, and Michael Reid gave the smallest counterexample. Group theory would certainly be a lot easier if this was true, but probably also a lot less challenging. But there is a similar argument. If M is a normal subgroup of a group N that is invariant under all automorphisms of N, then M is called *characteristic*. For example N' is always a characteristic subgroup of N. If N is a subgroup of a group G, and M is a characteristic subgroup of N, then M is normal in G. Also if N is a characteristic subgroup of G, and M is a characteristic subgroup of N, then M is also a characteristic subgroup of G. This actually happens here, At and Af are characteristic in GC' and GE', so they are normal in G. But this is not so easy to prove, it is simpler to verify directly that At and Af are normal in G (or use the fact that they are again stabilizers of appropriate operations of G). Jerry continued: I guess my questions are as follows: 1) why must we restrict ourselves to alternating groups? 2) For example, just as we found three subgroups of M with index 2, might we not find other subgroups of G with index 2 than the one we found? 3) Might we not find a normal subgroup of G with some index other than 2, e.g., with index 3? I got A as the derived subgroup of G. Since this is the minimal normal subgroup such that the factor group is abelian, there cannot be another normal subgroup of index 2 or 3. But there can be other normal subgroups with non-abelian factor groups, and indeed there are. The rest of this message describes how one can find all normal subgroups of G. My approach may or may not be equal to Frey and Singmaster's. Let us first consider GC. This group is a subgroup of index 3 in the wreath product C_3 S_8. This wreath product is isomorphic to the group of the following elements ( c_1, c_2, c_3, c_4, c_5, c_6, c_7, c_8; p ) where the c_i are in {0,1,2} and p is a permutation in S_8. Multiplication of those elements is defined as follows (c_1,c_2,...,c_8;p) (d_1,d_2,...,d_8;q) := ( c_1 + d_{1^p}, c_2 + d_{2^p}, ..., c_8 d_{8^p}; p * q ) where d_{i^p} denotes d_j, where j is the image of i under the permutation p, and c_i + d_j is the sum of c_i and d_j modulo 3. p * q is simply the product of p and q in S_8. So you first permute the components of the second element with the permutation of the first element, then sum componentwise, and finally multiply the two permutations. Clearly C_3 S_8 has 3^8 8! elements. GC is the subgroup of those elements of C_3 S_8 for which c_1+c_2+...+c_8 = 0 (mod 3). It is easy to see that the set of all 3^7 elements (c_1,c_2,...,c_8,) of GC forms a normal subgroup of GC. I shall call this subgroup VC (V because VC is in fact a vector space), Jerry called this subgroup At. Next I shall show that no proper subgroup of VC can be a normal subgroup of GC. Suppose that H is a normal subgroup of VC, and let x = (x_1,x_2,...,x_8;) be any non-trivial element of H. Because 1+1+...+1 <> 0 (mod 3) and 2+2+...+2 <> 0 (mod 3), there are two components x_i and x_j which are different. An easy calculation shows y := (0,0,...,0;(i,j))^-1 * x^-1 * (0,0,...,0;(i,j)) * x has y_i = 1 and y_j = 2 (or the other way around). Since H is supposed to be normal, y must also be in H. Furthermore the 6 elements zk := (0,0,...,0;(j,k))^-1 * y * (0,0,...,0;(j,k)) where k <> j and k <> i all have zk_i = 1 and zk_k = -1. Again since H is supposed to be normal, they must all lie in H. But y and those 6 elements are obviously linearly independent, i.e., form a basis for VC. In particular it follows that H = VC. So no proper subgroup of VC is a normal subgroup of GC. Now let N be any normal subgroup of GC. Then the intersection of N and VC must be a normal subgroup of GC contained in VC. Thus there are only two possibilities for this intersection; it can be VC (i.e. N contains VC) or it can be trivial. Assume first that N contains VC. Then N/VC must be a normal subgroup of GC/VC. But GC/VC is S_8, which has only three normal subgroups, namely S_8, A_8 (= S_8'), and <1>. Thus we have three normal subgroups containing VC, namely GC, GC', and VC. On the other hand assume that N intersects trivially with VC. Then the closure M of N and VC must be one of the three normal subgroups given above. The isomorphism theorem tells us that M/N ~ VC. GC does not have a factor group isomorphic to VC, since its largest abelian factor group is GC/GC' of size 2. GC' also does not have a factor group isomorphic to VC, since it has no non-trivial abelian factor group at all. So M must be VC, and N must be trivial. All in all GC has 4 normal subgroups, GC, GC', VC, and <1>. Basically the same argument works for GE. But there is one exception. Namely VE has one normal subgroup of size 2 , generated by the element (1,1,...,1;). You may not recognize this element, but it is in fact the superflip, which flips all twelve edges. I shall call this subgroup Z. Thus GE has 5 normal subgroups GE, GE', VE, Z, and <1>. Now we are ready to return to G resp. GCE. The normal subgroups of GCE are direct or subdirect products of normal subgroups of GC and GE. For a direct product we take a normal subgroup NC of GC and a normal subgroup NE of GE and take their direct product, i.e., their closure in GCE. For a subdirect product we must take a normal subgroup NC of GC and a normal subgroup NE of GE and ``glue'' together a common factor group F of NC and NE. But there are only two cases where a normal subgroup of GC and a normal subgroup of GE have a common factor group. Once case is where NC = GC and NE = GE and F = C_2, and we get G as a subdirect product. The other case is NC = GC and NE = Z and F = C_2. All in all, we get the following lattice of normal subgroups of GCE. GCE /|\ X G X / \|/ \ / G' \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ X / / \ / \ / / X \ / / / \ \ X / / \ \ / \ / / \ \ / X / \ GE ~ G[E] / / \ / \ / 2 X / \ / GE' /|\ / \ / / G[C] ~ GC + X \ / / 2 \|/ \ \ / / GC' \ \ / / \ \ \ / / \ \ \ / / 12!/2 \ \ X / 8!/2 \ \ / \ / \ \ / \ / \ \ / \ / \ X \ / \ / \ \ / VC \ VE \ \ / \ \ / 2^10 3^7 \ \ / \ Z \ / 2 <1> (Looks nice, doesn't it?) Bear with me, we are almost done. We only need one more step, namely to show that the normal subgroups of GCE that lie in G are exactely the normal subgroups of G. One direction is obvious, the normal subgroups of GCE that lie in G are also normal subgroups of G. But we need to show that any normal subgroup of G is also a normal subgroup of GCE. Assume then that N1 is a normal subgroup of G that is not *not* normal in GCE. G is then the normalizer of N1, and because the index of the normalizer in GCE is the number of conjugates of N1, it follows that N1 has one more conjugate subgroup in G. Call this subgroup N2, and assume N2 = x^-1 N1 x for an appropriate element x of GCE. Because N_GCE(N2) = N_GCE(x^-1 N1 x) = x^-1 NGCE(N1) x = x^-1 G x = G, it follows that N2 is also a normal subgroup of G. The closure and the intersection of a whole family of conjugated subgroups are always normal. Thus the closure and the intersection of N1 and N2 are normal subgroups of GCE (and are therefore subgroups that appear in the above lattice). Call them N12 and N. Clearly N12 and N are subgroups of G. Now the isomorphism theorem tells us that N12/N1 ~ N2/N. Then |N12/N| = |N12/N1| |N1/N| = |N12/N1| |N2/N| = |N12/N1| |N12/N1|. Thus |N12/N| is a square. But the only factor groups with square sizes are VE/Z, (VE*VC)/(Z*VC), (VE*GC')/(Z*GC') (all of size 2^10). We can intersect the whole situation into VE, so we can without loss of generality assume that N1 and N2 are subgroups of VE. But if N1 and N2 are normal subgroups of G, then they are certainly normal subgroups of GE'. But GE' has only the 4 normal subgroups: GE', VE, Z, and <1>. Thus there cannot be a normal subgroup of G that is not normal in GCE. So the following picture gives the lattice of normal subgroups of G. G | 2 G' / \ / \ / \ / \ / \ / \ / \ / \ / X / / \ / / \ / / \ X / \ / \ / \ / \ / GE' / \ / / X \ / / / \ \ / / GC' \ \ / / \ \ \ / / \ \ \ / / 12!/2 \ \ X / 8!/2 \ \ / \ / \ \ / \ / \ \ / \ / \ X \ / \ / \ \ / VC \ VE \ \ / \ \ / 2^10 3^7 \ \ / \ Z \ / 2 <1> So Jerry had it almost right. But he missed the center Z, and all the closures of pairs of normal subgroups. 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 Mon Jan 2 23:07:26 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA25455; Mon, 2 Jan 95 23:07:26 EST Message-Id: <9501030407.AA25455@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5142; Mon, 02 Jan 95 23:00:17 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 3296; Mon, 2 Jan 1995 23:00:17 -0500 X-Acknowledge-To: Date: Mon, 2 Jan 1995 23:00:01 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: Normal Subgroups of G In-Reply-To: Message of 12/30/94 at 15:17:00 from , Martin.Schoenert@math.rwth-aachen.de On 12/30/94 at 15:17:00 Martin Schoenert said: >Basically the same argument works for GE. But there is one exception. >Namely VE has one normal subgroup of size 2 , generated by the element >(1,1,...,1;). You may not recognize this element, but it is >in fact the superflip, which flips all twelve edges. I shall call this >subgroup Z. >Thus GE has 5 normal subgroups GE, GE', VE, Z, and <1>. I am still absorbing this article, which exceeds my current knowledge of group theory. But at the risk of asking a dumb question, doesn't the center of GE (and of G) in fact consist of more than just the Superflip and the identity? Does it not also include the Pons Asinorum and the composition of the Pons Asinorum and the Superflip? Call the Pons Asinorum P and the Superflip E. I think you are saying Z={I,E}. But isn't the center {I,P,E,PE}, with subgroups {I,P}, {I,E}, {I,PE}, and {I}? These should all be central, and hence also normal, I would think. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From @mail.uunet.ca:mark.longridge@canrem.com Tue Jan 3 02:39:05 1995 Return-Path: <@mail.uunet.ca:mark.longridge@canrem.com> Received: from seraph.uunet.ca (uunet.ca) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA08669; Tue, 3 Jan 95 02:39:05 EST Received: from portnoy.canrem.com ([198.133.42.17]) by mail.uunet.ca with SMTP id <123884-5>; Tue, 3 Jan 1995 01:55:18 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA25721; Tue, 3 Jan 95 01:51:24 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1C6CAC; Tue, 3 Jan 95 01:22:30 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Centres From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.932.5834.0C1C6CAC@canrem.com> Date: Tue, 3 Jan 1995 00:05:00 -0500 Organization: CRS Online (Toronto, Ontario) Jerry Bryan asks: > ... doesn't the center of GE (and of G) in fact consist > of more than just the Superflip and the identity? Does it > not also include the Pons Asinorum and the composition of > the Pons Asinorum and the Superflip? Hmmm, I don't think so... The centre commutes with every process, and the Pons Asinorum just doesn't. E.g. R1 + F2 B2 U2 D2 L2 R2 <> F2 B2 U2 D2 L2 R2 + R1 I think Martin has scoped out all the possible centres in other subgroups. -> Mark <- From mschoene@math.rwth-aachen.de Tue Jan 3 07:02:09 1995 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA12797; Tue, 3 Jan 95 07:02:09 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rP7tL-000MPFC; Tue, 3 Jan 95 12:59 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rP7tK-00025cC; Tue, 3 Jan 95 12:59 WET Message-Id: Date: Tue, 3 Jan 95 12:59 WET From: "Martin Schoenert" To: Cube-Lovers@ai.mit.edu In-Reply-To: "Jerry Bryan"'s message of Mon, 2 Jan 1995 23:00:01 EST <9501030407.AA25455@life.ai.mit.edu> Subject: Re: Re: Normal Subgroups of G Jerry Bryan wrote in his e-mail message of 1995/01/02 I am still absorbing this article, which exceeds my current knowledge of group theory. But at the risk of asking a dumb question, doesn't the center of GE (and of G) in fact consist of more than just the Superflip and the identity? Does it not also include the Pons Asinorum and the composition of the Pons Asinorum and the Superflip? Call the Pons Asinorum P and the Superflip E. I think you are saying Z={I,E}. But isn't the center {I,P,E,PE}, with subgroups {I,P}, {I,E}, {I,PE}, and {I}? These should all be central, and hence also normal, I would think. This is not a dump question. Clearly ``Pons Asinorum'' P looks very regular, and it is not farfetched to think that it is central. But it is not. Only one out of 332640 elements of GE (and of G) centralizes P. That is to say that the index of the centralizer of P in GE has index 332640 in GE. Since all elements of GC commute with all elements of GE, the index of the centralizer of P in G also has index 332640 in G. Z is indeed the center of GE', GE, G, G', and GCE. It is in fact not too difficult to find the centers. Recall that GE consists of the elements ( c_1, c_2, ..., c_12; p ), where c_1 + c_2 + ... c_12 = 0 (mod 2) and p in S_12. Since we can permute the components c_i in any way by conjugation with an appropriate element (0,0,...,0;p), it follows that any central element must have c_1 = c_2 = ... = c_12. Furthermore any central elemement must have a permutation p that is central in S_12. So we see that we have exactely two elements in the center of GE, namely (0,0,...,0;) and (1,1,...,1;). An easy argument shows that this is also the center of GE'. The same argumentation works for GC, but the element (1,1,...,1;) is not in GC, since 1 + 1 + ... + 1 <> 0 (mod 3) (since we have 8 summands). So GC has trivial center. Again an easy argument shows that this is also the center of GC'. The center of the direct product GCE is of course the direct product of the centers of GC and GE. So we see that the center of GCE is again Z. And again an easy argument shows that this is also the center of G. If you have more questions, please do ask. I have tried to make my article selfcontained. I think the only result that I used without proof is that S_8 and S_12 have only one proper normal subgroup. The problem is that in order to keep the article reasonably short, I had to be rather terse at several places. 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 mreid@ptc.com Thu Jan 5 17:01:22 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA23191; Thu, 5 Jan 95 17:01:22 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA00298; Thu, 5 Jan 95 17:00:01 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA04664; Thu, 5 Jan 1995 17:12:18 -0500 Date: Thu, 5 Jan 1995 17:12:18 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501052212.AA04664@ducie.ptc.com> To: cube-lovers%life.ai.mit.edu@ptc.com Subject: kociemba's algorithm for quarter turns Content-Length: 605 for much too long now, i've meant to implement kociemba's algorithm for quarter turns. finally i've gotten around to it, and it's found superflip: B3 L3 U3 L3 F1 U1 D1 L3 B1 U1 F1 R3 L1 F3 B2 U1 D1 F2 B2 R2 U1 D1 26q it's interesting to note that david plummer gave a 28 quarter turn maneuver for superflip on december 10, 1980. as far as i know, this is the first improvement since then. also found: supertwist: B3 L2 U1 D1 R2 B3 D2 F2 D3 R2 F1 B1 L2 D3 B2 U2 24q superfliptwist: U1 B3 U3 L3 F3 U3 B3 R3 D1 F3 D3 B3 U3 F3 L3 U1 F1 U1 D3 B2 U3 22q more patterns to follow ... mike From gej@spamalot.mfg.sgi.com Thu Jan 5 20:58:47 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA05251; Thu, 5 Jan 95 20:58:47 EST Received: from sgigate.sgi.com by ptc.com (5.0/SMI-SVR4-NN) id AA02280; Thu, 5 Jan 95 20:57:14 EST Received: from spamalot.mfg.sgi.com by sgigate.sgi.com via ESMTP (940627.SGI.8.6.9/911001.SGI) id RAA17897; Thu, 5 Jan 1995 17:58:31 -0800 Received: by spamalot.mfg.sgi.com (940816.SGI.8.6.9/930416.SGI) id RAA02633; Thu, 5 Jan 1995 17:58:06 -0800 From: gej@spamalot.mfg.sgi.com (Gene Johannsen) Message-Id: <199501060158.RAA02633@spamalot.mfg.sgi.com> Subject: Re: kociemba's algorithm for quarter turns To: mreid@ptc.com (michael reid) Date: Thu, 5 Jan 1995 17:58:05 -0800 (PST) Cc: cube-lovers%life.ai.mit.edu@ptc.com In-Reply-To: <9501052212.AA04664@ducie.ptc.com> from "michael reid" at Jan 5, 95 05:12:18 pm X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 8bit Content-Length: 223 > > for much too long now, i've meant to implement kociemba's algorithm I'm new to the list, and I've seen Kociemba's Algorithm referred to several times. Where can I find some more information on it? Thanks. gene From @mail.uunet.ca:mark.longridge@canrem.com Sat Jan 7 00:14:01 1995 Return-Path: <@mail.uunet.ca:mark.longridge@canrem.com> Received: from seraph.uunet.ca (uunet.ca) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA03726; Sat, 7 Jan 95 00:14:01 EST Received: from portnoy.canrem.com ([198.133.42.17]) by mail.uunet.ca with SMTP id <124324-5>; Sat, 7 Jan 1995 00:14:52 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA10958; Sat, 7 Jan 95 00:10:54 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1C791B; Fri, 6 Jan 95 23:57:55 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: More cube terms From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.940.5834.0C1C791B@canrem.com> Date: Fri, 6 Jan 1995 23:53:00 -0500 Organization: CRS Online (Toronto, Ontario) Notes on Notation and Terminology for Rubik's Cube -------------------------------------------------- In the "Handbook of Cubik Math": cubicles are in lower case, cubies are in UPPER CASE. If we use the 6 letters to describe the 6 faces and the various pieces and positions, e.g. UR, UF, UL, UB are the 4 edge pieces of the U face and URF, UFL, ULB, UBR are the 4 corner pieces. We agree to list the facelets at a corner in clockwise order. This gives the following edge & corner cubicles: uf, ul, ub, ur, rf, fl, lb, br, df, dl, db, dr urf, ufl, ulb, ubr, dfr, dlf, dbl, drb and the following edge & corner cubies: UF, UL, UB, UR, RF, FL, LB, BR, DF, DL, DB, DR URF, UFL, ULB, UBR, DFR, DLF, DBL, DRB By adhering to these conventions we can establish a standard notation for cube positions. The sequence R2 U3 F1 B3 R2 F3 B1 U3 R2 (9 q+h, 12 q) generates a 3-cycle of edges. The cycle representation of this sequence would be ( UF, UR, UB ) in ( ur, ub, uf). Thus cubie UF resides in cubicle ur cubie UR resides in cubicle ub cubie UB resides in cubicle uf If we assume that the unreferenced cubies are in proper position and orientation we have enough information to completely describe a cube in a way which provides more information on it's cycle structure. If an edge pair is flipped we refer to ( FU, LU ) in ( uf, ul) If a corner triple is twisted clockwise we refer to ( RFU, FLU, LBU ) in ( urf, ufl, ulb ) Here are a couple more examples: The super-flip has a cycle representation of ( FU, LU, BU, RU, FR, LF, BL, RB, FD, LD, BD, RD ) ( uf, ul, ub, ur, rf, fl, lb, br, df, dl, db, dr ) The 6 X order 3 has a cycle representation of (( FR, FU, UR ) ( BR, FD, LU ) (BU, RD, FL ) ( BD, DL, BL)) (( uf, ur, rf ) ( df, ul, br ) (dr, fl, ub ) ( dl, lb, db)) -> Mark <- Email: mark.longridge@canrem.com P.S. I'm not certain if the previously mentioned Rubik Algebra uses something like this, but I am going to add it to my cube program. From @mail.uunet.ca:mark.longridge@canrem.com Sat Jan 7 00:27:55 1995 Return-Path: <@mail.uunet.ca:mark.longridge@canrem.com> Received: from seraph.uunet.ca (uunet.ca) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA04016; Sat, 7 Jan 95 00:27:55 EST Received: from portnoy.canrem.com ([198.133.42.17]) by mail.uunet.ca with SMTP id <124322-2>; Sat, 7 Jan 1995 00:14:48 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA10950; Sat, 7 Jan 95 00:10:52 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1C7919; Fri, 6 Jan 95 23:57:55 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Cube terms From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.938.5834.0C1C7919@canrem.com> Date: Fri, 6 Jan 1995 23:50:00 -0500 Organization: CRS Online (Toronto, Ontario) Martin Schoenert states: > Only one out of 332640 elements of GE (and of G) centralizes P. > That is to say that the index of the centralizer of P in GE has index > 332640 in GE. Since all elements of GC commute with all elements of > GE, the index of the centralizer of P in G also has index 332640 in G. > Z is indeed the center of GE', GE, G, G', and GCE. I get the fact that only the super-flip (or 12-flip) is the centre of G and the centre of GE. Another way to look at it would be the centre of the cube group must effect all the corners & edges in the same way, and only the super-flip fits these conditions when we allow all 6 generators < U, D, F, B, L, R > to be used. In the case of the smaller group < U, R > we can get 6 corners twisted either clockwise or counter-clockwise, thus effecting all the corners and edges the same, due to the fact we can have 6 twists the same and < U, R > only contains 6 corners, and so this is the centre of < U, R >. But I don't understand how only one out of 332,640 elements of GE and G centralizes P. I thought that GE had: (12 ^ 2 / 2 ) * 12! = 980,995,276,800 elements That is to say that the group on the cube of edges only has 980,995,276,800 elements. To be honest I'm not sure what P represents! Jerry refers to P as the Pons Asinorum, but I think the term may have two meanings in the two messages. Z is the centre of G right? I need an ANSI standard math dictionary, but I doubt such a book exists. I'm going to tackle some more cube terminology in my next message. -> Mark <- Email: mark.longridge@canrem.com From @mail.uunet.ca:mark.longridge@canrem.com Sat Jan 7 00:34:57 1995 Return-Path: <@mail.uunet.ca:mark.longridge@canrem.com> Received: from seraph.uunet.ca (uunet.ca) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA04167; Sat, 7 Jan 95 00:34:57 EST Received: from portnoy.canrem.com ([198.133.42.17]) by mail.uunet.ca with SMTP id <124330-4>; Sat, 7 Jan 1995 00:14:48 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA10954; Sat, 7 Jan 95 00:10:53 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1C791A; Fri, 6 Jan 95 23:57:55 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Cube with GAP From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.939.5834.0C1C791A@canrem.com> Date: Fri, 6 Jan 1995 23:51:00 -0500 Organization: CRS Online (Toronto, Ontario) Dan Hoey states: > Well, call me John Henry. Say, do you have gap libraries for other > magic polyhedra? For higher-dimensional magic? Well, I've played with GAP for a while now and at the risk of being incorrect, I'm going to make a few comments :-) As I understand it, the format Martin uses in GAP is to represent the 3x3x3 cube by assigning each individual facelet an unique number like so (by the way, the following part is all from the GAP documentation). ---------------------------------------------------------------------- +--------------+ | 1 2 3 | | 4 top 5 | | 6 7 8 | +--------------+--------------+--------------+--------------+ | 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 | | 12 left 13 | 20 front 21 | 28 right 29 | 36 rear 37 | | 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 | +--------------+--------------+--------------+--------------+ | 41 42 43 | | 44 bottom 45 | | 46 47 48 | +--------------+ then the group is generated by the following generators, corresponding to the six faces of the cube (the two semicolons tell GAP not to print the result, which is identical to the input here). gap> cube := Group( > ( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19), > ( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35), > (17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11), > (25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24), > (33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27), > (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40) > );; ---------------------------------------------------------------------- You can't use T for facelet 1, and in general you can only use numbers as facelet identifiers, no alphabetics. Given the following conventions a magic dodecahedron should be no problem, or say a picture Rubik's Revenge ... I don't know how a normal 4x4x4 could be represented though. -> Mark <- Email: mark.longridge@canrem.com From @mail.uunet.ca:mark.longridge@canrem.com Sat Jan 7 03:15:53 1995 Return-Path: <@mail.uunet.ca:mark.longridge@canrem.com> Received: from seraph.uunet.ca (uunet.ca) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA06404; Sat, 7 Jan 95 03:15:53 EST Received: from portnoy.canrem.com ([198.133.42.17]) by mail.uunet.ca with SMTP id <124280-4>; Sat, 7 Jan 1995 03:16:50 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA18252; Sat, 7 Jan 95 03:12:54 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1C7961; Sat, 7 Jan 95 02:39:25 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Cube Twist Correction From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.941.5834.0C1C7961@canrem.com> Date: Fri, 6 Jan 1995 23:59:00 -0500 Organization: CRS Online (Toronto, Ontario) > If a corner triple is twisted clockwise we refer to > ( RFU, FLU, LBU ) in ( urf, ufl, ulb ) Okay..... this would actually be an anti-clockwise tri-twist. -> Mark <- From mschoene@math.rwth-aachen.de Sat Jan 7 10:55:20 1995 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA16566; Sat, 7 Jan 95 10:55:20 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rQdRF-000MPIC; Sat, 7 Jan 95 16:52 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rQdRE-00025cC; Sat, 7 Jan 95 16:52 WET Message-Id: Date: Sat, 7 Jan 95 16:52 WET From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu In-Reply-To: Mark Longridge's message of Fri, 6 Jan 1995 23:50:00 -0500 <60.938.5834.0C1C7919@canrem.com> Subject: Re: Cube terms I wrote in my e-mail of 1995/01/03 Only one out of 332640 elements of GE (and of G) centralizes P. That is to say that the index of the centralizer of P in GE has index 332640 in GE. Since all elements of GC commute with all elements of GE, the index of the centralizer of P in G also has index 332640 in G. Z is indeed the center of GE', GE, G, G', and GCE. Mark Longridge answered in his e-mail of 1995/01/06 I get the fact that only the super-flip (or 12-flip) is the centre of G and the centre of GE. Another way to look at it would be the centre of the cube group must effect all the corners & edges in the same way, and only the super-flip fits these conditions when we allow all 6 generators < U, D, F, B, L, R > to be used. This sounds very plausible. But I must admit that I find it notoriously difficult to turn such plausible arguments into proper proofs. If you try, you may in fact end up with something similar to my proof. Because the crucial part in my proof is that a central element must have all components in the wreath product equal, because one has the full symmetric group S_12 acting on the 12 components. Mark continued In the case of the smaller group < U, R > we can get 6 corners twisted either clockwise or counter-clockwise, thus effecting all the corners and edges the same, due to the fact we can have 6 twists the same and < U, R > only contains 6 corners, and so this is the centre of < U, R >. This is the ``odd'' element I referred to in my message on shift invariant processes. Mark continued But I don't understand how only one out of 332,640 elements of GE and G centralizes P. I thought that GE had: (12 ^ 2 / 2 ) * 12! = 980,995,276,800 elements That is to say that the group on the cube of edges only has 980,995,276,800 elements. To be honest I'm not sure what P represents! Jerry refers to P as the Pons Asinorum, but I think the term may have two meanings in the two messages. Sorry, that is just me wrestling with English. What I meant to say was ``... only one out of *every* 332640 elements of GE ...''. That is, of the total 980995276800 elements in GE only 980995276800/332640 = 2949120 elements centralize P. And I used the definition of P from your e-mail of 1995/01/03, i.e., P = (F2 B2) (U2 D2) (L2 R2) = (F2 B2) (L2 R2) (U2 D2) = ... (one gets the same element independent of the order of the three pairs). Mark continued Z is the centre of G right? I need an ANSI standard math dictionary, but I doubt such a book exists. I'm going to tackle some more cube terminology in my next message. Z in this case refers to the subgroup generated by the superflip. I wrote in my e-mail of 1994/12/30 Namely VE has one normal subgroup of size 2 , generated by the element (1,1,...,1;). You may not recognize this element, but it is in fact the superflip, which flips all twelve edges. I shall call this subgroup Z. I would have preferred to call it C, but C was already taken for the group of rotations of the entire cube. Thus I took Z instead, because ``Zentrum'' is the german word for center. It is not uncommon to use Z to denote the center of a group G, e.g., Huppert uses Z(G) for the center in his ``Theory of Groups''. 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 Sat Jan 7 11:08:45 1995 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA16753; Sat, 7 Jan 95 11:08:45 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rQdeH-000MPIC; Sat, 7 Jan 95 17:05 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rQdeG-00025cC; Sat, 7 Jan 95 17:05 WET Message-Id: Date: Sat, 7 Jan 95 17:05 WET From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu Cc: gej@spamalot.mfg.sgi.com In-Reply-To: Gene Johannsen's message of Thu, 5 Jan 1995 17:58:05 -0800 (PST) <199501060158.RAA02633@spamalot.mfg.sgi.com> Subject: Re: Re: kociemba's algorithm for quarter turns Gene Johannsen wrote in his e-mail message of 1995/01/05 I'm new to the list, and I've seen Kociemba's Algorithm referred to several times. Where can I find some more information on it? Great timing. This allows me to tell you all about the newest feature of the Cube-Lovers WWW pages. You can now search the old articles for keywords (if you have a Browser that supports forms, e.g. 'Mosaic' or 'Netscape'). Check out http://www.math.rwth-aachen.de:8000/~mschoene/Cube-Lovers/Index_for_Keyword.html 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 Sat Jan 7 11:09:27 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA16758; Sat, 7 Jan 95 11:09:27 EST Message-Id: <9501071609.AA16758@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 3760; Sat, 07 Jan 95 10:15:53 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 2792; Sat, 7 Jan 1995 10:15:53 -0500 X-Acknowledge-To: Date: Sat, 7 Jan 1995 10:15:52 EST From: "Jerry Bryan" To: Subject: Re: Cube with GAP In-Reply-To: Message of 01/06/95 at 23:51:00 from mark.longridge@canrem.com On 01/06/95 at 23:51:00 mark.longridge@canrem.com said: > As I understand it, the format Martin uses in GAP is to represent >the 3x3x3 cube by assigning each individual facelet an unique >number like so (by the way, the following part is all from the >GAP documentation). >---------------------------------------------------------------------- > +--------------+ > | 1 2 3 | > | 4 top 5 | > | 6 7 8 | > +--------------+--------------+--------------+--------------+ > | 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 | > | 12 left 13 | 20 front 21 | 28 right 29 | 36 rear 37 | > | 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 | > +--------------+--------------+--------------+--------------+ > | 41 42 43 | > | 44 bottom 45 | > | 46 47 48 | > +--------------+ Note that this model does not include the face centers. That is, it is G[C,E] rather than G[C,E,F]. 56 numbers would be required to include the face centers. The distinction between 48 facelets and 56 facelets bears on the nitpicky question of whether the set C of rotations is a subgroup of G or not. What I don't see is how to model the Supergroup in GAP. It looks like you would have to label each Face center with four numbers so you could see the rotations of the Face centers, but that seems like overkill. I call this kind of model a facelet model rather than a cubie model, and the twists and flips are implicit in a facelet model. I would think that the twists and flips would have to be made explicit in a cubie model. Dan Hoey reported to me once that he had an error wherein his corners turned themselves inside out. I can't totally picture how that happened, but it was related to the fact that he was using a cubie model with a little multiplication table for the twists. I have always used a facelet model, except that I number the corners from 1 to 24 and the edges from 1 to 24 for historical reasons. That is, I started with corners only or edges only, and have only lately put the two together. It really does not create any problems for me to use the same numbers for both edges and corners because the edges and corners are stored disjointly, as are the edge and corner permutations for quarter and half turns, and as are the edge and corner permutations for rotations and reflections. When I write the model out to disk, I only write out 8 corner facelets and 12 edge facelets. For example, I only write out the front and back corner facelets. This saves space and converts the model from a facelet model to a cubie model, with the twists implicitly encoded rather than being explicitly encoded via multiplication tables. It also automatically establishes a frame of reference by which a proof of conservation of twist and flip can be accomplished. > ... I don't know how a normal 4x4x4 could >be represented though. I fail to see the problem. Just number the facelets. The only problem would then lie in deciding what the generators are -- i.e., which kind of slice moves do you accept. You would also have to decide whether to model the invisible 2x2x2 inside, but again if you did, just number the invisible facelets and include their movements with your generators. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 mreid@ptc.com Sat Jan 7 16:43:14 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA29291; Sat, 7 Jan 95 16:43:14 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA09335; Sat, 7 Jan 95 16:41:53 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA06870; Sat, 7 Jan 1995 16:54:18 -0500 Date: Sat, 7 Jan 1995 16:54:18 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501072154.AA06870@ducie.ptc.com> To: cube-lovers@life.ai.mit.edu Subject: Re: kociemba's algorithm for quarter turns Content-Length: 652 gene writes: > I'm new to the list, and I've seen Kociemba's Algorithm > referred to several times. Where can I find some more > information on it? there are several places you might try. dik winter first wrote about this new searching algorithm on may 3, 1992, and there was a bit of discussion after that. so you can look through the archives (cube-mail-8). if you are a member of nkc (nederlands kubus club) you might look through the newsletter cff (cubism for fun) issue #28 where herbert kociemba first writes about his algorithm. also, martin gave some info about the cube-lovers archives being available on the world-wide-web. mike From mreid@ptc.com Sat Jan 7 19:32:56 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA06222; Sat, 7 Jan 95 19:32:56 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA09534; Sat, 7 Jan 95 19:31:01 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA07043; Sat, 7 Jan 1995 19:43:27 -0500 Date: Sat, 7 Jan 1995 19:43:27 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501080043.AA07043@ducie.ptc.com> To: cube-lovers@ai.mit.edu Subject: two stage filtration Content-Length: 4359 kociemba's algorithm uses the filtration G = of order 43252003274489856000 H = of order 19508428800 1 = <> of order 1 i've run an exhaustive search on the coset space G / H. the number of cosets at each distance is: distance quarter turns face turns 0 1 1 1 4 4 2 34 50 3 312 592 4 2772 7156 5 24996 87236 6 225949 1043817 7 2017078 12070278 8 17554890 124946368 9 139132730 821605960 10 758147361 1199128738 11 1182378518 58202444 12 117594403 476 13 14072 the computation for face turns was already done by dik winter (see his message of may 28, 1992), so in particular, this confirms his calculation. the cosets G / H are described by triples (c, e, l), where c = corner orientation e = edge orientation l = location of middle layer edges (FR, FL, BR, BL) there are 3^7 = 2187 corner configurations, 2^11 = 2048 edge configurations, and / 12 \ \ 4 / = 495 location configurations, to give a total of 2187 * 2048 * 495 = 2217093120 configurations. to reduce this number somewhat, we can utilize symmetry. there are 16 symmetries of the cube that preserve the U-D axis, and therefore preserve the subgroup H. up to these symmetries, the number of distinct corner configurations is 168, so we need only consider a mere 168 * 2048 * 495 = 170311680 configurations. (so far, this is the same approach that dik used for his calculation.) each configuration is stored with 2 bits of memory and thus the whole space consumes about 42 megabytes. each configuration is assigned one of 4 values: distance is currently unknown distance = current search depth distance = current search depth - 1 distance < current search depth - 1 from here, i just used a simple breadth first search. unfortunately, something unpleasant happened along the way ... at some point, i realized that the symmetries do not act on the edge configurations. to define edge flip, one must choose one facelet from each of the 4 middle layer edges to correspond to the U or D facelet of the other 8 edges. (i chose the F and B facelets, but this is completely arbitrary.) but now we've lost some symmetry; these 12 facelets are not preserved under the 16 symmetries, in particular, the rotation C_U does not preserve them. therefore, we need lookup tables for the action of the symmetries on edge x location space. this gives 16 symmetries * 2048 edge configurations * 495 location configurations * 4 bytes per integer = 64 megabytes of lookup tables. ouch! i was too far along at this point to start all over, and i had the memory available, so i just continued with this approach. however, in hindsight, i'd probably use one of the following ideas if i had to start over: i) only use the 8 symmetries that preserve my choice of 12 edge facelets. ii) combine the two coordinates edge and location into a single coordinate and divide this coordinate by the 16 symmetries. run times were improved significantly by using a simple trick that i hadn't used in earlier programs. during the first few depth levels, i use "forward searching", i.e. i examine the neighbors of each configuration found at the previous depth. however, after at least half the search space has been found, i switch to "backward searching", i.e. examine the configurations (and their neighbors) that haven't yet been found. (have others been using this same idea when running similar search programs?) closer analysis of this technique suggests that the switch from forward to backward searching should occur even before half the space has been found. i didn't do this here since the run times were quite satisfactory: 40 minutes for quarter turns, 47 minutes for face turns. this was done on a DEC 3000 alpha 700, apparently a very fast machine. mike From mreid@ptc.com Sat Jan 7 19:53:08 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA06520; Sat, 7 Jan 95 19:53:08 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA09551; Sat, 7 Jan 95 19:51:46 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA07071; Sat, 7 Jan 1995 20:04:09 -0500 Date: Sat, 7 Jan 1995 20:04:09 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501080104.AA07071@ducie.ptc.com> To: cube-lovers@ai.mit.edu Subject: two stage filtration Content-Length: 3087 i've also run an exhaustive search on the subgroup H = . here are the number of positions at each distance. distance quarter turns face turns 0 1 1 1 4 10 2 10 67 3 36 456 4 123 3079 5 368 19948 6 1192 123074 7 3792 736850 8 11263 4185118 9 34352 22630733 10 102638 116767872 11 287320 552538680 12 810144 2176344160 13 2261028 5627785188 14 5941838 7172925794 15 16291708 3608731814 16 41973415 224058996 17 107458884 1575608 18 269542476 1352 19 628442876 20 1367654200 21 2613422312 22 3997726648 23 4444701268 24 3661653732 25 1906936668 26 407132392 27 34358944 28 1664168 29 14840 30 160 a position at distance 18 face turns was exhibited by hans kloosterman on may 30 1992. (he also found three others that differ only in the middle layer edges.) it was then observed by dik winter (also on may 30 1992) that kociemba's algorithm took exceptionally long for this position. however, this does not appear to be the case for most of the antipodes. (i will give the antipodes for each metric in separate messages.) the 4 positions found by kloosterman are also antipodes in the quarter turn metric, and, up to symmetry, are the only positions which are antipodal in both metrics. hmmm... elements of H are described by triples (c, e, m), where c = corner permutation, e = U D edge permutation, m = middle layer edge permutation, and the total parity is even. there are 8! = 40320 corner configurations, 8! = 40320 U D edge configurations and 4! = 24 middle layer edge configurations, for a total of 40320 * 40320 * 24 / 2 = 19508428800 positions. if we divide by symmetry along the corner coordinate, we get 2768 corner configurations (of course we get the same number if we divide by symmetry along the U D edge coordinate), so we can reduce to 1339269120 positions. at 2 bits per configuration, this requires 327 megabytes, which is too large. however, if we also divide out by inversion, we can reduce the number of corner configurations to 1672, the total number of positions to 808980480, and the memory required to 200 megabytes. this is still a lot, but is within reach. the calculations were done on the same machine: DEC 3000 alpha 700, configured with 256 Mb RAM. run times were much more modest: 10 hours for quarter turns, 7.5 hours for face turns. mike From mreid@ptc.com Sat Jan 7 20:14:05 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07520; Sat, 7 Jan 95 20:14:05 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA09581; Sat, 7 Jan 95 20:12:09 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA07129; Sat, 7 Jan 1995 20:24:35 -0500 Date: Sat, 7 Jan 1995 20:24:35 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501080124.AA07129@ducie.ptc.com> To: cube-lovers@ai.mit.edu Subject: new upper bounds Content-Length: 2083 from these calculations, we get new upper bounds on the length of "god's algorithm": 42 quarter turns, 29 face turns. (no, i didn't add incorrectly.) the previous upper bounds were 56 quarter turns, 37 face turns. the best known lower bounds are 21 quarter turns, 18 face turns. here's how to get these upper bounds. note that the last twist in stage 1 is always a quarter turn of either F, R, B or L, and the direction doesn't matter. thus by choosing the direction of this quarter turn properly, we hope to be able to avoid the positions at maximal distance in stage 2. the program verified that no two positions at distance 30 quarter turns differ by F2, R2, B2 or L2, so we may avoid these bad cases. i expected to be able to avoid the positions at distance 29 quarter turns as well, but alas, things do not always go as planned. the following two positions at distance 29 quarter turns differ by B2: position 1: D1 R2 D3 L2 D3 R2 U3 D3 R2 U1 B2 D3 L2 D3 R2 D3 F2 D1 B2 D1 29q position 2: R2 U3 L2 U3 D3 L2 D1 L2 D1 R2 F2 D1 F2 D3 L2 B2 D1 B2 D1 29q there are probably many other examples. similarly, the positions at distance 18 face turns were checked and no two of these differ by F2, R2, B2 or L2, so these positions may be avoided. this gives upper bounds of 13 + 29 = 42 quarter turns and 12 + 17 = 29 face turns. i expect to be able to reduce the 42 quarter turns slightly. for example, to improve it to 41 quarter turns, i just need to check that any position in stage 2 can be solved in at most 28 quarter turns, where we now allow all turns. of course, this only requires testing the positions at distance 29 and 30. i expect this to be straightforward, but i don't know how much improvement i can get with this approach. the same approach doesn't seem plausible for face turns. in order to get just 1 face turn improvement, all positions at distance 17 face turns would need to be solvable in at most 16 face turns. this doesn't seem promising. probably most of these require 17 face turns even with all turns available. mike From mreid@ptc.com Sat Jan 7 20:33:56 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA08623; Sat, 7 Jan 95 20:33:56 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA09617; Sat, 7 Jan 95 20:32:02 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA07165; Sat, 7 Jan 1995 20:44:27 -0500 Date: Sat, 7 Jan 1995 20:44:27 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501080144.AA07165@ducie.ptc.com> To: cube-lovers@ai.mit.edu Subject: antipodes in quarter turn metric Content-Length: 2017 these are the antipodes of H = in the quarter turn metric, divided by the 16 symmetries. btw, these symmetries are generated by C_U, C_F2 and reflection through the U-D plane. 1) D3 B2 D1 F2 R2 B2 R2 U1 R2 U3 F2 D3 R2 D1 R2 U3 L2 B2 U3 30q 2) D3 B2 D3 L2 F2 B2 D1 L2 U3 L2 F2 D1 F2 U3 B2 U1 L2 F2 U3 30q 3) D3 B2 L2 D3 B2 R2 L2 B2 R2 L2 D3 B2 R2 U3 D3 F2 L2 D1 30q 4) D3 B2 L2 D3 B2 R2 L2 B2 R2 L2 D3 B2 R2 U2 R2 F2 U1 30q 5) D3 B2 D3 B2 L2 B2 U1 F2 U1 R2 L2 U1 F2 L2 D3 F2 L2 F2 30q 6) D3 B2 D3 B2 L2 B2 D1 R2 D1 R2 L2 D1 L2 B2 U3 F2 L2 F2 30q 7) D3 B2 L2 D1 F2 B2 L2 F2 B2 L2 D1 F2 L2 U1 D1 B2 R2 D1 30q 8) D3 B2 D3 B2 U1 F2 U3 L2 D3 F2 D1 R2 B2 R2 L2 D1 B2 R2 U1 30q 9) D3 B2 D3 F2 L2 U3 R2 D1 B2 R2 D3 R2 U1 F2 L2 D1 B2 R2 U1 30q 10) D3 B2 L2 D3 B2 R2 L2 B2 R2 L2 D3 B2 R2 U3 D3 F2 L2 U3 30q 11) D3 B2 L2 D1 F2 B2 L2 F2 B2 L2 D1 B2 R2 U3 D3 F2 L2 U3 30q 12) D3 B2 L2 D1 F2 B2 L2 F2 B2 L2 D1 F2 L2 U1 D1 B2 R2 U3 30q 13) D3 B2 D3 F2 L2 D3 F2 U1 F2 L2 D3 L2 U1 B2 R2 U1 L2 B2 U1 30q 14) D3 B2 L2 D1 F2 B2 L2 F2 B2 L2 D1 B2 R2 U1 D1 B2 R2 U1 30q 15) D3 B2 L2 D3 B2 R2 L2 B2 R2 L2 D3 B2 R2 U2 R2 F2 D1 30q 16) inverse of 15 17) D3 B2 L2 D3 B2 R2 L2 B2 R2 L2 D3 B2 R2 U1 D1 B2 R2 U1 30q 18) D3 B2 D3 B2 L2 B2 U1 F2 U1 R2 L2 U1 F2 L2 U3 R2 F2 R2 30q 19) D3 B2 L2 D3 B2 R2 L2 B2 R2 L2 D3 F2 L2 U3 D3 F2 L2 U1 30q 20) D3 B2 D3 B2 L2 U1 L2 U3 F2 L2 D1 R2 U3 B2 U1 B2 R2 D3 F2 30q 21) inverse of 20 22) D3 B2 D3 B2 U1 R2 L2 F2 U3 B2 R2 D1 F2 L2 U1 B2 U3 F2 D3 30q 23) D3 B2 D3 B2 L2 U3 L2 U1 F2 D1 F2 D3 L2 F2 B2 D1 F2 R2 D3 30q 24) D3 B2 D3 L2 D1 L2 U3 B2 U1 B2 L2 U1 B2 R2 L2 D3 F2 U3 R2 30q 25) D3 B2 D3 B2 L2 D3 B2 U1 L2 D1 L2 D3 B2 R2 L2 D1 L2 F2 D3 30q the position identified by hans kloosterman is number 14. there are also a few closely related positions. mike From mreid@ptc.com Sat Jan 7 21:03:01 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA09743; Sat, 7 Jan 95 21:03:01 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA09649; Sat, 7 Jan 95 21:01:07 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA07228; Sat, 7 Jan 1995 21:13:32 -0500 Date: Sat, 7 Jan 1995 21:13:32 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501080213.AA07228@ducie.ptc.com> To: cube-lovers@ai.mit.edu Subject: antipodes in face turn metric Content-Length: 8220 these are the antipodes of H = in the face turn metric, divided by the 16 symmetries. 1) D3 B2 D3 B2 D2 L2 D1 L2 B2 D2 F2 D1 R2 F2 U1 R2 F2 R2 18f 2) D3 B2 D3 B2 D2 L2 D1 L2 B2 D2 F2 U1 F2 L2 D1 R2 F2 R2 18f 3) D3 B2 D3 F2 D2 L2 U3 L2 F2 B2 U2 F2 U1 B2 U1 L2 B2 R2 18f 4) D3 B2 D3 L2 D2 R2 L2 F2 D3 B2 D2 R2 D3 F2 U1 B2 L2 F2 18f 5) D3 B2 D3 B2 U2 R2 D1 R2 F2 U2 F2 U1 F2 L2 D1 R2 F2 R2 18f 6) inverse of 5 7) D3 B2 D3 L2 U2 R2 L2 B2 U3 R2 D2 F2 D3 L2 D1 B2 L2 F2 18f 8) D3 B2 D3 L2 U1 B2 U3 B2 R2 D3 B2 R2 U3 F2 D1 R2 B2 R2 18f 9) inverse of 8 10) D3 B2 D3 L2 D1 L2 D3 B2 R2 U3 L2 B2 D3 F2 D1 R2 B2 R2 18f 11) D3 B2 D3 L2 D1 L2 U3 L2 B2 D3 L2 B2 D3 F2 D1 R2 B2 R2 18f 12) inverse of 11 13) D3 B2 D3 L2 D1 L2 U3 L2 B2 D3 L2 B2 U3 R2 U1 R2 B2 R2 18f 14) D3 B2 L2 D2 L2 D3 B2 L2 U1 F2 U2 R2 U3 F2 B2 R2 D1 B2 18f 15) inverse of 14 16) D3 B2 U2 R2 D1 L2 F2 R2 F2 D1 R2 D2 R2 B2 U1 B2 U1 B2 18f 17) inverse of 16 18) D3 B2 L2 D2 L2 D3 B2 L2 D3 F2 D2 R2 U1 R2 L2 B2 U1 B2 18f 19) D3 B2 U2 R2 D1 L2 F2 R2 F2 U1 F2 D2 F2 R2 D1 B2 U1 B2 18f 20) D3 B2 D3 R2 F2 B2 U1 R2 L2 B2 D3 R2 D1 R2 F2 U1 L2 D3 18f 21) inverse of 20 22) D3 B2 D3 F2 B2 R2 U1 R2 U3 L2 F2 R2 F2 D3 B2 U1 R2 D3 18f 23) D3 B2 D3 F2 B2 R2 U1 R2 D3 B2 L2 F2 L2 U3 B2 U1 R2 D3 18f 24) inverse of 23 25) D3 B2 D3 F2 L2 U3 L2 D1 F2 U3 L2 D1 L2 B2 D1 F2 L2 B2 18f 26) D3 B2 D3 F2 B2 R2 D1 B2 U3 F2 R2 B2 R2 U3 F2 D1 F2 U3 18f 27) inverse of 26 28) D3 B2 D2 L2 D1 L2 D1 L2 B2 D2 F2 D1 R2 U3 F2 L2 F2 B2 18f 29) inverse of 28 30) D3 B2 D2 L2 D1 L2 U1 B2 R2 U2 R2 U1 R2 U3 F2 L2 F2 B2 18f 31) D3 B2 D3 F2 B2 R2 U1 R2 D3 B2 L2 F2 L2 D3 R2 D1 R2 D3 18f 32) D3 B2 L2 U3 F2 R2 B2 R2 D1 B2 U3 F2 U1 F2 D1 F2 D3 B2 18f 33) D3 F2 B2 L2 D1 B2 U1 R2 D3 L2 D1 L2 D1 R2 F2 U1 F2 R2 18f 34) D3 B2 R2 D3 F2 L2 B2 L2 D1 L2 D3 R2 U1 F2 D1 R2 U3 L2 18f 35) D3 B2 L2 D3 L2 F2 R2 F2 D1 R2 D3 B2 D1 L2 D1 L2 U3 B2 18f 36) D3 B2 L2 D3 L2 F2 R2 F2 D1 R2 U3 L2 D1 F2 D1 F2 D3 B2 18f 37) inverse of 36 38) D3 B2 R2 U3 R2 F2 L2 F2 U1 L2 D3 R2 D1 R2 U1 R2 U3 L2 18f 39) D3 B2 L2 D3 R2 D2 B2 D3 R2 B2 U2 F2 D1 B2 D3 R2 B2 R2 18f 40) D3 B2 L2 D3 R2 U2 F2 U3 F2 R2 D2 R2 U1 B2 D3 R2 B2 R2 18f 41) D3 B2 L2 D1 B2 D2 R2 D1 R2 B2 U2 F2 U1 R2 U3 R2 B2 R2 18f 42) D3 B2 L2 D1 B2 D2 R2 U1 F2 R2 U2 L2 D1 R2 U3 R2 B2 R2 18f 43) D3 B2 L2 D3 R2 D2 B2 U3 B2 L2 D2 L2 D1 R2 U3 R2 B2 R2 18f 44) inverse of 43 45) D3 B2 L2 D3 R2 D2 B2 D3 R2 B2 U2 F2 U1 R2 U3 R2 B2 R2 18f 46) D3 B2 D3 B2 L2 D2 F2 L2 F2 R2 D2 F2 R2 D1 F2 B2 R2 U3 18f 47) D3 B2 D3 B2 L2 U2 L2 F2 D2 F2 R2 U1 B2 R2 L2 B2 R2 U3 18f 48) D3 B2 D3 B2 L2 D2 L2 F2 D2 B2 L2 U1 B2 R2 L2 B2 R2 U3 18f 49) D3 B2 D3 B2 L2 U2 B2 L2 F2 L2 D2 B2 L2 D1 F2 B2 R2 U3 18f 50) D3 B2 U1 B2 U3 L2 U1 L2 U3 B2 R2 D3 F2 D1 L2 B2 L2 F2 18f 51) D3 B2 D1 B2 D3 R2 U1 F2 D3 R2 B2 D3 B2 D1 F2 R2 F2 L2 18f 52) inverse of 51 53) D3 B2 D1 B2 D3 R2 D1 R2 D3 B2 L2 D3 L2 U1 F2 R2 F2 L2 18f 54) inverse of 53 55) D3 B2 D1 B2 D3 R2 U1 F2 U3 B2 L2 D3 L2 U1 F2 R2 F2 L2 18f 56) D3 B2 D1 F2 L2 D3 R2 F2 D3 L2 D1 B2 R2 U1 F2 U3 B2 R2 18f 57) D3 B2 D1 F2 L2 D3 R2 F2 U3 F2 U1 B2 R2 D1 R2 D3 B2 R2 18f 58) D3 B2 D1 B2 U3 B2 U1 R2 D3 B2 L2 D3 L2 U1 F2 R2 F2 L2 18f 59) D3 B2 U1 F2 R2 U3 L2 F2 D3 F2 U1 R2 B2 U1 B2 U3 R2 B2 18f 60) inverse of 59 61) D3 B2 L2 D3 R2 U1 F2 R2 L2 D3 L2 F2 U3 L2 U3 L2 D1 R2 18f 62) D3 B2 D2 L2 D1 R2 U3 F2 L2 U2 L2 D3 R2 D1 F2 R2 F2 L2 18f 63) inverse of 62 64) D3 B2 D2 L2 U1 B2 R2 B2 L2 D3 R2 U2 L2 B2 D3 F2 U3 R2 18f 65) D3 B2 D2 L2 D1 L2 B2 L2 F2 D3 B2 U2 F2 L2 D3 R2 D3 R2 18f 66) D3 B2 D2 L2 D1 L2 B2 L2 F2 U3 L2 D2 L2 B2 D3 F2 U3 R2 18f 67) D3 B2 D2 L2 D1 R2 D3 L2 B2 D2 F2 D3 B2 U1 F2 R2 F2 L2 18f 68) D3 B2 D2 L2 D1 L2 B2 L2 F2 D3 B2 D2 B2 R2 U3 F2 U3 R2 18f 69) D3 B2 U2 R2 U1 B2 U3 R2 F2 U2 F2 D3 B2 U1 F2 R2 F2 L2 18f 70) D3 B2 D1 B2 D3 L2 F2 U1 B2 D3 F2 B2 L2 D1 B2 L2 D3 L2 18f 71) inverse of 70 72) D3 B2 U1 R2 D3 B2 L2 U1 R2 D3 R2 L2 B2 D1 R2 B2 U3 L2 18f 73) D3 B2 D2 R2 U1 L2 F2 R2 F2 D3 F2 D2 B2 L2 D3 R2 D3 R2 18f 74) D3 B2 D2 R2 U1 L2 F2 R2 F2 U3 R2 U2 R2 B2 D3 F2 U3 R2 18f 75) D3 B2 D2 R2 D1 F2 R2 B2 R2 D3 R2 U2 R2 B2 D3 F2 U3 R2 18f 76) D3 B2 D2 R2 U1 L2 F2 R2 F2 D3 F2 U2 F2 R2 U3 F2 U3 R2 18f 77) D3 B2 D2 R2 D1 F2 R2 B2 R2 D3 R2 U2 R2 B2 U3 R2 D3 R2 18f 78) D3 B2 D3 F2 D2 L2 D3 F2 U2 L2 F2 B2 D3 R2 D3 L2 F2 R2 18f 79) inverse of 78 80) D3 B2 D3 F2 D2 L2 D3 F2 D2 R2 F2 B2 U3 F2 U3 L2 F2 R2 18f 81) D3 B2 D3 F2 D2 L2 D1 R2 F2 B2 U2 F2 U1 F2 U3 L2 F2 R2 18f 82) inverse of 81 83) D3 B2 D1 B2 D1 B2 U2 R2 D3 L2 F2 L2 B2 D1 B2 U2 F2 L2 18f 84) D3 B2 D3 F2 U2 R2 D3 B2 U2 R2 F2 B2 U3 F2 U3 L2 F2 R2 18f 85) inverse of 84 86) D3 B2 D3 F2 U2 R2 U1 B2 R2 L2 U2 R2 U1 R2 D3 L2 F2 R2 18f 87) D3 B2 D1 B2 D1 B2 D2 L2 D3 R2 B2 R2 F2 D1 F2 D2 F2 L2 18f 88) D3 B2 D3 F2 D2 L2 U1 F2 R2 L2 U2 L2 D1 F2 U3 L2 F2 R2 18f 89) D3 B2 D3 F2 D2 L2 U1 F2 R2 L2 D2 R2 U1 R2 D3 L2 F2 R2 18f 90) D3 B2 D3 R2 D2 F2 D3 L2 D2 B2 U1 F2 R2 L2 U3 L2 B2 R2 18f 91) inverse of 90 92) D3 B2 D3 R2 D2 F2 U3 F2 D2 L2 U1 R2 F2 B2 D3 L2 B2 R2 18f 93) D3 B2 D3 R2 D2 B2 R2 L2 U1 L2 U2 B2 U3 L2 D3 R2 B2 L2 18f 94) inverse of 93 95) D3 B2 D3 R2 D2 B2 R2 L2 D3 R2 U2 B2 D1 L2 D3 R2 B2 L2 18f 96) D3 B2 D3 R2 D2 B2 R2 L2 U3 B2 U2 L2 U1 L2 D3 R2 B2 L2 18f 97) inverse of 96 98) D3 B2 D3 R2 D2 B2 R2 L2 U1 L2 U2 B2 D3 B2 U3 R2 B2 L2 18f 99) D3 B2 D3 R2 D2 F2 U3 F2 U2 R2 D1 F2 R2 L2 U3 L2 B2 R2 18f 100) D3 B2 D3 R2 D2 F2 D1 B2 D2 L2 D3 R2 F2 B2 D3 L2 B2 R2 18f 101) D3 B2 D3 R2 D2 B2 R2 L2 D3 R2 U2 B2 U1 B2 U3 R2 B2 L2 18f 102) D3 B2 D2 L2 D1 B2 R2 F2 R2 U1 F2 D2 B2 R2 D1 R2 U1 F2 18f 103) D3 B2 D3 F2 D1 R2 U3 B2 L2 U3 B2 L2 U3 R2 D1 R2 F2 R2 18f 104) D3 B2 U2 R2 D1 F2 L2 B2 L2 D1 L2 U2 L2 B2 U1 R2 U1 F2 18f 105) D3 B2 U3 R2 D1 B2 D3 B2 L2 U3 B2 L2 U3 R2 D1 R2 F2 R2 18f 106) D3 B2 D3 F2 U1 F2 D3 F2 R2 D3 L2 F2 D3 R2 D1 R2 F2 R2 18f 107) inverse of 106 108) D3 B2 U2 R2 U1 L2 B2 R2 B2 U1 R2 D2 L2 B2 U1 R2 U1 F2 18f 109) D3 B2 U3 R2 D1 B2 U3 L2 F2 U3 L2 F2 D3 R2 D1 R2 F2 R2 18f 110) D3 B2 D3 B2 R2 L2 D1 F2 B2 R2 U3 B2 U1 B2 L2 D1 F2 D3 18f 111) D3 B2 D2 L2 D1 F2 U1 F2 R2 D2 R2 D1 R2 D3 B2 L2 F2 B2 18f 112) D3 B2 U3 L2 F2 B2 U1 F2 B2 R2 D3 R2 D1 B2 L2 U1 L2 U3 18f 113) D3 B2 D3 B2 U1 L2 F2 L2 B2 D1 R2 U3 R2 F2 B2 D1 B2 D3 18f 114) D3 B2 D3 B2 D1 F2 R2 F2 L2 D1 B2 D3 R2 F2 B2 U1 R2 U3 18f 115) inverse of 114 116) D3 B2 D3 B2 D1 F2 R2 F2 L2 D1 B2 D3 R2 F2 B2 D1 B2 D3 18f 117) D3 B2 D2 L2 U1 L2 U1 L2 F2 U2 B2 U1 R2 D3 B2 L2 F2 B2 18f 118) D3 B2 D3 F2 U2 F2 B2 L2 D3 F2 D2 L2 D3 L2 D1 R2 F2 L2 18f 119) inverse of 118 120) D3 B2 D3 F2 D2 F2 B2 R2 D1 R2 D2 B2 U1 F2 U1 R2 F2 L2 18f 121) D3 B2 D3 L2 D2 B2 D1 L2 U2 F2 R2 L2 D3 R2 D1 F2 R2 B2 18f 122) D3 B2 D3 F2 U2 F2 B2 L2 U1 B2 U2 R2 D1 F2 U1 R2 F2 L2 18f 123) D3 B2 D3 F2 D2 F2 B2 R2 D1 R2 U2 F2 D1 L2 D1 R2 F2 L2 18f 124) D3 B2 D3 F2 D2 F2 B2 R2 U3 L2 U2 F2 D3 F2 U1 R2 F2 L2 18f 125) D3 B2 L2 D3 B2 D1 R2 B2 D2 B2 D1 F2 R2 U1 R2 D2 R2 B2 18f 126) inverse of 125 127) D3 B2 L2 D3 B2 D1 R2 B2 U2 F2 U1 R2 B2 D1 L2 U2 R2 B2 18f 128) D3 B2 L2 U3 L2 D1 B2 L2 U2 R2 U1 B2 L2 U1 L2 U2 R2 B2 18f 129) D3 B2 L2 U3 L2 D1 B2 L2 U2 R2 D1 L2 F2 D1 R2 D2 R2 B2 18f 130) D3 B2 L2 D3 B2 U1 F2 R2 D2 R2 U1 B2 L2 U1 L2 U2 R2 B2 18f 131) D3 B2 L2 D3 B2 D1 R2 B2 D2 B2 U1 L2 F2 D1 R2 D2 R2 B2 18f 132) D3 B2 R2 U3 F2 D3 R2 U1 L2 F2 L2 B2 U1 R2 D1 L2 U3 B2 18f 133) inverse of 132 134) D3 B2 L2 D3 F2 D3 R2 B2 U2 L2 B2 U1 R2 D1 B2 L2 U2 L2 18f 135) D3 B2 R2 D3 L2 U3 B2 R2 D2 F2 R2 U1 R2 D1 R2 F2 U2 B2 18f 136) D3 B2 L2 U3 R2 D3 B2 L2 U2 F2 L2 D1 L2 D1 F2 R2 D2 L2 18f 137) D3 B2 L2 D3 F2 U3 B2 L2 U2 F2 L2 U1 B2 U1 B2 L2 U2 L2 18f 138) D3 B2 L2 D3 F2 D3 R2 B2 D2 R2 F2 U1 L2 D1 F2 R2 D2 L2 18f kloosterman's position is number 46. mike From dik@cwi.nl Sat Jan 7 21:36:02 1995 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA11148; Sat, 7 Jan 95 21:36:02 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Sun, 8 Jan 1995 03:35:30 +0100 Received: by boring.cwi.nl id ; Sun, 8 Jan 1995 03:35:54 +0100 Date: Sun, 8 Jan 1995 03:35:54 +0100 From: Dik.Winter@cwi.nl Message-Id: <9501080235.AA01808=dik@boring.cwi.nl> To: cube-lovers@ai.mit.edu, mreid@ptc.com Subject: Re: two stage filtration > i've run an exhaustive search on the coset space G / H. the number > of cosets at each distance is: Ah, well. To think that I had the program publicly available since February 1993 through anonymous ftp, I ought to have thought about it when we got a machine large enough to run the program; about a year ago. Damn ;-). > distance quarter turns face turns I am running and will confirm tomorrow; no doubt about that. ... > to give a total of 2187 * 2048 * 495 = 2217093120 configurations. > to reduce this number somewhat, we can utilize symmetry. there are 16 > symmetries of the cube that preserve the U-D axis, and therefore > preserve the subgroup H. up to these symmetries, the number of distinct > corner configurations is 168, so we need only consider a mere > 168 * 2048 * 495 = 170311680 configurations. > (so far, this is the same approach that dik used for his calculation.) The approach is the same, but I did avoid the embarrasment you had later. I came up with 324 * 2048 * 495 = 328458240 configurations. > each configuration is stored with 2 bits of memory and thus the whole > space consumes about 42 megabytes. each configuration is assigned > one of 4 values: > distance is currently unknown > distance = current search depth > distance = current search depth - 1 > distance < current search depth - 1 > from here, i just used a simple breadth first search. This is similar to what I did outline about that time. It comes from a remark somebody not on this list (Arjeh Cohen) made to me about a file helping solving the cube. You store only the distance mod 3; that will give you a simple database to solve it. That again came from a talk at some congress I do not remember at this time of the night ;-). ... > i) only use the 8 symmetries that preserve my choice of > 12 edge facelets. I did this indeed. > run times were improved significantly by using a simple trick that i hadn't > used in earlier programs. during the first few depth levels, i use > "forward searching", i.e. i examine the neighbors of each configuration > found at the previous depth. however, after at least half the search space > has been found, i switch to "backward searching", i.e. examine the > configurations (and their neighbors) that haven't yet been found. > (have others been using this same idea when running similar search programs?) > closer analysis of this technique suggests that the switch from forward to > backward searching should occur even before half the space has been found. Here I am a bit surprised. I would think the time needed for a phase is entirely dependend on the number of neighbo(u)rs you have to examine. This appears to be 6 times the number of configurations you visit. So I would think that going the other way pays when the number of configurations not yet decided is less than the number of configurations found in the previous step. And no, I did not implement this; although it looks simple indeed. Phase 2 for me needs a bit of consideration as obviously you reduced the number of cases a bit more than I did when I wrote my program. (Mine still does not fit in 256 Mb.) More tomorrow. dik -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924098 home: bovenover 215, 1025 jn amsterdam, nederland; e-mail: dik@cwi.nl From dik@cwi.nl Sun Jan 8 05:56:01 1995 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA21545; Sun, 8 Jan 95 05:56:01 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Sun, 8 Jan 1995 11:55:56 +0100 Received: by boring.cwi.nl id ; Sun, 8 Jan 1995 11:55:55 +0100 Date: Sun, 8 Jan 1995 11:55:55 +0100 From: Dik.Winter@cwi.nl Message-Id: <9501081055.AA02279=dik@boring.cwi.nl> To: cube-lovers@ai.mit.edu, mreid@ptc.com Subject: Re: two stage filtration Mike Reid: > i've run an exhaustive search on the coset space G / H. the number > of cosets at each distance is: I can confirm Mike's results on phase 1. Here follows my table which also contains the number of local maxima (which you will not find in "backward" steps): turns q loc.max q+h loc.max 0 1 1 1 4 4 2 34 50 3 312 592 4 2772 7156 5 24996 87236 4 6 225949 5 1043817 97 7 2017078 32 12070278 2800 8 17554890 730 124946368 110582 9 139132730 39000 821605960 16713104 10 758147361 10861351 1199128738 750219596 11 1182378518 608836624 58202444 58196874 12 117594403 117439129 476 476 13 14072 14072 > 40 minutes for quarter turns, 47 minutes for face turns. this was done > on a DEC 3000 alpha 700, apparently a very fast machine. I got 131 minutes for quarter turns and 186 minutes for face turns on a measly SGI Challenge, apparently not so very fast. (I presume it would have been faster if it had been possible to run with 64 bit long's.) I will try to verify phase 2 later next week. dik From mschoene@math.rwth-aachen.de Sun Jan 8 07:50:49 1995 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA23788; Sun, 8 Jan 95 07:50:49 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rQx2I-000MPPC; Sun, 8 Jan 95 13:47 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rQx2I-00025cC; Sun, 8 Jan 95 13:47 WET Message-Id: Date: Sun, 8 Jan 95 13:47 WET From: "Martin Schoenert" To: BRYAN@wvnvm.wvnet.edu Cc: cube-lovers@life.ai.mit.edu In-Reply-To: "Jerry Bryan"'s message of Sat, 7 Jan 1995 10:15:52 EST <9501071609.AA16758@life.ai.mit.edu> Subject: Re: Re: Cube with GAP Jerry Bryan wrote in his e-mail message of 1995/01/07 Note that this model does not include the face centers. That is, it is G[C,E] rather than G[C,E,F]. 56 numbers would be required to include the face centers. The distinction between 48 facelets and 56 facelets bears on the nitpicky question of whether the set C of rotations is a subgroup of G or not. Absolutely right. This part of the GAP documentation was written years ago. These days I represent MG, CG, etc. as permutation groups on 54 points. I also changed the numbering, so that the [1..24] represent the edges, [25..48] points represent the edges, and [49..54] represent the centers. Jerry continued What I don't see is how to model the Supergroup in GAP. It looks like you would have to label each Face center with four numbers so you could see the rotations of the Face centers, but that seems like overkill. This is also correct. But GAP doesn't mind those 24 more points. Jerry continued When I write the model out to disk, I only write out 8 corner facelets and 12 edge facelets. For example, I only write out the front and back corner facelets. This saves space and converts the model from a facelet model to a cubie model, with the twists implicitly encoded rather than being explicitly encoded via multiplication tables. It also automatically establishes a frame of reference by which a proof of conservation of twist and flip can be accomplished. In terms of computational group theory this sequence of 8 corner and 12 edgde facelets is called a *base* for the permutation group G. That is, each element of the group is uniquely determined by the images of those 20 facelets. Of course if you have already proved that no single corner can be twisted and no single edge can be flipped, you can reduce this to 7 corner and 11 edge facelets. Mark Longridge wrote in his e-mail message of 1995/01/03 ... I don't know how a normal 4x4x4 could be represented though. Jerry answered I fail to see the problem. Just number the facelets. The only problem would then lie in deciding what the generators are -- i.e., which kind of slice moves do you accept. You would also have to decide whether to model the invisible 2x2x2 inside, but again if you did, just number the invisible facelets and include their movements with your generators. The problem is that many different positions all look solved. For example, you can permute the 4 center facelets of one face or exchange two adjacent edges, and the cube still looks solved (of course you cannot do all this independently). So if we take the obvious permutation group on the 6*16 points, then a whole subgroup would correspond to what a puzzler would consider solved states. If by a model we mean a group whose elements correspond to the different states a puzzler would see, and whose identity corresponds to what a puzzler would consider solved, then I have no good idea how to model the 4x4x4 cube as a permutation group. 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 mreid@ptc.com Sun Jan 8 16:14:33 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA11497; Sun, 8 Jan 95 16:14:33 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA11704; Sun, 8 Jan 95 16:13:05 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA07786; Sun, 8 Jan 1995 16:25:34 -0500 Date: Sun, 8 Jan 1995 16:25:34 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501082125.AA07786@ducie.ptc.com> To: dik@cwi.nl, cube-lovers@ai.mit.edu Subject: Re: two stage filtration Content-Length: 1392 dik writes: > > run times were improved significantly by using a simple trick that i hadn't > > used in earlier programs. during the first few depth levels, i use > > "forward searching", i.e. i examine the neighbors of each configuration > > found at the previous depth. however, after at least half the search space > > has been found, i switch to "backward searching", i.e. examine the > > configurations (and their neighbors) that haven't yet been found. > > > (have others been using this same idea when running similar search programs?) > > > closer analysis of this technique suggests that the switch from forward to > > backward searching should occur even before half the space has been found. > > Here I am a bit surprised. I would think the time needed for a phase is > entirely dependend on the number of neighbo(u)rs you have to examine. This > appears to be 6 times the number of configurations you visit. So I would > think that going the other way pays when the number of configurations not > yet decided is less than the number of configurations found in the previous > step. except that when searching backward, you need not visit all the neighbors of a configuration. you only need to find one neighbor at the previous distance; after that, the other neighbors don't need to be examined. i did not realize this until implementing this technique. mike From mreid@ptc.com Sun Jan 8 16:28:22 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA11881; Sun, 8 Jan 95 16:28:22 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA11783; Sun, 8 Jan 95 16:26:58 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA07811; Sun, 8 Jan 1995 16:39:27 -0500 Date: Sun, 8 Jan 1995 16:39:27 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501082139.AA07811@ducie.ptc.com> To: dik@cwi.nl, cube-lovers@ai.mit.edu Subject: Re: two stage filtration Content-Length: 714 dik writes > I can confirm Mike's results on phase 1. great! > Here follows my table which > also contains the number of local maxima (which you will not find in > "backward" steps): this is true. i decided i was more interested in performance than in knowing about local maxima. > I will try to verify phase 2 later next week. let me offer a suggestion here. since i divided the corner configurations by symmetry, it might be nicer if you divide the U-D edge configurations by symmetry. (the numbers involved are the same.) it's always nice to confirm a calculation like this using a different method. although what i'm suggesting isn't much of a change. mike From dik@cwi.nl Sun Jan 8 19:08:05 1995 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17727; Sun, 8 Jan 95 19:08:05 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Mon, 9 Jan 1995 01:07:56 +0100 Received: by boring.cwi.nl id ; Mon, 9 Jan 1995 01:07:55 +0100 Date: Mon, 9 Jan 1995 01:07:55 +0100 From: Dik.Winter@cwi.nl Message-Id: <9501090007.AA02883=dik@boring.cwi.nl> To: cube-lovers@ai.mit.edu, mreid@ptc.com Subject: Re: two stage filtration [ Mike: You need not visit all neighbors when going backwards. ] Right you are; I missed that completely. dik From dik@cwi.nl Sun Jan 8 19:12:24 1995 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA18508; Sun, 8 Jan 95 19:12:24 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Mon, 9 Jan 1995 01:12:17 +0100 Received: by boring.cwi.nl id ; Mon, 9 Jan 1995 01:12:17 +0100 Date: Mon, 9 Jan 1995 01:12:17 +0100 From: Dik.Winter@cwi.nl Message-Id: <9501090012.AA02894=dik@boring.cwi.nl> To: cube-lovers@ai.mit.edu, mreid@ptc.com Subject: Re: two stage filtration > this is true. i decided i was more interested in performance than > in knowing about local maxima. > > I will try to verify phase 2 later next week. > let me offer a suggestion here. since i divided the corner configurations > by symmetry, it might be nicer if you divide the U-D edge configurations > by symmetry. (the numbers involved are the same.) I will see how I divide it now, but I can change easily. My biggest change is to weed out parity. I just realized that, but that is the reason it will not fit now. Moreover, I will go completely forward to get also local maxima. I do not know yet what to do about the quarter turn version. I never put that in my program for this phase. I had some form of quarter turn version, but only for U and D. I will see, dik From BRYAN@wvnvm.wvnet.edu Sun Jan 8 23:24:08 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA27846; Sun, 8 Jan 95 23:24:08 EST Message-Id: <9501090424.AA27846@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 7702; Sun, 08 Jan 95 23:16:57 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 9435; Sun, 8 Jan 1995 23:16:57 -0500 X-Acknowledge-To: Date: Sun, 8 Jan 1995 23:16:52 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: kociemba's algorithm for quarter turns In-Reply-To: Message of 01/05/95 at 17:12:18 from mreid@ptc.com On 01/05/95 at 17:12:18 mreid@ptc.com said: >for much too long now, i've meant to implement kociemba's algorithm >for quarter turns. finally i've gotten around to it, and it's found >superflip: > B3 L3 U3 L3 F1 U1 D1 L3 B1 U1 F1 R3 L1 F3 B2 U1 D1 F2 B2 R2 U1 D1 26q I read the articles in the archives about Kociemba's algorithm about a year ago, without (I confess) fully understanding them. In particular, I do not fully understand what differentiates Kociemba's algorithm from Thistlethwaite's algorithm, other than it uses a different arrangement of nested subgroups. I shall strive to read the articles again with a deeper level of understanding. But in the meantime, I wonder if you could verify that Kociemba's algorithm does not guarantee to find a minimal process? In particular, is it the case that 26q is a minimal superflip, or is it only an upper bound? The reason I ask is that I have decided to go ahead and calculate God's Algorithm under quarter turns for depth 11. (Through depth 10 is already in hand.) Once that is accomplished, it should be a *fairly* easy task to establish a lower bound on the superflip at 22 quarter turns via two half depth searches. In fact, the second half depth search should be fairly easy to accomplish because all I have to do is superflip each element of the data base from the first search to establish the data base for the second search. I can already establish a lower bound of 14 quarter turns on the superflip. It may be recalled that I was able to accomplish a complete search for edges-only (no corners, no Face centers, and rotations considered equivalent). There was some consternation when I reported that the superflip was 9 quarter turns from Start because the superflip is even. But without Face centers and with rotations considered equivalent, normal parity rules do not apply. I am now working on edges-only, either with centers, or else with rotations *not* considered equivalent (either G[E,F] or G[E]), depending on which way you want to think about it. In this case, the superflip really is even. I am working on level 13, and the superflip has not yet appeared. Hence, it is at least at level 14 (without corners), and will therefore be at least at level 14 when the corners are added in. Strictly speaking, the superflip has appeared already, and at level 9 just where it had to appear. But in its appearance at level 9, it is composed with a non-trivial rotation, so it isn't the superflip as the superflip is normally understood. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 dik@cwi.nl Mon Jan 9 17:25:44 1995 Return-Path: Received: from hera.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA12462; Mon, 9 Jan 95 17:25:44 EST Received: from boring.cwi.nl by hera.cwi.nl with SMTP id ; Mon, 9 Jan 1995 23:25:25 +0100 Received: by boring.cwi.nl id ; Mon, 9 Jan 1995 23:24:17 +0100 Date: Mon, 9 Jan 1995 23:24:17 +0100 From: Dik.Winter@cwi.nl Message-Id: <9501092224.AA05290=dik@boring.cwi.nl> To: BRYAN@wvnvm.wvnet.edu, Cube-Lovers@ai.mit.edu Subject: Re: kociemba's algorithm for quarter turns > I read the articles in the archives about Kociemba's algorithm about > a year ago, without (I confess) fully understanding them. In particular, > I do not fully understand what differentiates Kociemba's algorithm from > Thistlethwaite's algorithm, other than it uses a different arrangement > of nested subgroups. The basis is similar (although Kociemba's algorithm uses searching to get solutions while Thistlethwaite's uses tables and directly arrives at solutions). The main difference is that once a solution is found Thistlethwaite's algorithm stops. Kociemba's algorithm continues finding newer solutions (even longer than the original solution) to phase 1 and trying to fit them with a solution for phase 2 such that the total solution is shorter. This proves to be very effective. Of course this is easier to do with a 2 phase algorithm than with a 4 phase algorithm. > But in the meantime, I wonder if you could verify that Kociemba's > algorithm does not guarantee to find a minimal process? In particular, > is it the case that 26q is a minimal superflip, or is it only an > upper bound? Given time Kociemba's algorithm will find a minimal solution. I confess that my implementations does not if the configuration can be solved through phase 2 only, but the cube can be rotated to avoid that. The reason is that ultimately Kociemba's algorithm will find longer part solutions of phase 1 and ultimately stumble on a complete solution in phase 1 which will be minimal because of the breadth first search. But it can take long. Getting a minimal solution if the length is 16 or less appears to be doable. If the length is 19 or more it takes an awfully long time. What I have found until now is: 1. There are no configurations known that require 21 turns or more, and I checked an awfully large number. 2. There are known configurations that require 18 turns. The middle part is a grey area. From mreid@ptc.com Mon Jan 9 18:04:52 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA14555; Mon, 9 Jan 95 18:04:52 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA16591; Mon, 9 Jan 95 18:03:21 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA09092; Mon, 9 Jan 1995 18:15:55 -0500 Date: Mon, 9 Jan 1995 18:15:55 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501092315.AA09092@ducie.ptc.com> To: cube-lovers@ai.mit.edu, bryan@wvnvm.wvnet.edu Subject: Re: kociemba's algorithm for quarter turns Content-Length: 3238 jerry writes > I read the articles in the archives about Kociemba's algorithm about > a year ago, without (I confess) fully understanding them. In particular, > I do not fully understand what differentiates Kociemba's algorithm from > Thistlethwaite's algorithm, other than it uses a different arrangement > of nested subgroups. thistlethwaite's algorithm is a method which guarantees solving any cube in at most 52 (well, now it's 44) face turns. i don't think it was ever really used to find short solutions (although at the time it was invented, 52 face turns may have been considered short). kociemba's algorithm is a method for finding short solutions. it didn't come with any guarantees, (although i've just shown that the first solution it finds is at most 43 quarter [30 face] turns, and in these extreme cases, it will quickly find a shorter solution.) kociemba gave an effective way to navigate through the sequence of subgroups G = , H = , 1 = <>, without using enormous tables. (this is how it differs from thistlethwaite's method, and also why there are (well, were) no guarantees.) kociemba also allows non-optimal sequences in stage 1 in exchange for shorter sequences in stage 2. we start by finding all length n sequences in stage 1, and for each, the shortest sequence in stage 2. then we move on to length n + 1 in stage 1. kociemba's method is so effective, that searching through length 14 or 15 in stage 1 is usually quite feasible. also, this technique has been so successful that it's improved many of the shortest known maneuvers. > But in the meantime, I wonder if you could verify that Kociemba's > algorithm does not guarantee to find a minimal process? In particular, > is it the case that 26q is a minimal superflip, or is it only an > upper bound? 26q is only an upper bound. my program will eventually find the shortest process, well, if my os doesn't crash first, the universe doesn't end, ... but i've only given the shortest maneuver it's found so far. at some point you've gotta give up. (there are plenty of other patterns waiting to be stuffed into this program. :-) ) > The reason I ask is that I have decided to go ahead and calculate God's > Algorithm under quarter turns for depth 11. (Through depth 10 is > already in hand.) Once that is accomplished, it should be a > *fairly* easy task to establish a lower bound on the superflip > at 22 quarter turns via two half depth searches. you should search with the list you have right now. (i presume you're talking about a list of all positions within 10q of START.) you will either find a maneuver of length <= 20q (unlikely, i'd say), or you will show that its distance from START is >= 22q. this latter possibility would be very exciting, since it would raise the lower bound on the diameter of G. > I can already establish a lower bound of 14 quarter turns on the > superflip. my program can do this in only a few seconds! in fact, it takes 12q to get from superflip into the subgroup H. since we may also suppose that the last twist in a shortest maneuver is U , it follows that superflip requires at least 13q (and thus 14q , by parity). mike From TanisElf@aol.com Mon Jan 9 18:35:45 1995 Return-Path: Received: from mail02.mail.aol.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA16276; Mon, 9 Jan 95 18:35:45 EST Received: by mail02.mail.aol.com (1.38.193.5/16.2) id AA14331; Mon, 9 Jan 1995 18:36:41 -0500 Date: Mon, 9 Jan 1995 18:36:41 -0500 From: TanisElf@aol.com Message-Id: <950109183639_3748705@aol.com> To: cube-lovers@life.ai.mit.edu Subject: remove from list Please remove me from this mailing list TanisElf@aol.com Tanis From alan@curry.epilogue.com Mon Jan 9 18:49:15 1995 Return-Path: Received: from curry.epilogue.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17354; Mon, 9 Jan 95 18:49:15 EST Received: (from alan@localhost) by curry.epilogue.com (8.6.8/8.6.6) id SAA07465; Mon, 9 Jan 1995 18:50:54 -0500 Date: Mon, 9 Jan 1995 18:50:54 -0500 Message-Id: <9Jan1995.184223.Alan@LCS.MIT.EDU> From: Alan Bawden Sender: Cube-Lovers-Request@ai.mit.edu To: TanisElf@aol.com Cc: cube-lovers@ai.mit.edu In-Reply-To: TanisElf@aol.com's message of Mon, 9 Jan 1995 18:36:41 -0500 <950109183639_3748705@aol.com> Subject: remove from list Date: Mon, 9 Jan 1995 18:36:41 -0500 From: TanisElf@aol.com To: cube-lovers@life.ai.mit.edu ^^^^^^^^^^^ Subject: remove from list Please remove me from this mailing list TanisElf@aol.com Tanis YOU ARE AN IDIOT! WHY DID YOU ASK THE -ENTIRE- MAILING LIST? I told you quite clearly when I added you that you get off the list by sending mail to Cube-Lovers-REQUEST@AI.MIT.EDU. And I am purposely CC'ing this message to the entire Cube-Lovers mailing list in order to remind everyone else about Cube-Lovers-REQUEST, because invariably when one idiot makes this mistake, a whole pack of other lemming-idiots follows the first idiot and makes the same mistake. From ncramer@bbn.com Tue Jan 10 09:54:58 1995 Return-Path: Received: from LABS-N.BBN.COM by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA28269; Tue, 10 Jan 95 09:54:58 EST Message-Id: <9501101454.AA28269@life.ai.mit.edu> Date: Tue, 10 Jan 95 9:47:23 EST From: Nichael Cramer To: cube-lovers@life.ai.mit.edu Subject: Source for Cheap 5X Cubes ...and now that Alan has _that_ out of his system... ;-) For the interested: A topic that has come up a few times (and of which I was in hot pursuit for a couple of years): I just got a new Ishi Press flier in the mail yesterday. Among other toys they were selling 5X5X5 cubes for $20 (+S&H). There order number is (800) 859-2086. (Include standard disclaimers re non-connectedness, etc.) Enjoy Nichael ncramer@bbn.com Paradise Farm Brattleboro VT From news@nntp-server.caltech.edu Tue Jan 10 12:45:58 1995 Return-Path: Received: from piccolo.cco.caltech.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07564; Tue, 10 Jan 95 12:45:58 EST Received: from gap.cco.caltech.edu by piccolo.cco.caltech.edu with ESMTP (8.6.7/DEI:4.41) id JAA05353; Tue, 10 Jan 1995 09:45:48 -0800 Received: by gap.cco.caltech.edu (8.6.7/DEI:4.41) id JAA05375; Tue, 10 Jan 1995 09:45:41 -0800 To: mlist-cube-lovers@nntp-server.caltech.edu Path: nntp-server.caltech.edu!txr From: txr@alumni.caltech.edu (Tim Rentsch) Newsgroups: mlist.cube-lovers Subject: Re: kociemba's algorithm for quarter turns Date: 10 Jan 1995 17:45:35 GMT Organization: California Institute of Technology CCO Unix cluster Lines: 40 Message-Id: References: <9501092224.AA05290=dik@boring.cwi.nl> Nntp-Posting-Host: alumni.caltech.edu In-Reply-To: Dik.Winter@cwi.nl's message of Mon, 09 Jan 95 23:03:57 GMT Dik.Winter@cwi.nl writes: >But it can take long. Getting a minimal solution if the length is 16 >or less appears to be doable. If the length is 19 or more it takes an >awfully long time. What I have found until now is: >1. There are no configurations known that require 21 turns or more, > and I checked an awfully large number. >2. There are known configurations that require 18 turns. >The middle part is a grey area. How hard would it be to write a program to try the following? 1) Initialize set S with a configuration that requires a large number of turns (the max, perhaps). 2) Test the length of all configurations one turn from any configuration in S. 3) If one or more of these has a minimum length longer than the initial position, replace the set S with the set of those configuration with longer length (of course print out useful intermediate result). 4) If none of the test positions has a minimum length longer than the length of positions in S, replace the set of test positions with positions one more turn away, and test again until 3 works. (Obviously it would be useful to store something about previous results so that work is not redone needlessly. I think it's easy to figure out what information should be stored, although I haven't done so.) 5) Give up when patience is exhausted. It would be nice to get a higher lower bound, and this seems like a plausible way of doing so. regards, Tim Rentsch From ishius@ishius.com Tue Jan 10 13:14:59 1995 Return-Path: Received: from holonet.net (orac.holonet.net) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA09074; Tue, 10 Jan 95 13:14:59 EST Received: from DialupEudora (ishius@localhost) by holonet.net (Anton Dovydaitis) with SMTP id KAA07315; Tue, 10 Jan 1995 10:08:07 -0800 Date: Tue, 10 Jan 1995 10:08:07 -0800 Message-Id: <199501101808.KAA07315@holonet.net> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: cube-lovers@life.ai.mit.edu From: ishius@ishius.com (ishius@holonet.net) Subject: Re: Source for Cheap 5X Cubes >For the interested: > >A topic that has come up a few times (and of which I was in hot pursuit for >a couple of years): I just got a new Ishi Press flier in the mail >yesterday. Among other toys they were selling 5X5X5 cubes for $20 (+S&H). > >There order number is (800) 859-2086. Yes, these are on sale for $20 plus S/H. However, I must say that as they are difficult to manufacture, the mechanism is not as smooth as I would prefer, the center cube faces sometimes need to be reglued, and the stickers sometimes slide. On the other hand, these are the only 5x5x5 cubes you can get (to my knowledge), and they are only $20.00. Also, if you buy one, you can buy a Toyo Glass puzzle for $8.70 (they usually go for $25 to $40). I KNOW you guys would like a 4x4x4 cube, but I can't find them. We do have another rotational puzzle called the SKEWB, also for $20.00, which is a cube with 4 diagonal cuts that pass through all six faces of the cube (so that any move changes all six faces). The mechanism is very smooth and very well made, and I've NEVER had a defective one yet. If you're familiar with the SKEWB, I would like to know whether it's harder or easier than the classic 3x3x3 Rubik's Cube (I suspect it's simpler, but it has fewer symmetries). If you would like a full color catalog of our puzzles, including the latest offerings, please send me your POSTAL mailing address. 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 dlitwin@geoworks.com Tue Jan 10 14:26:42 1995 Return-Path: Received: from geoworks.com (fusion.geoworks.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA12974; Tue, 10 Jan 95 14:26:42 EST Received: from radium.geoworks.com.geoworks by geoworks.com (4.1/SMI-4.1) id AA14522; Tue, 10 Jan 95 11:23:44 PST Date: Tue, 10 Jan 95 11:23:44 PST From: dlitwin@geoworks.com (David Litwin) Message-Id: <9501101923.AA14522@geoworks.com> To: ishius@ishius.com (ishius@holonet.net) Cc: cube-lovers@life.ai.mit.edu In-Reply-To: <199501101808.KAA07315@holonet.net> Subject: Re: Source for Cheap 5X Cubes ishius@holonet.net writes: > Yes, these are on sale for $20 plus S/H. However, I must say that as they > are difficult to manufacture, the mechanism is not as smooth as I would > prefer, the center cube faces sometimes need to be reglued, and the stickers > sometimes slide. With regard to the stickers (as far as I can tell just the orange side has problems) I had good luck following the suggetions that came with mine (written up by Christoph Bandelow). They recommend placing a piece of paper over the cube and ironing (not too hot). This melts the glue and the stickers get a better grip. I've not had any problems since. Dave Litwin From whuang@cco.caltech.edu Tue Jan 10 16:44:58 1995 Return-Path: Received: from piccolo.cco.caltech.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA22169; Tue, 10 Jan 95 16:44:58 EST Received: from accord.cco.caltech.edu by piccolo.cco.caltech.edu with ESMTP (8.6.7/DEI:4.41) id NAA00237; Tue, 10 Jan 1995 13:44:49 -0800 From: whuang@cco.caltech.edu (Wei-Hwa Huang) Received: by accord.cco.caltech.edu (8.6.7/UGCS:4.41) id NAA23853; Tue, 10 Jan 1995 13:44:47 -0800 Message-Id: <199501102144.NAA23853@accord.cco.caltech.edu> Subject: Re: SKEWB To: cube-lovers@life.ai.mit.edu Date: Tue, 10 Jan 1995 13:44:47 -0800 (PST) In-Reply-To: <199501101808.KAA07315@holonet.net> from "ishius@holonet.net" at Jan 10, 95 10:08:07 am X-Mailer: ELM [version 2.4 PL22] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 495 > > If you're familiar with the SKEWB, > I would like to know whether it's harder or easier than the classic 3x3x3 > Rubik's Cube (I suspect it's simpler, but it has fewer symmetries). It took me a while to give out a working algorithm from it. Surprizingly my moves have very little use on Rubik's, and if the SKEWB wasn't as simple as it was it would be really tough to work out. Fortunately, due to its simplicity I need to remember only one code sequence. (Solution posted on request.) From brett@math.toronto.edu Tue Jan 10 16:48:40 1995 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 AA23054; Tue, 10 Jan 95 16:48:40 EST Message-Id: <9501102148.AA23054@life.ai.mit.edu> Subject: seminar I have to give To: cube-lovers@ai.mit.edu (cube) Date: Tue, 10 Jan 1995 16:48:47 -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: 163 I have to give a small seminar in two weeks and thought I might do it on something cube related. Can anyone give me suggestions on topics, please thanks brett From whuang@cco.caltech.edu Tue Jan 10 16:48:49 1995 Return-Path: Received: from piccolo.cco.caltech.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA23061; Tue, 10 Jan 95 16:48:49 EST Received: from accord.cco.caltech.edu by piccolo.cco.caltech.edu with ESMTP (8.6.7/DEI:4.41) id NAA00769; Tue, 10 Jan 1995 13:48:46 -0800 From: whuang@cco.caltech.edu (Wei-Hwa Huang) Received: by accord.cco.caltech.edu (8.6.7/UGCS:4.41) id NAA24322; Tue, 10 Jan 1995 13:48:42 -0800 Message-Id: <199501102148.NAA24322@accord.cco.caltech.edu> Subject: SKEWB To: cube-lovers@life.ai.mit.edu Date: Tue, 10 Jan 1995 13:48:41 -0800 (PST) X-Mailer: ELM [version 2.4 PL22] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 973 > > > ishius@holonet.net writes: > > > Yes, these are on sale for $20 plus S/H. However, I must say that as they > > > are difficult to manufacture, the mechanism is not as smooth as I would > > > prefer, the center cube faces sometimes need to be reglued, and the stickers > > > sometimes slide. > > > > With regard to the stickers (as far as I can tell just the orange > > side has problems) I had good luck following the suggetions that came with > > mine (written up by Christoph Bandelow). They recommend placing a piece of > > paper over the cube and ironing (not too hot). This melts the glue and the > > stickers get a better grip. I've not had any problems since. > > > > Dave Litwin > > > I believe the poster is referring to the fact that the plastic faces fall > off, revealing a screw inside, not the stickers (which are well done). > Super-glue solved my problem easily. One more thing: the mechanism gets > smoother after repeated use. > > > From brett@math.toronto.edu Tue Jan 10 17:01:33 1995 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 AA23595; Tue, 10 Jan 95 17:01:33 EST Message-Id: <9501102201.AA23595@life.ai.mit.edu> Subject: solid brass cube To: cube-lovers@ai.mit.edu (cube) Date: Tue, 10 Jan 1995 17:01:42 -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: 209 My friend gave me a solid brass cube for the holidays. he found it in a small antiques store in L.A. and thought I would like it. Does anyone know the origin of this novelty? brett brett@math.toronto.edu From dlitwin@geoworks.com Tue Jan 10 17:18:09 1995 Return-Path: Received: from geoworks.com (fusion.geoworks.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA25088; Tue, 10 Jan 95 17:18:09 EST Received: from radium.geoworks.com.geoworks by geoworks.com (4.1/SMI-4.1) id AA18001; Tue, 10 Jan 95 14:13:01 PST Date: Tue, 10 Jan 95 14:13:01 PST From: dlitwin@geoworks.com (David Litwin) Message-Id: <9501102213.AA18001@geoworks.com> To: whuang@cco.caltech.edu (Wei-Hwa Huang) Cc: cube-lovers@life.ai.mit.edu In-Reply-To: <199501102148.NAA24322@accord.cco.caltech.edu> Subject: SKEWB Wei-Hwa Huang writes: > Dave Litwin writes: > > ishius@holonet.net writes: > > > ... > > > I would prefer, the center cube faces sometimes need to be reglued, > > > and the stickers sometimes slide. > > > > With regard to the stickers (as far as I can tell just the orange > > ... > > > > Dave Litwin > > I believe the poster is referring to the fact that the plastic faces fall > off, revealing a screw inside, not the stickers (which are well done). > Super-glue solved my problem easily. One more thing: the mechanism gets > smoother after repeated use. If you notice the last line of the ishius@holonet.net post, they also mention the stickers sliding, which is what I was addressing. I've only noticed 1 or 2 out of the at least 30 I've seen that *don't* have a problem with the orange stickers: sliding off, dog earing etc. The problem of the center caps coming off is separate, and much easier to fix. Actually, before you glue them on you may want to adjust the tensions of the screws on all the axes (only requiring one cap per axis, not all six). The few I've done this to move much smoother when loosened (just a bit, as being too loose can cause problems of its own). Dave Litwin From mouse@collatz.mcrcim.mcgill.edu Tue Jan 10 17:20:31 1995 Return-Path: Received: from Collatz.McRCIM.McGill.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA25297; Tue, 10 Jan 95 17:20:31 EST Received: (root@localhost) by 10414 on Collatz.McRCIM.McGill.EDU (8.6.8.1 Mouse 1.0) id RAA10414; Tue, 10 Jan 1995 17:20:19 -0500 Date: Tue, 10 Jan 1995 17:20:19 -0500 From: der Mouse Message-Id: <199501102220.RAA10414@Collatz.McRCIM.McGill.EDU> To: dlitwin@geoworks.com, ishius@ishius.com Subject: Re: Source for Cheap 5X Cubes Cc: cube-lovers@life.ai.mit.edu >> Yes, these [5x5x5 Cubes] are on sale for $20 plus S/H. However, I >> must say that as they are difficult to manufacture, the mechanism is >> not as smooth as I would prefer, the center cube faces sometimes >> need to be reglued, and the stickers sometimes slide. > With regard to the stickers (as far as I can tell just the orange > side has problems) [...] recommend placing a piece of paper over the > cube and ironing (not too hot). This melts the glue and the stickers > get a better grip. I've not had any problems since. My experience matches yours, in that only the orange side has trouble. I found that a tiny little dab of plain ordinary contact cement would nail down a sticker very nicely. Four of the 25 orange-side stickers on my 5x5x5 (which I understand the local shop got from Ishi Press, btw Anton :-) show evidence of my having used a little too much contact cement; I don't recall how many others got glued with a more appropriate amount. As for 4x4x4s, I own one but have been unable to find it lately. This doesn't bother me especially, since given a 5x5x5, if you just ignore the center slice along each axis (remove the stickers, paint white-out over them, etc) and you have something mathematically identical to a 4x4x4. der Mouse mouse@collatz.mcrcim.mcgill.edu From mouse@collatz.mcrcim.mcgill.edu Tue Jan 10 18:14:19 1995 Return-Path: Received: from Collatz.McRCIM.McGill.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA27832; Tue, 10 Jan 95 18:14:19 EST Received: (root@localhost) by 10516 on Collatz.McRCIM.McGill.EDU (8.6.8.1 Mouse 1.0) id SAA10516; Tue, 10 Jan 1995 18:14:15 -0500 Date: Tue, 10 Jan 1995 18:14:15 -0500 From: der Mouse Message-Id: <199501102314.SAA10516@Collatz.McRCIM.McGill.EDU> To: cube-lovers@life.ai.mit.edu Subject: Difficulty of Skewb Cc: ishius@ishius.com > If you're familiar with the SKEWB, I would like to know whether it's > harder or easier than the classic 3x3x3 Rubik's Cube (I suspect it's > simpler, but it has fewer symmetries). I think I have a skewb. Each face is cut into a square turned 45 degrees, and four little 45-45-90 triangles, right? And there are four cuts you can turn it about, all passing through the center of the cube? In that case, here's my opinion. Mathematically, it verges on trivial compared to the 3x3x3, but because it's deep-cut, there are no stable portions to take the psychological place of the face centers on the 3x3x3, and each turn affects all six faces so, unlike the 2x2x2, there are no unaffected faces to pick up the slack. These combine to make it difficult for psychological reasons. I called it verging on trivial, but that is relative to the 3x3x3. There is some structure. If the 3x3x3 has 8!*3^8*12!*2^12 "imaginable" configurations (of which only 1/12 are reachable from any given state), the skewb has only 8!*3^8*6! "imaginable". Of these, far less than 1/12 are reachable; in my estimate, not having thought about it hard, the reachable number is (4!*4!)*(3^8/3)*(6!/2), or only one in 420 of the "imaginable" configurations, a reduction achieved largely due to the constraints on corner mixing: they form two tetrahedral sets, and it is not possible to mix the sets. Thus 8! turns into 4!*4!; this is a factor of 70. The additional factor of 6 comes from the usual sort of parity constraints, and again is only my guess. The size of the thing is thus somewhere on the order of 500 million configurations. This is why I called it trivial next to the 3x3x3. :-) The group structure in terms of facicles, for what's-his-name to sic GAP on should he care to, derived from the following facicle labeling +----------+ | 6 7 | | 8 | | 9 10 | +----------+----------+----------+----------+ | 1 2 | 11 12 | 21 22 | 31 32 | | 3 | 13 | 23 | 33 | | 4 5 | 14 15 | 24 25 | 34 35 | +----------+----------+----------+----------+ | 16 17 | | 18 | | 19 20 | +----------+ is: Cut 1: (15 7 4) (24 31 19) (17 22 35) (20 25 34) (18 23 33) Cut 2: (12 1 20) (10 32 25) (21 6 34) (22 7 31) (23 8 33) Cut 3: (11 19 22) ( 2 35 7) ( 9 4 31) ( 6 1 32) ( 8 3 33) Cut 4: (14 25 6) (16 34 1) ( 5 20 32) ( 4 19 35) ( 3 18 33) (This formulation holds facicle 13 fixed at all times.) der Mouse mouse@collatz.mcrcim.mcgill.edu From dik@cwi.nl Tue Jan 10 18:20:52 1995 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA28829; Tue, 10 Jan 95 18:20:52 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Wed, 11 Jan 1995 00:09:41 +0100 Received: by boring.cwi.nl id ; Wed, 11 Jan 1995 00:09:40 +0100 Date: Wed, 11 Jan 1995 00:09:40 +0100 From: Dik.Winter@cwi.nl Message-Id: <9501102309.AA08275=dik@boring.cwi.nl> To: cube-lovers@life.ai.mit.edu, txr@alumni.caltech.edu Subject: Re: kociemba's algorithm for quarter turns > Dik.Winter@cwi.nl writes: > >But it can take long. Note the word *long*. There is a 20-turn sequence for superflip. I have tried for shorter sequences using Kociemba's algorithm. (The 20-turn sequence does not take so awfully long to find, something like a day on this machine * perhaps). I started the program 12 November 1993 at 12:03. At 11 December 11:58 it had searched phase1 up to length 16. Alas, the machine crashed on 16 December 22:14. The problem is the awfully large number of solutions that come out of phase 1 and that have to be checked &. To wit: Length phase 1 number complete solutions 8 0 9 0 10 3072 L=23, L=22 11 61568 L=21 12 792256 13 8695488 L=20 14 87912832 15 841171136 16 7765525280 % The following solutions were successively found: L=23: F1 B1 R1 F2 R2 U3 D1 F1 R1 L1 B2 D1 F2 B2 D3 B2 D1 B2 U2 R2 B2 D1 B2 L=22: F1 B1 R1 F2 R2 U3 D1 F1 R3 L1 U1 R2 F2 D3 B2 D3 R2 L2 U3 F2 D2 L2 L=21: F1 B1 R1 U2 B2 U3 D3 R2 B3 R1 L1 U1 F2 L2 D2 B2 D3 F2 D1 L2 D1 L=20: F1 B1 U2 R1 F2 R2 B2 U3 D1 F1 U2 R3 L3 U1 B2 D1 R2 U1 B2 U1 So the next step is 17 in phase 1 with at most 2 turns in phase 2. I will start the program again sometime. So we find more than a month for a single configuration. And for this we need not check neighbors as the configuration is at a local maximum. I have another file with longuish configuration. That is from a period when I tried random configurations, the results were: turns #conf 16 1 17 24 18 248 19 1429 20 8481 total 10183 This has also taken an awfully long time to do (I think it was about 2 months). I let the program stop as soon as it had found a solution of 20 turns or less. All random configurations were solved, but many of the 20 turn configurations have shorter solutions. So yes, it can be done, but: > 5) Give up when patience is exhausted. this will come up before anything useful can be concluded I think. Unless something can be done to reduce the numbers. It is possible because there are configurations that will come up many times during the process, but I do not yet know what to do about that within a reasonable amount of memory. -- * The machine is one processor of a Cray SMP: a 66 MHz Sparc. & The number is much larger than what I found with other configurations, for 15 turns about 800 times as large as the second largest. % Estimated, there was overflow. It can be off an integer multiple of 4294967296. From mreid@ptc.com Tue Jan 10 18:46:05 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA29380; Tue, 10 Jan 95 18:46:05 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA26317; Tue, 10 Jan 95 18:44:42 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA18972; Tue, 10 Jan 1995 18:57:20 -0500 Date: Tue, 10 Jan 1995 18:57:20 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501102357.AA18972@ducie.ptc.com> To: cube-lovers@ai.mit.edu Subject: superflip Content-Length: 131 this just appeared today, after a lot of searching: R3 U2 B1 L3 F1 U3 B1 D1 F1 U1 D3 L1 D2 F3 R1 B3 D1 F3 U3 B3 U1 D3 24q mike From diamond@jrdv04.enet.dec-j.co.jp Tue Jan 10 20:02:53 1995 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 AA03464; Tue, 10 Jan 95 20:02:53 EST Received: by jnet-gw-1.dec-j.co.jp (8.6.9/JNET-GW-940327.1); id KAA18147; Wed, 11 Jan 1995 10:01:29 +0900 Message-Id: <9501110102.AA07690@jrdmax.jrd.dec.com> Received: from jrdv04.enet.dec.com by jrdmax.jrd.dec.com (5.65/JULT-4.3) id AA07690; Wed, 11 Jan 95 10:02:47 +0900 Received: from jrdv04.enet.dec.com; by jrdmax.enet.dec.com; Wed, 11 Jan 95 10:02:48 +0900 Date: Wed, 11 Jan 95 10:02:48 +0900 From: Norman Diamond 11-Jan-1995 1001 To: cube-lovers@life.ai.mit.edu Apparently-To: cube-lovers@life.ai.mit.edu Subject: Re: Source for Cheap 5X Cubes Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=ISO-2022-JP >I KNOW you guys would like a 4x4x4 cube, Last catalog that I received from the maker of the 5x5x5 and Skewb also had a 4x4x4 in it, though that was a few years ago. Meanwhile, I think the 4x4x4 is still on store shelves in the country where Ishi gets its other stuff, and its name, from. But it costs around 3,000 yen. -- Norman Diamond diamond@jrdv04.enet.dec-j.co.jp [Digital did not write this.] From ishius@ishius.com Tue Jan 10 21:41:17 1995 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 AA07607; Tue, 10 Jan 95 21:41:17 EST Received: from DialupEudora (ishius@localhost) by holonet.net (Anton Dovydaitis) with SMTP id SAA00316; Tue, 10 Jan 1995 18:38:02 -0800 Date: Tue, 10 Jan 1995 18:38:02 -0800 Message-Id: <199501110238.SAA00316@holonet.net> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" To: cube-lovers@life.ai.mit.edu From: ishius@ishius.com (ishius@holonet.net) Subject: Re: 5x5x5 cube >> I believe the poster is referring to the fact that the plastic faces fall >> off, revealing a screw inside, not the stickers (which are well done). Actually, I see both problems. But then, since I'm customer support, I see all the complaints. >> Super-glue solved my problem easily. Yes, but if WE do it, and spend labor on it, we have to increase the price to compensate. Originally we were selling these things for $30.00. What I'm saying is that these ARE a good value, but you should be careful. Remember: no one is manufacturing these things anymore, nor is anyone likely to in the future. If you know you'll want one, I'd buy it sooner rather than later, because there won't be no later. We bought up the last from the manufactuer, and there's fewer than 100 left. >> One more thing: the mechanism gets smoother after repeated use. That's good to know. I'll have to abuse mine some more. 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 BRYAN@wvnvm.wvnet.edu Tue Jan 10 23:43:25 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA19401; Tue, 10 Jan 95 23:43:25 EST Message-Id: <9501110443.AA19401@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 9498; Tue, 10 Jan 95 23:13:03 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 5520; Tue, 10 Jan 1995 23:13:03 -0500 X-Acknowledge-To: Date: Tue, 10 Jan 1995 23:13:02 EST From: "Jerry Bryan" To: Subject: Re: kociemba's algorithm for quarter turns In-Reply-To: Message of 01/11/95 at 00:09:40 from Dik.Winter@cwi.nl On 01/11/95 at 00:09:40 Dik.Winter@cwi.nl said: >Note the word *long*. There is a 20-turn sequence for superflip. I think we have a winner. I compared the data base for level 0 through 9 against the same data base superflipped, with no matches. That should mean that there is no 18-turn or less sequence for superflip. Adding in level 10 will take a bit longer. Also, there is some minor new programming involved in this particular effort. When I do get level 10 added in, and do get a match, that should be a complete validation of the new programming, and complete confirmation that the 20-turn sequence is minimal. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 mreid@ptc.com Wed Jan 11 09:56:20 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA12225; Wed, 11 Jan 95 09:56:20 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA28170; Wed, 11 Jan 95 09:54:58 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA19537; Wed, 11 Jan 1995 10:07:37 -0500 Date: Wed, 11 Jan 1995 10:07:37 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501111507.AA19537@ducie.ptc.com> To: bryan@wvnvm.wvnet.edu, cube-lovers@ai.mit.edu Subject: Re: kociemba's algorithm for quarter turns Content-Length: 570 jerry bryan writes > On 01/11/95 at 00:09:40 Dik.Winter@cwi.nl said: > > >Note the word *long*. There is a 20-turn sequence for superflip. > > I think we have a winner. I compared the data base for level 0 > through 9 against the same data base superflipped, with no > matches. That should mean that there is no 18-turn or less > sequence for superflip. wait a moment. dik is talking about face turns. what are you talking about? face turns or quarter turns? and if you're talking about face turns, there's no reason an odd length maneuver can't exist. mike From BRYAN@wvnvm.wvnet.edu Wed Jan 11 10:11:10 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA12605; Wed, 11 Jan 95 10:11:10 EST Message-Id: <9501111511.AA12605@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 1343; Wed, 11 Jan 95 10:03:57 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 4490; Wed, 11 Jan 1995 10:03:57 -0500 X-Acknowledge-To: Date: Wed, 11 Jan 1995 10:03:56 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: kociemba's algorithm for quarter turns In-Reply-To: Message of 01/11/95 at 10:07:37 from mreid@ptc.com On 01/11/95 at 10:07:37 mreid@ptc.com said: >jerry bryan writes >> On 01/11/95 at 00:09:40 Dik.Winter@cwi.nl said: >> >> >Note the word *long*. There is a 20-turn sequence for superflip. >> >> I think we have a winner. I compared the data base for level 0 >> through 9 against the same data base superflipped, with no >> matches. That should mean that there is no 18-turn or less >> sequence for superflip. >wait a moment. dik is talking about face turns. what are you >talking about? face turns or quarter turns? >and if you're talking about face turns, there's no reason an odd >length maneuver can't exist. I am talking about quarter turns. "Quarter turns" is in the subject of Dik's note???? If Dik's figures are for face turns, then Mike's 26q solution is still the best so far, and we have a long way to go. (Oops. I just peeked at Dik's 20 move solution. It is definitely for face turns. In fact, as a quarter turn solution, it is 28 quarter turns.) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 dik@cwi.nl Wed Jan 11 10:25:57 1995 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA13785; Wed, 11 Jan 95 10:25:57 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Wed, 11 Jan 1995 16:25:45 +0100 Received: by boring.cwi.nl id ; Wed, 11 Jan 1995 16:25:45 +0100 Date: Wed, 11 Jan 1995 16:25:45 +0100 From: Dik.Winter@cwi.nl Message-Id: <9501111525.AA11031=dik@boring.cwi.nl> To: BRYAN@wvnvm.wvnet.edu, cube-lovers@ai.mit.edu Subject: Re: kociemba's algorithm for quarter turns Yes, indeed my remark was about face turns (although the subject mentioned quarter turns). I ought to have modified the subject. dik From BRYAN@wvnvm.wvnet.edu Wed Jan 11 13:47:48 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA24849; Wed, 11 Jan 95 13:47:48 EST Message-Id: <9501111847.AA24849@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 2821; Wed, 11 Jan 95 13:40:35 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 1926; Wed, 11 Jan 1995 13:40:35 -0500 X-Acknowledge-To: Date: Wed, 11 Jan 1995 13:40:34 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: two stage filtration In-Reply-To: Message of 01/07/95 at 19:43:27 from mreid@ptc.com On 01/07/95 at 19:43:27 mreid@ptc.com said: >each configuration is stored with 2 bits of memory and thus the whole >space consumes about 42 megabytes. each configuration is assigned >one of 4 values: > distance is currently unknown > distance = current search depth > distance = current search depth - 1 > distance < current search depth - 1 This little table reminded me of something I had meant to say about storing the whole cube space in about 10^18 cells. In principle, under the Q turn metric it would be possible for each cell to contain only one bit by storing (depth mod 4)/2. However, in *building* the solution I think you would need a value in the cell meaning essentially "distance is currently unknown". Hence, you would need at least three separate values and therefore at least two bits. After the table were complete, it might be possible to reduce the two bits down to one. Even then, you might want to be able to identify those small percentage of cells which were empty, in which case you would need two bits anyway. Under the Q+H metric, you would need two bits in any case to store (depth mod 3), and the fourth bit pattern would be available to represent "distance is currently unknown" or "empty cell" as appropriate. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 Wed Jan 11 14:01:19 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA25989; Wed, 11 Jan 95 14:01:19 EST Message-Id: <9501111901.AA25989@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 2905; Wed, 11 Jan 95 13:53:57 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 2283; Wed, 11 Jan 1995 13:53:31 -0500 X-Acknowledge-To: Date: Wed, 11 Jan 1995 13:53:30 EST From: "Jerry Bryan" To: Subject: Re: Re: Cube with GAP In-Reply-To: Message of 01/08/95 at 13:47:00 from , Martin.Schoenert@Math.RWTH-Aachen.DE On 01/08/95 at 13:47:00 Martin Schoenert said: >Jerry Bryan wrote in his e-mail message of 1995/01/07 > Note that this model does not include the face centers. That is, it > is G[C,E] rather than G[C,E,F]. 56 numbers would be required to > include the face centers. The distinction between 48 facelets and > 56 facelets bears on the nitpicky question of whether the set C of > rotations is a subgroup of G or not. >Absolutely right. This part of the GAP documentation was written years >ago. These days I represent MG, CG, etc. as permutation groups on 54 >points. I also changed the numbering, so that the [1..24] represent the >edges, [25..48] points represent the edges, and [49..54] represent the >centers. Martin was kind enough not to point out that 6*9 is 54 rather than 56. > When I write the model out to disk, I only write out 8 corner facelets > and 12 edge facelets. For example, I only write out the front and > back corner facelets. This saves space and converts the model from > a facelet model to a cubie model, with the twists implicitly encoded > rather than being explicitly encoded via multiplication tables. It > also automatically establishes a frame of reference by which a > proof of conservation of twist and flip can be accomplished. >In terms of computational group theory this sequence of 8 corner and >12 edgde facelets is called a *base* for the permutation group G. >That is, each element of the group is uniquely determined by the >images of those 20 facelets. Of course if you have already proved >that no single corner can be twisted and no single edge can be flipped, >you can reduce this to 7 corner and 11 edge facelets. With some of my models it can be reduced slightly more. Since representative elements of equivalence classes are what are being stored, the representative element can be chosen to fix a cubie of your choice. The cubie which is being fixed need not be stored. This trick does not work, of course, if all cube positions are being stored rather than just representative elements. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 Wed Jan 11 16:21:44 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA03957; Wed, 11 Jan 95 16:21:44 EST Message-Id: <9501112121.AA03957@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 3326; Wed, 11 Jan 95 15:04:55 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 4406; Wed, 11 Jan 1995 15:04:54 -0500 X-Acknowledge-To: Date: Wed, 11 Jan 1995 15:04:43 EST From: "Jerry Bryan" To: Subject: When is 4x4x4 Solved in GAP? In-Reply-To: Message of 01/08/95 at 13:47:00 from , Martin.Schoenert@Math.RWTH-Aachen.DE On 01/08/95 at 13:47:00 Martin Schoenert said: >Mark Longridge wrote in his e-mail message of 1995/01/03 > ... I don't know how a normal 4x4x4 could > be represented though. >Jerry answered > I fail to see the problem. Just number the facelets. The only > problem would then lie in deciding what the generators are -- i.e., > which kind of slice moves do you accept. You would also have to > decide whether to model the invisible 2x2x2 inside, but again if you > did, just number the invisible facelets and include their movements > with your generators. >The problem is that many different positions all look solved. For >example, you can permute the 4 center facelets of one face or exchange >two adjacent edges, and the cube still looks solved (of course you cannot >do all this independently). So if we take the obvious permutation group >on the 6*16 points, then a whole subgroup would correspond to what a >puzzler would consider solved states. If by a model we mean a group >whose elements correspond to the different states a puzzler would see, >and whose identity corresponds to what a puzzler would consider solved, >then I have no good idea how to model the 4x4x4 cube as a permutation >group. Start by numbering all the facelets and defining your generators (about which there might be some controversy), and call the resulting group G. Decide which permutations you consider equivalent and call this set K. K would probably include such things as the whole cube rotations C, as well invisible permutations of the four center facelets, etc. In most reasonable choices for K, K would certainly be a group. Your model then becomes the set of cosets G/K (which is *not* a factor group! I am learning.). The questions then become: 1) can you define an operation on the cosets G/K such that G/K is a group, and 2) can you find a mapping from G/K onto a subgroup of G such that the mapping respects costs? If the answer to both questions is "yes", then it is this subgroup of G which you would want to put into GAP. By the way, I am sensitive to the distinction between G and CG, but in the case of any Face centerless cube such as 2x2x2 or 4x4x4, it would seem to me that the distinction is less important than in cubes with Face centers such as 3x3x3 and 5x5x5. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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 mreid@ptc.com Thu Jan 12 19:36:23 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA23412; Thu, 12 Jan 95 19:36:23 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA08082; Thu, 12 Jan 95 19:34:56 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA25588; Thu, 12 Jan 1995 19:47:42 -0500 Date: Thu, 12 Jan 1995 19:47:42 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501130047.AA25588@ducie.ptc.com> To: cube-lovers@ai.mit.edu Subject: superflip Content-Length: 1768 i've also done some searching for short maneuvers for superflip, although not to the extent that dik has. i was never really satisfied with my efforts to exploit its symmetry and centrality. however, i've recently had some new thoughts about this which look promising. consider two cases: case 1: suppose that there is a minimal sequence for superflip which contains a half-turn. then, by applying R' U2 to superflip, we've moved 3q (or 2f ) closer to start. case 2: otherwise, every minimal sequence contains only 90 degree turns. then either R' U' gets us 2q (or 2f ) closer to start, or R' U gets us 2q (or 2f ) closer to start. (and probably both do.) it would be nice to reduce this latter case to only one of R' U' or R' U . can anyone do this? this was how i found the 24q sequence for superflip. i figured that case 1 was fairly likely, so i tested the position superflip R' U2 kociemba's algorithm found in succession 11 + 22 = 33q, 11 + 20 = 31q, 12 + 17 = 29q, 13 + 14 = 27q, 13 + 12 = 25q, which gives superflip in 28q. there was no improvement for quite some time until depth 17 in stage 1 when it found 17 + 6 = 23q. it searched for several days more and finished depth 17 and depth 18 in stage 1. i was about to give up when i saw that it found 19 + 2 = 21q, to give superflip in 24q. here's a nice (and quite surprising application) of the above use of symmetry and centrality: when searching for superflip in the face turn metric, it's sufficient to search through depth 17 in stage 1! suppose we have a 19f sequence for superflip. then, by considering parity, some turn must be a half-turn. now we may suppose (as above) that the last two face turns are U R2 , which is in stage 2! mike From dik@cwi.nl Thu Jan 12 20:35:59 1995 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA26027; Thu, 12 Jan 95 20:35:59 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Fri, 13 Jan 1995 02:35:45 +0100 Received: by boring.cwi.nl id ; Fri, 13 Jan 1995 02:35:45 +0100 Date: Fri, 13 Jan 1995 02:35:45 +0100 From: Dik.Winter@cwi.nl Message-Id: <9501130135.AA14054=dik@boring.cwi.nl> To: cube-lovers@ai.mit.edu, mreid@ptc.com Subject: Re: superflip > i've also done some searching for short maneuvers for superflip, > although not to the extent that dik has. i was never really > satisfied with my efforts to exploit its symmetry and centrality. > however, i've recently had some new thoughts about this which > look promising. I have indeed considered this, but have not yet come to a conclusion. > case 1: > suppose that there is a minimal sequence for superflip which > contains a half-turn. then, by applying R' U2 to superflip, > we've moved 3q (or 2f ) closer to start. I do not know whether this is clear for all readers. My reasoning was similar but the conclusion different, but someway equivalent: If the minimal sequence contains a half-turn, we may just as well assume that that half turn is the last, and F2. I do not know whether the proof has been shown on this list, but it is simple. Suppose M is a minimal sequence, and Z is some random sequence, in that case Z M Z' is also superflip. Take Z the maximal sequence at the end consisting of quarter-turns only, we end with a sequence of equal length terminating with a half-turn. Because of symmetry we may just as well consider it to be F2. > case 2: > otherwise, every minimal sequence contains only 90 degree turns. > then either R' U' gets us 2q (or 2f ) closer to start, > or R' U gets us 2q (or 2f ) closer to start. (and probably > both do.) > it would be nice to reduce this latter case to only one of R' U' > or R' U . can anyone do this? This needs more than simple symmetry. There are 12*8 different endings, and we have 48 symmetries (24 by rotation * 2 by inversion). Leaving 2 cases. I considered this, but have not yet come to conclusions. On the other hand I do not yet know what to conclude from M M' = I for every superflip sequence. > when searching for superflip in the face turn metric, it's > sufficient to search through depth 17 in stage 1! > suppose we have a 19f sequence for superflip. then, by considering > parity, some turn must be a half-turn. now we may suppose (as above) > that the last two face turns are U R2 , which is in stage 2! Yes, I had seen that. One of the major reasons I was not amused when the system crashed doing depth 17 in stage 1! I will restart the program doing depth 17, but I will first redo the counting so that counts larger than 2^32 are correct. dik From BRYAN@wvnvm.wvnet.edu Thu Jan 12 21:14:10 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA27432; Thu, 12 Jan 95 21:14:10 EST Message-Id: <9501130214.AA27432@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 1639; Thu, 12 Jan 95 21:13:36 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 0846; Thu, 12 Jan 1995 21:13:36 -0500 X-Acknowledge-To: Date: Thu, 12 Jan 1995 21:13:35 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: superflip In-Reply-To: Message of 01/12/95 at 19:47:42 from mreid@ptc.com Another thought. It would seem to me that under either metric, the position halfway through ought to be "symmetric". I am not sure just what "symmetric" means here, and my use of the word is largely arm waving similar to the use of "symmetric" to describe local maxima prior to "Symmetry and Local Maxima". But if such a "symmetric" position could be identified, it should be quite easy to search from it back to Start or back to Superflip in a minimal number of moves. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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