The laws of nature are but the mathematical thoughts of God. 
-- Euclid

God's Algorithm & God's Number

You may wonder why the title is like that, because you remember what I promised yesterday: introducing the data structure for Rubik's Cube. Sure. My goal hasn't changed over night, but I need a cool term (or two cool terms) to break the ice.

OK. Seriously, there are so many candidates, but which to choose? For instance, in this thread on stack overflow, there are at least 13 ways to store the states of a Rubik's Cube. It is a puzzle too well-known, so I guess that's the reason why a simple go-to data structure does not exist.
It is actually fun to see how people model Rubiks' Cube: alphabetic approach, 3D array, hybrid method, etc.

My choice is, instead of choosing a simple data structure randomly from a stack overflow thread, I want something representative. It would be ideal if there is a bulletproof Rubik's Cube software, it has accomplished some result in practice, and the data structure it uses is understandable. Luckily, a best fit exists, from a group of clever people who seek the God's Number. They implemented God's Algorithm as a ... software (they didn't gave it a name as cool as the intention, what a shame).

Why bother going into the details when the links give you concise descriptions? Still TL;DR: God's number (For 3x3x3) is 20 because all valid states of a standard Rubik's Cube can be solved in at most 20 twists; God's algorithm is the method, or a set of methods, to calculate optimal solutions for all valid states.

Cubeops

Anyway, the implemented class was named cubeops, and it has great documentation. One of our main interests in this series is hypercube 2x2x2x2, so here I just focus on how Cubeops deal with corners, because a 2x2x2 cube is equivalent to a cornor-only 3x3x3.

Let me quote some of the important paragraph from the document:

In short,

• There are 8 corner "slots"
• Each corner cubie can have 3 possible orientations at each slot
• So, each cubie has 24 states

The numbering of the 8 corner cubies looks straightforward, but it is fun to see the embedded gray code. Not necessary to go into the details.

Some of the definition remains unclear. What does the 3 different orientations represented? It is a part of the "twist convention", where 0 means no twist; 1 means clockwise twist; 2 means counterclockwise twist. It is still confusing. Says cubie 0 (it belongs to slot 0 when solved) is currently at the diagnol place, slot 7, which of its 3 possible orientatins is no twist? which is counterclockwise twist?

To find out the answers, we have to go further. In the below paragraph:

OK then. From these definitions, Cubeops then generates tables for all 6 kinds of moves (L/R/U/D/F/B). The table entries provides all transitions, semantically equivalent to applying a twist X to a cubie, so that it goes from slot A orientation B to slot C orientation D.

Conclusion

Seeking the God's number for Rubik's Cube was a great quest. Cubeops, our reference software, was for its purpose. I believe it indicates that this representation is efficient and easy to manipulate enough.

This also sheds some light for us about what to expect next. If MC4D/2x2x2x2 follows the same philosophy, we will find that it stores 16 cubies (2x2x2x2, literally 16 "corners"), and each has ... well, 12 possibility of orientations (I admit this is not that obvious). In other words, an unsigned char (1-byte memory) can still represent all states of a cubie.

What if it uses a totally different scheme to store the information of the hypercube? Well, we will see...

小結

參考 Cubops 這一套資料結構。