Mapping a Rubik's Cube state to a unique natural number

Question

I am writing an implementation of Kociemba's algorithm, and I am trying to generate pruning tables. However, this requires converting the state of the Rubik's Cube to a natural number that can be created quickly. I have access to the orientation and positions of the corners and edges of the cube, so I think that it is possible to map each possible state to a unique number. However, I cannot figure out how, and I figured that this question is more about the math of the cube than the coding of the algorithm, but let me know if you think I should move it to stack overflow. Thank you in advance for your help.

Answer 1

If you just need an identifier for each state, prime numbers are your friend. Assign a number from $0$ to $5$ to each color. Start from the upper left front cubie and assign a prime to each color square. A natural thing is to assign $2$ to the top face, $3$ to the front face and $5$ to the left face. You can represent this cubie by $2^a3^b5^c$ where $a$ is the color on top, $b$ is the color on the front, and $c$ is the color on the left. Assign different primes to each location. Raise each to the power of the color at that location. Multiply the values for each location and you have a unique number for each cube configuration. You can take a standard position for the center cubies, so ignore them.

This works. Each number has only one configuration of the cube. It ignores the ease of writing an algorithm that takes a given configuration of the cube, does one rotation, and returns the new configuration of the cube. It also uses a lot of bits, though bits are cheap, because the highest prime you will use is $223$ and powers of that are big. It would probably be better to represent a cube configuration by a string of $48$ numbers from $0$ to $5$ where you just list the locations aside from the centers and the numbers are the color at that location. Now a quarter turn of the right slice is just a permutation of the string. If you are worried about storage each number is only three bits so a cube configuration is $144$ bits. You have to pack and unpack them, so it would be time efficient but space inefficient to make your strings ASCII. A state is then $48$ bytes instead of $16$ but processing them is much easier.

Answer 2

I would try an approach using permutations. First, work on corner, edge and center face cubies separately. So, for example, the eight corner cubies are permuted. There are standard ways of ranking of permutations, so use one of them. For edge cubies do something similar. Finally, for center face cubies, the same thing. You will probably want to include rotations of cubies (order three for corners, order two for edges), in an ordered list, using $\{0,1,2\}$ or $\{0,1\}$, respectively for elements. Combine all these together by a standard ranking of Cartesian products of ranked sets.