From BRYAN@wvnvm.wvnet.edu Sat Jan 21 17:03:15 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA05451; Sat, 21 Jan 95 17:03:15 EST Message-Id: <9501212203.AA05451@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 3609; Sat, 21 Jan 95 12:46:20 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 3611; Sat, 21 Jan 1995 12:46:20 -0500 X-Acknowledge-To: Date: Sat, 21 Jan 1995 12:44:42 EST From: "Jerry Bryan" To: "der Mouse" Cc: "Cube Lovers List" Subject: Re: superflip in quarter turn metric In-Reply-To: Message of 01/21/95 at 09:05:55 from , mouse@Collatz.McRCIM.McGill.EDU On 01/21/95 at 09:05:55 der Mouse said: >> The superflip is especially amenable to a "two half depth search". >> Normally, you would have to build one tree with Start at the root, >> and a second tree with X at the root, where X is the position you >> were testing. But a search tree with superflip at the root is >> identical to a search tree with Start at the root except that the >> superflip tree has each element superflipped as compared to the >> respective element of the tree with Start at the root. >Isn't this equally true of any other position, except that the >conversion from a Start-rooted tree's position to an X-rooted tree's >position is more complicated than just superflipping? Just think of >your tree, instead of describing positions as "cubie in cubicle >", as describing positions as "cubie that started in cubicle in >cubicle ". I am taking the liberty of CC'ing Cube-Lovers as well. A search tree giving distances from Start calculates d(I,IY) for all positions IY in the domain of inquiry. With an X-rooted tree, distances are of the form d(X,XZ) for all positions XZ in the domain of inquiry. In general, it is not the case that d(I,IY)=d(X,XY). Hence, we cannot simply take Z=Y, and elements of the form XY do not produce the X-rooted tree. Therefore, to perform two half-depth searches to connect I and X, you really do have to construct a standard Start-rooted tree as well as an X-rooted tree. You are looking for a position IY=XZ such that |IY|=|XZ|=|X|/2. However, in the case of the Superflip E, it is the case that d(I,IY)=d(E,EY). Hence, in order to construct an E-rooted tree, it is sufficient to calculate all elements of the form EY from your existing I-rooted tree of the form IY. >Or are you storing only M-conjugate-class representatives, and I'm >exposing my ignorance of basic group theory? :-) Yes, I am storing only M-conjugate-class representatives, but that isn't the problem (see above). However, it does make the processing a bit less trivial than I have indicated. For every Y in the Start-rooted tree, I first form EY, then {m'(EY)m}, and finally Repr{m'(EY)m}. These representatives are sorted and then compared against all the Y's (which are themselves representative elements, of course). We are looking for some V and W such that Repr{m'(IV)m}=Repr{m'(EW)m}, and this will be a "half-way" position. What I *really* want is some V such that Repr{m'(IV)m}=Repr{m'(EV)m}. It seems to me that all half way positions should be "symmetric" in this fashion, but I cannot prove it. The recent discussions by Mike Reid and Mark Longridge about the 24q superflips are suggestive in this regard. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU