Cube coordinates

In this page I describe the way I implemented coordinates, in the sense of Cube Explorer, in one of the versions of Nissy.

Unfortunately, this implementation got lost between rewrites and is currently not included in any working version of Nissy or other projects, so it this page is of theoretical interest only. Some code is available in the nissy-nx repository, but it is currently broken (what is described in this page works, though).

What are cube coordinates?

A cube coordinate is a way of associating to any legal position of the Rubik’s cube an integer in a certain range [0..n-1]. For example, any way of encoding the permutation of the corners as a number from 0 to 8!-1 is a valid coordinate; another example is an encoding of the orientation of the edges with respect to a given axis as a number in [0..2^11].

In other words, a coordinate is a function from the set of legal configurations to [0..n-1]. Coordinates need not be surjective, though it is more convenient if they are, and in my examples they will be.

To work with cube coordinates, we need to implement the following:

An integer n, the maximum value of a coordinate +1.
A function index() that takes a cube as input and returns an integer in the range [0..n-1] as output.
A function to_cube() that takes an integer in [0..n-1] as input and returns a cube c such that index(to_cube(x)) == x for every x in [0..n-1]. In other words, to_cube() is a section of index(). In practice, it is not necessary that the output of to_cube() is a valid cube object.
A function move() that takes as input a coordinate, a move m and an integer x in [0..n-1] and returns an integer y in [0..n-1] such that y == index(m(to_cube(x))) (here m(c) is the cube c moved by m).
If applicable, a transform() function that applies a transformation in a similar way as move() applies a move. For coordinates this is not possible, because they do not capture enough of the cube state. For some coordinates, only some transformations are possible. For example, for the edge orientation coordinate only the transformations that fix the axis with respect to which the edge orientation is defined can be applied.

For the implementation, see coord.c and coord.h, as well as the definition of coordinate in cubetypes.h.

Coordinate types

In my work I have defined four types of coordinates (but I actually use only three of them).

Basic coordinates

Basic coordinates are the simplest kind, and they are completely defined by the integer n and the functions index() and to_cube() defined above. This is the type of coordinate that “does not exist” in the code, because they are just a special case of composite coordinates.

Composite coordinates (COMP_COORD)

Composite coordinates are, like the name says, a composition of many basic coordinates. They are given by a list of basic coordinates (n_1, index_1(), to_cube_1()), …, (n_k, index_k(), to_cube_k()). The value of such a composite coordinate on cube c is computed as index_1(c) + n_1 * (index_2(c) + n_2 * (...)).

Symmetric coordinates (SYM_COORD)

A symmetric coordinate consists of a basic coordinate reduced by symmetry. Symmetric coordinates must be initialized from a given set of cube transformations before they can be used. The initialization step produces the following data:

A table that associates every possible value of the basic coordinate with its class in the symmetric coordinate. Computing the value of the symmetric coordinate will then amount to computing the basic coordinate via index() and looking up the value in this table.
A table that associates every possible value of the basic coordinate with a fixed representative for its class.
A table that associates every possible value of the basic coordinate the cube transformation that brings it to its representative.
A table that associates every possible value of the basic coordinate with the list of cube transformations that do not affect it, that is a list of self-symmetries. This will be useful when computing the pruning table associated to this coordinate.

Symmetric-composite coordinates (SYMCOMP_COORD)

A symmetric-composite coordinate is based on two other coordinates, a symmetric coordinate and a composite coordinate. To compute the value of a symmetric-composite coordinate one must compute the symmetric coordinate value first, then transform the cube using the transformation that brings the basic coordinate associated to the symmetric coordinate to its representative in order to compute the correct value for the composite coordinate, and finally combine the two.

More precisely and with less tong-twisting, for a given cube c one must take the following steps:

Compute the value x_s of the symmetric coordinate at c, the value x_b of the basic coordinate associated with the symmetric coordinate and the value x_c of the composite coordinate.
Read from the table the transformation t that brings x_b to its representative.
Apply t to the composite coordinate value x_c to obtain x_t.
Compute the value x_s * n_c + x_t, where n_c is the maximum value +1 of the composite coordinate.

Moving coordinates

A move is applied to a coordinate by lookup into a transition table, pretty much as explained in Jaap’s computer puzzling page. These transition tables are initialized once and for all at the beginning, and in my implementation I actually saved them to a file to speed up subsequent runs.

Some extra care has to be taken in dealing with symmetries.

Basic and composite coordinates

This case is quite simple: the transition table with something along these lines:

for i in [0..n-1]
    for m in Moves
        move_table[m][i] = index(m(to_cube(i)))

Symmetric coordinates

As mentioned above, this case and the next are tricky, because we need to keep track of which transformation has to be applied to get from the representative of the symmetry class to our actual cube.

You can imagine a move applied to symmetric coordinate as if we just move between different representatives. The actual cube can be recovered from this by keeping track of an offset transformation, and updating it after every move.

The necessary tables can be generated with something like this:

for i in [0..n-1]
    for m in Moves
        j = m(rep of i) /* Apply as basic coordinate */
        move_table[m][i] = class of j
        offset_table[m][i] = transformation bringing j to its rep

Symmetric-composite coordinates

A symmetric-composite coordinate requires some extra work, but the hard part is already handled by its base symmetric coordinate.

To move a symmetric-composite coordinate, first we recover the value s of its symmetric coordinate’s and the value c of its composite coordinate by taking the quotient and the remainder of division by the maximum value of the composite coordinate.

Then we apply the move to the values s and c using their respective transition tables. The offset transformation is taken from the symmetric coordinate, and apply it to the result of the move on the composite coordinate.

This may be summarized with the following pseudo-code:

s = ind / M /* M is the maximum value +1 of the composite coordinate */
c = ind % M
new_s = move_table_s[m][s] /* Using the table for the symmetric coordinate */
new_c = move_table_c[m][c] /* Using the table for the composite coordinate */
offset = offset_table[m][s]
new_c = offset(new_c) /* See next section for transformations */

return (new_s * M + new_c, offset)

Transforming coordinates

When we talk about cube transformations, we are talking about conjugating a cube by a rotation, possibly combined with a mirroring along a fixed axis. More precisely, transforming a cube c is done with the following steps:

Start from a solved cube
(optional) Mirror it left-right
Apply the required rotation
Apply c (as a permutation / move sequence) to the rotated solved cube
Apply the inverse of the rotation
(optional) Mirror it left-right

When working with coordinates, transformations are applied pretty much in the same way as moves, using a transition table. This time, though, symmetric coordinates are much less of a problem: any transformation on a symmetric coordinate is, by definition, trivial! Of course, this is only true if we limit ourselves to applying transformations that are part of the set used to “reduce” the symmetric coordinate; but we always do this anyway.

Pruning tables

I’d like to mention pruning tables here, because their computation is quite straightforward when using coordinates.

Say you want to compute a table that associates every possible value i in [0..n-1] of a coordinate with the minimum amount of moves required to solve any cube c such that index(c) == i. For the purpose of this page we assume one can afford to allocate enough bits so that the actual value can be stored.

With coordinates, one can do the following, without ever going back to the full cube representation:

set all values of the pruning table to infinity
set the value associated with the solved cube to 0
for d in [1..20]
    for i in [0..n-1]
        if pruning_table[i] == d-1
            for m in Moves
                old = pruning_table[m(i)]
                pruning_table[m(i)] = min(d, old)

This is conceptually very simple, but unfortunately it is not enough. Because of self-symmetries, not every position will be reached in this way for a symmetric-composite coordinate: there may be more ways to bring the base of the symmetric coordinate to its representative, each having a different effect on the composite coordinate, but we only pick one of them when building the move tables.

Luckily, this can be solved because we have memorized for every position a list of all the transformations that keep it invariant (see above). Then it is enough to add the following loop at the end of every iteration of the outermost loop above:

    for i in [0..n-1]
        for t in the set of self-symmetries of i/M
            old = pruning_table[t(i)]
            pruning_table[t(i)] = min(d, old)

The code for this can be found in pruning.c. The use of pthread made it more complicated, so it can be hard to follow without reading this page first.

Why using coordinates?

Coordinates are necessary to compute pruning tables, which are fundamental when solving a cube using the methods described in Jaap’s computer puzzling page.

However, using transition tables for moves and transformations is not necessary. It used to be an efficient way to perform moves on a cube, but with newer hardware the trade-offs between memory access and instruction execution are changing.

One thing that is made particularly cumbersome by using coordinates instead of a full representation of the cube is computing the inverse. While it is possible to compute the inverse somewhat efficiently from a representation of the cube made of a smart selection of coordinate values, it is not necessarily efficient. See fst.c for an implementation.

For these reasons, I am not using the coordinate approach described here for my new work-in-progress solver (temporarily named h48).