The Coordinate Level

On the coordinate level we describe the permutations and the orientations of the corners and edges by natural numbers. This level of abstraction is especially suited to implement a fast algorithm to solve the cube.

The definition of the corner orientation coordinate

If we apply for example the move R to a clean cube we get

The orientation of the 8 corners are described by a number from 0 to 2186 (3^7 - 1).

In cubicube.pas you find the following definition

function CubieCube.CornOriCoord:Word;
var co: Corner; s: Word;
begin
  s:=0;
  for co:= URF to Pred(DRB) do s:= 3*s + PCorn^[co].o;
  Result:= s;
end;

In the example above this functions computes

2*3^6 + 0*3^5 + 0*3^4 + 1*3^3 +1*3^2 + 0*3^1 + 0*3^0 = 1494

This is just the number 2001100 in a ternary number system.

To make this easy method work we must write the permutation in the in the is replaced by representation. It will not work in the is carried to representation!

We ignore the orientation of the DRB-corner, because this orientation is determined by the orientations of the other seven corners: The sum of all orientations must be divisible by three.

The definition of the edge orientation coordinate

The edge orientation coordinate is defined in an analogous way.

The orientation of the 12 edges is described by a number from 0 to 2047 (2^11 - 1).

In cubicube.pas you find the following definition

function CubieCube.EdgeOriCoord:Word;
var ed: Edge; s: Word;
begin
  s:=0;
  for ed:= UR to Pred(BR) do s:= 2*s + PEdge^[ed].o;
  Result:= s;
end;

We use the binary number system instead of the ternary number system here. We ignore the orientation of the BR-edge because it is determined by the orientations of the other 11 edges. The sum of all orientations must be even.

The definition of the corner permutation coordinate

The corner permutation coordinate is given by a number from 0 to 40319 (8! - 1).

In this example, we use the permutation of the R-move again, but we ignore the orientations now.

We define a natural order on the corners by URF<UFL<ULB<UBR<DFR<DLF<DBL<DRB.

The number in the third row - below a corner XXX in the second row - gives the number of all corners left of XXX, whose orders are higher than the order of XXX.

Above the entry 4 we have for example the corner UBR.
From the 7 corners left of UBR, 4 corners have a higher order - DFR, DLF, DBL, DRB.

Above the entry 1 we have for example the corner DLF.
From the 5 corners left of DLF, only 1 corner has a higher order - DRB.

We build the permutation coordinate with the numbers of the third row.

1*1! + 1*2! + 3*3! + 0*4! + 1*5! + 1*6! + 4*7! = 21021

So we use a system with variable base here.

The following function from cubicube.pas does the job.

function CubieCube.CornPermCoord: Word;
var i,j: Corner; x,s: Integer;
begin
  x:= 0;
  for i:= DRB downto Succ(URF) do
  begin
    s:=0;
    for j:= Pred(i) downto URF do
    begin
      if PCorn^[j].c>PCorn^[i].c then Inc(s);
    end;
    x:= (x+s)*Ord(i);
  end;
  Result:=x;
end;

The definition of the edge permutation coordinate

The edge permutation coordinate is described in an analogous way by a number from 0 to 12! - 1.

We use the following function from cubicube.pas:

function CubieCube.EdgePermCoord: Integer;
var i,j: Edge; x,s: Integer;
begin
  x:= 0;
  for i:= BR downto Succ(UR) do
  begin
  s:=0;
  for j:= Pred(i) downto UR do
  begin
    if PEdge^[j].e>PEdge^[i].e then Inc(s);
  end;
  x:= (x+s)*Ord(i);
  end;
  Result:=x;
end

Now we are able to describe each cube with a tuple (x1,x2,x3,x4) and

0 <= x1 < 3^7,   0 <= x2< 2^11,   0 <= x3< 8!,   0 <= x4< 12!

Only half of these cubes are really possible to generate because all achievable permutations are even and so we have only 12! * 8! /2 permutations (ignoring the orientations).

The number of different cubes is therefore given by

3^7 * 2^11 * 8! *12! /2 = 43.252.003.274.489.856.000

There are some other coordinates we use for the Two-Phase-Algorithm which we introduce later.