0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Is the idea is to take that natural number mod $n$ and look it up in a hash table? If so it may be more efficient to generate the hash directly without actually computing a unique number corresponding to the state. $\endgroup$ Jun 6, 2017 at 3:06
  • $\begingroup$ Also, isn't there a sense in which the state already is a natural number, however you have implemented it? As long as the state is a sequence of bits, that is a unique number in binary. $\endgroup$ Jun 6, 2017 at 3:08
  • $\begingroup$ Yes, i think this question is better for Stack Overflow. There are dozens of algorithms and programs already done for rubik, for solving it optimally. Though we could suggest, nothing in here would talk correctly to be software efficient. $\endgroup$
    – Brethlosze
    Jun 6, 2017 at 3:10

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .