The Move Tables

If you apply one of the 18 possible faceturns (a "move") to the cube, the permutation of the corners and edges change. On the coordinate level, a move maps a coordinate to another coordinate.

This mapping is possible, because we can show that if we apply a move M onto two different permutations a and b with the same coordinate x, both results have the same coordinate x'. If a and b have the same coordinate x, and H is the subgroup defining the cosets for this coordinate, there exist a permutation g from the cube group G so that a and b are elements of H*g (remember that we use right cosets). Then a*M and b*M are of course elements from [H*g]*M = H*[g*M] and hence are in the same coset and have the same coordinate x'.

Move tables are twodimensional arrays which describe how this mapping is done. We distinguish between move tables for "simple" raw-coordinates and movetables for sym-coordinates, which are reduced by symmetries.

Move tables for raw-coordinates

All move tables for raw-coordinates have the same structure. Let us take for example the move table for the corner orientation coordinate:

TwistMove: array[0..2187-1,Ux1..Bx3] of Word;

If you apply for example the move R2, TwistMove[oldCoordinate,Rx2] gives the new coordinate. This is done pretty fast compared with doing a permutation on the cubie level or the on the facelet level.

Here is the documented code from CordCube.pas to generate this move table:

procedure CreateTwistMoveTable;
var c: CubieCube; i,k: Integer; j: TurnAxis;
begin
  c:= CubieCube.Create;//create a cube c on the cubie level
  for i:=0 to 2187-1 do
  begin
    c.InvCornOriCoord(i);//generate a permutation with corner orientation i
    for j:= U to B do
    begin
      for k:= 0 to 3 do //k=3 restores the original state
      begin
        c.Move(j);//apply all 18 face turns on c
        if k<>3 then TwistMove[i,Move(3*Ord(j)+k)]:=c.CornOriCoord;//save result in the array
      end;
    end;
  end;
  c.Free;
end;

Move tables for sym-coordinates

If we reduce a coordinate by symmetries, we only generate a move table for the representants of the equivalence classes. Let R(j) be a permutation belonging to the representant of the equivalence class with index j.

When we apply a move M on this representant, the result will be in another equivalence class k, so that there is a symmetry S(i) with R(j)*M = S(i)-1*R(k)*S(i). Then the resulting movetable entry is the corresponding sym-coordinate, that is MoveTable[ j,M ]:= 16*k + i .

Here is an example for the FlipUDSlice move table from cordcube.pas (all unimportant parts removed):

procedure CreateFlipUDSliceMoveTable;
var c: CubieCube; i,k,n: Integer; j: TurnAxis;
begin
  SetLength(FlipSliceMove,64430,18); //18 different faceturns
  c:= CubieCube.Create;
  for i:=0 to 64430-1 do //iterate over all equivalence classes
  begin
    n:= FlipUDSliceToRawFlipUDSlice[i]; //get the raw-coordinate of the representant
    c.InvUDSliceCoord(n div 2048); //and generate a permutation which has this FlipUDslice coordinate
    c.InvEdgeOriCoord(n mod 2048);
    for j:= U to B do
    begin
      for k:= 0 to 3 do
      begin
        c.Move(j); //apply all 18 faceturns
        if k<>3 then FlipSliceMove[i,3*Ord(j)+k]:= c.FlipUDSliceCoord; //the sym-coordinate
      end;
    end;
  end;
end;

The procedure to find the sym-coordinate for a given permutation P is not really difficult but a bit more complicated than the computation of the raw-coordinates. We only need this procedure in the initialization phase where we have to calculate the coordinates of the cube we want to solve.

For 0<=i<16 we apply S(i)*P*S(i)-1 and compute the raw-coordinate until we find the raw-coordinate in the ClassIndexToRepresentantArray at some position k. Let us denote this coordinate with R(k).

S(i)*P*S(i)-1 = R(k) is equivalent to S(i)-1*R(k)*S(i) = P, and this means P has the sym-coordinate 16*k + i.

Look at the function CubieCube.FlipUDSliceCoord in cubicube.pas for an example.

Applying a move also is more complicated for sym-coordinates compared to raw-coordinates, because we only have built a movetable for the representants of the equivalence classes. But the advantage of using sym-coordinates - reducing the big tables by a factor of about 16 - is much higher than the disadvantage due to the increased complexity.

If we have the sym-coordinate x, we can extract from this coordinate the index j of the equivalence class and the index i of the symmetry. For a move M we have, using the associativity of the permutation group and denoting the representant of the equivalence class with R(j):

[S(i)-1*R(j) *S(i)]*M = [S(i)-1*R(j)*S(i)]*M*[S(i)-1*S(i)] = [S(i)-1*R(j)]*[S(i)*M*S(i)-1]*S(i)

[S(i)*M*S(i)-1] is the conjugation of a move by a symmetry which is another move. In symmetry.pas the array SymMove[SymIdx,Move] is initialized, so that SymMove[i,M] gives the desired result. Let us denote the result by M1.

So we have to compute

[S(i)-1*R(j)]* M1*S(i) = S(i)-1*[R(j)* M1]*S(i)

The sym-coordinate y for [R(j)* M1] can be read off from MoveTable[j, M1]. From y we then extract the class index j1 and the symmetry index i1. That means [R(j)*M1] = S( i1)-1*R(j1)*S( i1).

So we have

S(i)-1*[R(j)* M1]*S(i) = S(i)-1*[ S( i1)-1*R(j1)*S( i1)]*S(i) = [S(i)-1*S( i1)-1]*R(j1)*[S( i1)*S(i)]

and because [S(i)-1*S( i1)-1] = [S( i1)*S(i)]-1 we can write this as

[S( i1)*S(i)]-1*R(j1)*[S( i1*S(i)].

[S( i1)*S(i)] is the product of two symmetries, which is another symmetry S(i2). The array SymMult[SymIdx,SymIdx] - created in symmetries.pas - does this computation. Let us denote SymMult[i1,i] with i2. So our result is

S(i2)-1*R(j1)*S( i2) and the corresponding sym-coordinate is 16*j1+ i2.

So in comparison with the movetables for raw-coordinates where we only need one table-lookup we now need three table-lookups in the tables SymMove, MoveTable and SymMult.