Formulating Rubik’s Cubes and other sequential move puzzles is one thing that I have been thinking for a long time.
I learned how to solve a Rubik’s Cube when I was 13. But I’ve never been a speed-solving type of player, even now, I’m still using the most elementary methods and can barely solve a Rubik’s Cube in 50 seconds. My interest is in making cool patterns and collecting and solving puzzles of different shape and structure.
As a CS student it’s quite natural to want to write programs for everything you find worthy of doing with a computer. And so I wanted to write a Rubik’s Cube simulator! Not just a simple one, but one with which you can simulate any combinatoric puzzle – one to rule them all!
Then we are faced with the problem of how to represent these puzzles. They must be machine-readable, of course. Then I think it should be friendly to a human user. It should not only be human-readable: it is intended to be primarily hand-written, so it must be made sense easily, be concise in syntax, not tedious to write, but still with immense expressing power. That will make most existing formats undesirable: with xml you will probably end up writing more tags than useful content, and with json there is no structure.
Then, on some day last year, I found the key! What makes it possible to describe the complex structure of a combinatoric puzzle concisely is its symmetry. I started working at once and after several weeks I’ve got a simple parser for my custom cube description language and a simple simulator. The syntax resembles a general purpose programming language but much simpler.
Then it’s time for graduate school applications and I put that project aside. Now that I have some spare time, I’d like to pick it up.
Actually I want to start from scratch again. The last time, I didn’t even write a specification for my language. Implementing a language without a specification, that’s like writing a program without comment, only worse. And after a year I’ve got a lot of new thoughts on how to describe and implement a puzzle, so the basic mechanism of my program would probably change.
And my rendering was done in OpenGL 1 style (primarily due to the lack of good tutorials on OpenGL 3+). That definitely need to be changed.
This time, I’ll write the specification of my custom cube description language before writing the parser and explain all the ideas behind it, and provide annotated examples, so that someone other than me can actually understand this language and use it to model puzzles. Hopefully it will finally become a useful tool for those hobbyists who can not afford to by expensive puzzles.
(And this will also be the first project of Martian Computing Research! Wait for more to come, ahahaha!)
Here as the first part of the documentation I’ll explain the central idea of my design by trying to formulate the definition of the original Rubik’s Cube. The syntax here is not what actually used in the language, it just serves to illustrate the idea.
First, we will want to define all the blocks. Following the convention, we name the faces U (up), R (right), F (front), D (down), L (left) and B (back). It seems logical to simply name each block by all the faces it touches. Then we get something like this:
block U, D, R, L, F, B; // The center blocks
block UR, UL, UF, UB, DR, DL, DF, DB, RF, RB, LF, LB; // The edge blocks
block URF, UFL, ULB, UBR, DFR, DLF, DBL, DRB; // The corner blocks.
There are some ambiguities in the ordering of faces when one block touches multiple faces, but for now we just pick an arbitrary one.
Then we will want to define all possible states of a block. Here, a state is just a position and an orientation. The set of positions is the same as the set of blocks. How about the orientations? We could have something like position name plus rotation angle:
state UR, UR+180;
state URF, URF+120, URF+240;
But after a second thought we found that it would be a good idea to just cycle the face order of the name of a block to get names of states:
state UR, RU;
state URF, RFU, FUR;
This is logical since the number of orientations of a block is determined by the number of faces it touches. Note that “block URF is in state RFU” means that the U sticker on block URF is on face R, etc., so rotating a corner block 120 degrees clockwise correspond to cycle the face names in the state name backwards 1 step. This form also give us a lot of advantages. If block URF is at its own position, its rotation angle is obvious. What if it is at another position, say position DBL, with its U sticker on face L? There is no straightforward definition of rotation angle. With this form, we can get rid of rotation angle: since U sticker is on face L, R sticker is on face D and F sticker is on face B, block URF must be in state LDB! Actually this give us a meaningful definition of rotation angle: state name LDB is obtained by cycling position name DBL backward 2 steps, so the rotation angle is defined to be 240 degrees! Once we have defined rotation angle for every block in every position, we can verify that the sum of rotation angles of all blocks (modulus 360) is invariant under any operation, which is an important step in proving the total number of possible states of a Rubik’s cube.
Finally we will want to define all the operations. An operation moves blocks and change their states, so its definition comes in two parts: a geometric transformation and a table of state changes:
operation U {
axis (0, 0, 1); // Assume that x axis points forawrds,
// y axis points rightwards and
// z axis points upwards
angle -90; // In mathematics positive angle usually
// means counterclockwise
UR -> UF;
RU -> FU;
...
UB -> UR;
BU -> RU;
URF -> UFL;
RFU -> FLU;
FUR -> LUF;
...
UBR -> URF;
U -> U; // The state does not change but geometric
// transformation still apply to block U
// so we include it.
}
If you know something about combinatorics, you should know that the change of states is actually a permutation. So we can write it more concisely in cycle notation:
operation U {
axis (0, 0, 1);
angle -90;
state_cycle (UR, UF, UL, UB);
state_cycle (RU, FU, LU, BU);
state_cycle (URF, UFL, ULB, UBR);
state_cycle (RFU, FLU, LBU, BRU);
state_cycle (FUR, LUF, BUL, RUB);
state_cycle (U);
}
We will then need to write this for every other operation! The inverse operations (U’, etc.) can be easily inferred by reversing the direction of the rotation and cycle so we don’t need to write them explicitly, but that’s still a lot of work! After that, we will have a full definition of a Rubik’s Cube.
Somehow we can feel the redundancy. But this redundancy is not like manually assigning the same value to each entry in a long array, which can easily be simplified with a for-loop. It is the result of the intrinsic symmetry, both geometric and algebraic, of the Rubik’s Cube. Actually, the Rubik’s Cube is probably the best real-life example of an object with a complex symmetry. If you check the “Group theory” article on Wikipedia, you can find a Rubik’s Cube right there on the beginning of the page!
But we only need a tiny portion of what group theory has to offer. We just focus on how the formulation of a Rubik’s Cube could be simplified.
Consider defining operation R. It would be good if we can just “rotate” the definition of operation U by -90 degrees around the x axis. What do we need to do this “rotation”? We need to rotate the axis around which operation U rotate the blocks (yes, we rotate a rotation!) and change the state names in the permutation such that U changes to R, R changes to D, etc., i.e. we do a permutation of face names. (And again, yes, we permute a permutation!) Let’s try it:
meta_rotation x {
axis (1, 0, 0);
angle -90；
face_cycle (U, R, D, L);
}
apply this to operation U, we get something like:
operation R {
axis (0, 1, 0);
angle -90;
state_cycle (RD, RF, RU, RB);
state_cycle (DR, FR, UR, BR);
state_cycle (RDF, RFU, RUB, RBD);
state_cycle (DFR, FUR, UBR, BDR);
state_cycle (FRD, URF, BRU, DRB);
state_cycle (R);
}
Yes! this exactly what we wanted. Apply this meta-rotation twice more and we get the definitions of operations D and L. We can similarly define meta-rotations around other axes:
meta_rotation y {
axis (0, 1, 0);
angle -90；
face_cycle (F, U, B, D);
}
meta_rotation z {
axis (0, 0, 1);
angle -90；
face_cycle (R, F, L, B);
}
Apply y to operation U, we get definitions of operations F and B.
What if we apply z? Well, we get essentially the same definition of operation U, but it does look a bit different:
operation U {
axis (0, 0, 1);
angle -90;
state_cycle (UF, UL, UB, UR);
state_cycle (FU, LU, BU, RU);
state_cycle (UFL, ULB, UBR, URF);
state_cycle (FLU, LBU, BRU, RFU);
state_cycle (LUF, BUL, RUB, FUR);
state_cycle (U);
}
The state orders in the state cycle have changed! What does this tell us? We only need to say UR -> UF, then UF -> UL -> UB -> UR can all be generated by applying the appropriate meta-rotation! So to get the definition of all operations, we only need a part of one definition! We will get something like this:
apply (x, xx, xxx, y, yyy) {
apply (z, zz, zzz) {
operation U {
axis (0, 0, 1);
angle -90;
U -> U;
UR -> UF;
RU -> FU;
URF -> UFL;
RFU -> FLU;
FUR -> LUF;
}
}
}
If you know a bit about symmetry groups, you can see that we are actually applying the whole chiral octahedral symmetry group O to the minimal part of definition to get the full definition. the group O is of order 24 and here we are only explicitly writing out 1/24 of the full definition. Group O can be generated by any two of x, y and z, so we may write our definition as
generate_group (x, y) {
operation U {
axis (0, 0, 1);
angle -90;
U -> U;
UR -> UF;
RU -> FU;
URF -> UFL;
RFU -> FLU;
FUR -> LUF;
}
}
Comparing to the whole lot of things we need to write without symmetry, this is a big step forward.
We can also simplify the definition of states in the same way:
generate_group (x, y) {
state U, UR, URF;
}
And also blocks. But this time we get URF, RFU and FUR which is actually the same block. But that’s not a problem, we can just do some tricks in the syntax if we really want to implement such a cube description language and allow blocks to have aliases:
generate_group (x, y) {
block U;
block UR alias RU;
block URF alias RFU;
}
Note that we don’t need to write this explicitly
block URF alias FUR;
Because that will also be automatically generated for us!
Now we can write the definition of a Rubik’s Cube in full:
meta_rotation x {
axis (1, 0, 0);
angle -90；
face_cycle (U, R, D, L);
}
meta_rotation y {
axis (0, 1, 0);
angle -90；
face_cycle (F, U, B, D);
}
generate_group (x, y) {
state U, UR, URF;
block U, UR alias RU, URF alias RFU;
operation U {
axis (0, 0, 1);
angle -90;
U -> U, UR -> UF, RU -> FU;
URF -> UFL, RFU -> FLU, FUR -> LUF;
}
}
So simple! But this still is an “abstract” definition, to actually be able to visually simulate a Rubik’s Cube we need geometric models. But even that can be simplified. Remember that we have geometric transformations in our meta-rotation definition. We can define the 3D model, sticker color, etc. for one of each different kind of block and the rest will be handled by the symmetry group! One we get the idea of how to simplify the definition, adding more features is just a matter of syntax.
Martian Computing Research | 火星计算研究所 