From cube-lovers-errors@mc.lcs.mit.edu Thu Dec 17 14:01:55 1998 Return-Path: Received: from sun28.aic.nrl.navy.mil (sun28.aic.nrl.navy.mil [132.250.84.38]) by mc.lcs.mit.edu (8.9.1a/8.9.1-mod) with SMTP id OAA21297 for ; Thu, 17 Dec 1998 14:01:50 -0500 (EST) Precedence: bulk Errors-To: cube-lovers-errors@mc.lcs.mit.edu Date: Thu, 17 Dec 1998 09:32:42 -0500 (Eastern Standard Time) From: Jerry Bryan Subject: Re : Optimal Cube Solver In-Reply-To: <366C1ED9.C11@hrz1.hrz.tu-darmstadt.de> To: kociemba@hrz1.hrz.tu-darmstadt.de Cc: Cube Lovers Message-Id: On Mon, 07 Dec 1998 19:30:49 +0100 Herbert Kociemba wrote: > > The third coordinate describes the edge permutation. Because there are > 12! coordinate values, even reduction by 48 symmetries still gives too > many coordinate values. So for use in a turntable we define two edge > permutations a and b equivalent, if a=m1*b*m2, were m1 and m2 are in M. > In this way we get 208816 equivalence classes c. If now m1*c*m2 is a > (not necessarily unique) representation of an edge permutation applying > a faceturn T is done like that: > > (m1*c*m2)*T = m1*c*[m2*T*m2^-1]*m2 = m1*[c*T']*m2= > [m1*m1']*c'*[m2'*m2]=m1''*c'*m2'' > This is remindful of a technique I used many years ago to reduce the size of the search space for the 2x2x2 problem, and the issue would apply to any cube such as the 4x4x4 with an even number of cubies per edge. That is, in the (2n)x(2n)x(2n) problem you can treat as equivalent any positions of the form (m1)*x*(m2) for m1 and m2 in M, provided only that both of m1 and m2 are rotations or that both of m1 and m2 are reflections. Another (and in some ways better) way to model a (2n)x(2n)x(2n) problem and to reduce the size of the search space is to fix one of the corners and to use the symmetry group which preserves the major diagonal axis which includes the corner which is fixed, but that is a different issue. Dan Hoey showed that (m1)*x*(m2) is equivalent to m'xmc for suitable choices of m and c, for m in M and for c in C (the set of 24 rotations). Requiring that m1 and m2 both be rotations or both be reflections is necessary because you really can't turn the corners inside out on a physical cube. Herbert does not impose the same restriction on both of m1 and m2 being rotations or reflections because his third coordinate applies only to the edges, and the edges can indeed be turned inside out on a physical cube, namely with the Pons Asinorum maneuver. So for this case, (m1)*x*(m2) is equivalent to m'xmc if m1 and m2 are both rotations or both reflections, and is equivalent to m'xmcv if they are not, where v is the central inversion of the edges (essentially, the Pons Asinorum applied to the edges). I used to talk about 1152-fold symmetry for the 2x2x2 (1152=24*48). Herbert's approach for the third coordinate yields a 2304-fold reduction in the search space (2304=48*48). However, the reductions in the search space in the two cases are not really dealing with quite the same issue. In the case of 1152-fold symmetry for the 2x2x2, there are (up to) 1152 equivalent positions which are the same distance from Start. If I am understanding Herbert's technique correctly, when positions are equivalent in the third coordinate, there are (up to) 2304 positions of the edges for which the distance from Start has the same lower bound. (Maybe I should say "the same non-trivial lower bound", because (for example) zero would be a lower bound for all positions.) ---------------------------------------- Jerry Bryan jbryan@pstcc.cc.tn.us Pellissippi State Technical Community College