If you were developing software to solve a Rubik's Cube, how would you represent the cube?
13 Answers
This ACM Paper describes several alternative ways that it has used to represent a rubik's cube and compares them against eachother. Sadly, I don't have an account to get the full text but the description states:
Seven alternative representations of Rubik's Cube are presented and compared: a 3-by-3-by-3 array of 3-digit integers; a 6-by-3-by-3 array of literals; a 5-by-12 literal matrix; an ll-by-ll sparse literal matrix; a 54-element vector; a 4-dimension array; and a 3-by-3-by-3 nested array. APL functions are given for orientation moves and quarter-turns plus several useful tools for solving the cube.
Also, this RubiksCube.java file contains a pretty clean representation along with the relevant code for rotating the sections (if you are looking for actual code). It uses a cell and faces array.
-
2Any ACM members able to download that PDF for us and repost it?– mmcdoleCommented Feb 1, 2009 at 5:39
-
@mmcdole the paper's examples are in APL to make use of them, I think we'll require more than just a PDF... APL isn't exactly the easiest language to read and understand. Commented Oct 10, 2020 at 12:33
-
If anyone is after the paper, it seems to be hosted in multiple free to access places as well as the ACM. See kupdf.net/download/…– DanCommented Feb 6, 2021 at 11:02
-
Note that the RubiksCube.java is only for a 2x2x2 cube. Still interesting as a starting point. Commented Jul 3, 2023 at 4:09
The short answer is that it depends on how you're going to solve the cube. If your solver is going to use a human method like the layer-by-layer approach or the Fridrich method then the underlying data structure won't make much of a difference. A computer can solve a cube using a human method in negligible time (well under a second) even in the slowest of programming languages. But if you are going to solve the cube using a more computationally intensive method such as Thistlethwaite's 52-move algorithm, Reid's 29-move algorithm, or Korf's 20-move algorithm, then the data structure and programming language are of utmost importance.
I implemented a Rubik's Cube program that renders the cube using OpenGL, and it has two different types of solvers built in (Thistlethwaite and Korf). The solver has to generate billions of moves and compare each cube state billions of times, so the underlying structure has to be fast. I tried the following structures:
- A three-dimensional array of chars, 6x3x3. The color of a face is indexed like cube[SIDE][ROW][COL]. This was intuitive, but slow.
- A single array of 54 chars. This is faster than (1), and the row and stride are calculated manually (trivial).
- 6 64-bit integers. This method is essentially a bitboard, and is significantly faster than methods (1) and (2). Twisting can be done using bit-wise operations, and face comparisons can be done using masks and 64-bit integer comparison.
- An array of corner cubies and a separate array of edge cubies. The elements of each array contain a cubie index (0-11 for edges; 0-7 for corners) and an orientation (0 or 1 for edges; 0, 1, or 2 for corners). This is ideal when your solver involves pattern databases.
Expanding on method (3) above, each face of the cube is made up of 9 stickers, but the center is stationary so only 8 need to be stored. And there are 6 colors, so each color fits in a byte. Given these color definitions:
enum class COLOR : uchar {WHITE, GREEN, RED, BLUE, ORANGE, YELLOW};
A face might look like this, stored in a single 64-bit integer:
00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001
Which is decoded as:
WGR
G B
WYO
An advantage of using this structure is that the rolq
and rorq
bit-wise operators can be used to move a face. Rolling by 16 bits effects a 90-degree rotation; rolling by 32 bits gives a 180-degree turn. The adjacent pieces need to be up-kept manually--i.e. after rotating the top face, the top layer of the front, left, back, and right faces need to be moved, too. Turning faces in this manner is really fast. For example, rolling
00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001
by 16 bits yields
00000000 00000001 00000000 00000001 00000010 00000011 00000100 00000101
Decoded, that looks like this:
WGW
Y G
OBR
Another advantage is that comparing cube states can in some instances be done using some clever bit masks and standard integer comparisons. That can be a pretty big speed-up for a solver.
Anyway, my implementation is on github: https://github.com/benbotto/rubiks-cube-cracker/tree/2.2.0 See Model/RubiksCubeModel.{h,cpp}
.
Expanding on method (4) above, some of the algorithms for programmatically solving the Rubik's Cube use an iterative deepening depth-first search with A*, using pattern databases as a heuristic. For example, Korf's algorithm utilizes three pattern databases: one stores the index and orientation of the 8 corner cubies; one stores the index and orientation of 6 of the 12 edge pieces; the last stores the index and orientation of the other 6 edges. When using pattern databases, a fast approach is to store the cube as a set of indexes and orientations.
Arbitrarily defining a convention, the edge cubies could be indexed as follows.
0 1 2 3 4 5 6 7 8 9 10 11 // Index.
UB UR UF UL FR FL BL BR DF DL DB DR // Position (up-back, ..., down-right).
RY RG RW RB WG WB YB YG OW OB OY OG // Colors (red-yellow, ..., orange-green).
So the red-yellow edge cubie is at index 0, and the white-green edge cubie is at index 4. Likewise, the corner cubies might be indexed like so:
0 1 2 3 4 5 6 7
ULB URB URF ULF DLF DLB DRB DRF
RBY RGY RGW RBW OBW OBY OGY OGW
So the red-blue-yellow corner cubie is at index 0, and the orange-green-yellow corner cubie is at index 6.
The orientation of each cubie needs to be kept as well. An edge piece can be in one of two orientations (oriented or flipped), while a corner piece can be in three different orientations (oriented, rotated once, or rotated twice). More details about the orientation of pieces can be found here: http://cube.rider.biz/zz.php?p=eoline#eo_detection With this model, rotating a face means updating indexes and orientations. This representation is the most difficult because it's hard for a human (for me at least) to look at a big blob of index and orientation numbers and verify their correctness. That being said, this model is significantly faster than dynamically calculating indexes and orientations using one of the other models described above, and so it's the best choice when using pattern databases. You can see an implementation of this model here: https://github.com/benbotto/rubiks-cube-cracker/tree/4.0.0/Model (see RubiksCubeIndexModel.{h,cpp}
).
As mentioned, the program also renders the cube. I used a different structure for that part. I defined a "cubie" class, which is six squares with 1, 2, or 3 colored faces for center, edge, and corner pieces, respectively. The Rubik's Cube is then composed of 26 cubies. The faces are rotated using quaternions. The code for the cubies and cube is here: https://github.com/benbotto/rubiks-cube-cracker/tree/4.0.0/Model/WorldObject
If you're interested in my Rubik's Cube solver program, there's a high-level overview video on YouTube: https://www.youtube.com/watch?v=ZtlMkzix7Bw&feature=youtu.be I also have a more extensive write-up on solving the Rubik's Cube programmatically on Medium.
One way would be to focus on the visual appearance.
A cube has six faces and each face is a three-by-three array of squares. So
Color[][][] rubik = new Color[6][3][3];
Then each move is a method that permutes a specific set of colored squares.
-
This is the way I have used. Makes it easy to rotate faces.
new_cube[face][i][j] = clockwise ? old_cube[j][2 - i] : old_cube[2 - j][i]; }
– azzCommented Feb 5, 2013 at 12:08
Eschew optimisation; make it object-oriented. A pseudocode class outline I've used is:
class Square
+ name : string
+ accronym : string
class Row
+ left_square : square
+ center_square : square
+ right_square : square
class Face
+ top_row : list of 3 square
+ center_row : list of 3 square
+ bottom_row : list of 3 square
+ rotate(counter_clockwise : boolean) : nothing
class Cube
+ back_face : face
+ left_face : face
+ top_face : face
+ right_face : face
+ front_face : face
+ bottom_face : face
- rotate_face(cube_face : face, counter_clockwise : boolean) : nothing
The amount of memory used is so small and processing so minimal that optimisation is totally unnecessary, especially when you sacrifice code usability.
-
2While not "optimization" I think this is "object-oriented overthinking", at least a little. What's the purpose of these elaborate faces and rows, really? A face can be simply 9 squares. Even simpler, a cube can be 54 squares. Getting the rotations right is tough, either way.– Jo SoCommented Sep 25, 2017 at 0:27
An interesting method to represent the cube is used by the software "Cube Explorer". Using a lot of clever maths that method can represent the cube using only 5 integers. The author explains the maths behind his program on his website. According to the author the representation is suited to implement fast solvers.
There are many ways to do this. Some ways are make more efficient use of memory than others.
I have seen people use a 3 x 3 x 3 array of cuboid objects, where the cuboid object needs to store color information (and yes, that center object is never used). I have seen people use 6 arrays, each of which is a 3 x 3 array of cuboids. I have seen a 3 x 18 array of cuboids. There are many possibilities.
Probably a bigger concern is how to represent the various transforms. Rotating a single face of a physical cube (all cube moves are essentially rotations of a single face) would have to be represented by swapping around a lot of cuboid objects.
Your choice should be one that makes sense for whatever application you are writing. It may be that you are only rendering the cube. It may be that there is no UI. You may be solving the cube.
I would choose the 3 x 18 array.
There are 20 cubies that matter. So one way to do it is as an array of 20 strings. The strings would hold 2 or 3 characters indicating the colors. Any single move affects 7 of the cubies. So you just need a remapper for each of the six sides.
Note: This solution doesn't manage to remember the orientation of the logo sticker that's on the white center.
By the way, I helped someone do a software Rubik's cube once, maybe 15 years ago, but I can't remember how we represented it.
You could imagine the cube as three vertical circular linked lists, which intersect three horizontal linked lists.
Whenever a certain row of the cube is rotated you would just rotate the corresponding pointers.
It would look like this:
struct cubeLinkedListNode {
cubedLinkedListNode* nextVertical;
cubedLinkedListNode* lastVertical;
cubedLinkedListNode* nextHorizontal;
cubedLinkedListNode* lastHorizontal;
enum color;
}
You might not actually need the 2 'last'-pointers.
[ I did this with C, but it could be done in Java or C# just using a simple class for cubeLinkedListNode, with each class holding references to other nodes. ]
Remember there are six interlocking circular linked lists. 3 vertical 3 horizontal.
For each rotation you would just loop through the corresponding circular linked list sequentially shifting the links of the rotating circle, as well as the connecting circles.
Something like that, at least...
The shortest representation is something like this one: codepen.io/Omelyan/pen/BKmedK
The cube is unwrapped in 1D array (vector of 54 elements). A few-line rotation function swaps stickers and based on the cube's symmetry. Here's complete working model in C, I made it in 2007 when was a student:
const byte // symmetry
M[] = {2,4,3,5},
I[] = {2,0,4,6};
byte cube[55]; // 0,0,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1,1, ... need to be filled first
#define m9(f, m) (m6(f, m)*9)
byte m6(byte f, byte m) {return ((f&~1)+M[m+(f&1)*(3-2*m)])%6;}
void swap(byte a, byte b, byte n) {
while (n--) {byte t=cube[a+n]; cube[a+n]=cube[b+n]; cube[b+n]=t;}
}
void rotate(byte f, byte a) { // where f is face, and a is number of 90 degree turns
int c=m9(f, 3), i;
swap(c, c+8, 1);
while (a--%4) for (i=2; i>=0; --i)
swap(m9(f, i) + I[i], m9(f, i+1) + I[i+1], 3),
swap(f*9+i*2, f*9+i*2+2, 2);
swap(c, c+8, 1);
}
A rubik cube has:
- 8 corners each containing a unique corner cubelet.
- 12 edges each containing a unique edge cubelet.
- 6 centres each containing a unique centre cubelet.
Each corner cubelet can be in one of 3 orientations:
- not rotated;
- rotated clockwise 120°; or
- rotated anti-clockwise 120°.
Each edge cubelet can be in one of 2 orientations:
- not flipped; or
- flipped 180°.
The centre cubelets are fixed relative to each other; however there are 24 possible orientations (ignoring rotations of individual centres, which is only relevant if you are solving a picture cube) as there are 6 ways to pick the centre cubelet that is on the "up" face of the cube and then 4 ways to pick the centre cubelet that would be on the "front" face.
You can store this as:
- an array of eight 3-bit integers each representing the corner cubelet in a corner position.
- an array of eight 2-bit integers each representing the orientation of the corner cubelet in a corner position.
- an array of twelve 4-bit integers each representing the edge cubelet in an edge position.
- an array of twelve 1-bit integers each representing the orientation of the edge cubelet an edge position.
- an 5-bit integer representing an enumeration of all 24 possible orientations of the centre cubelets.
This gives a total of 105 bits (14 bytes).
Space optimisations:
Since the centres are always fixed then you can assume that they never move and do not need to be stored. With this, if you want to do an
E
move then do an equivalentU D'
pair of moves instead.This would reduce the size to 100 bits (13 bytes).
If you restrict the representation to solvable cubes then it is possible to store the cube in a smaller space as:
- Once you know 7 corner cubelets you can work out what the 8th is.
- The orientation of the corner cubelets has a fixed parity so once you know the orientation of 7 corners you can derive the 8th.
- Similar for the edges, you only need to store 11-of-12 edge cubelets and edge orientations and can calculate the remaining one.
This saves a further 10 bits for a total of 90 bits (12 bytes). However, the calculations required to work out the missing information may mean that this space optimisation is not worth the performance penalty.
More Space Optimisations:
If you really want to optimise the space for the cube the:
- the 8 corner cubelets can be arranged in
8! = 40320
permutations and40320
can be represented in16
bits. - 7 ternary (base-3) digits can represent the orientation of the corners (deriving the position of the 8th) and
3^7 = 2187
and can be represented in12
bits. - the 12 edge cubelets can be arranged in
12! = 479001600
permutations and479001600
can be represented in29
bits. - 11 binary digits can represent the orientation of the edges (deriving the position of the 12th) which would be
11
bits.
This gives a total of 68 bits (9 bytes).
The maximum number of permutations of a solvable rubik cube is (8!*3^8*12!*2^12)/12 = 43,252,003,274,489,856,000 ~= 4.3*10^19
which can be stored in 66
bits (9 bytes) and while its possible to enumerate all the possible solutions it is not worth it to save those last 2 bits.
The others well addressed describing the physical cube, but regarding the state of the cube... I would try using an array of vector transformations to describe the changes of the cube. That way you could keep the history of the rubiks cube as changes are made. And I wonder if you could multiply the vectors into a transformation matrix to find the simplest solution?
As a permutation of the 48 faces which can move. The basic rotations are also permutations, and permutations can be composed, they form a group.
In a program such a permutation would be represented by an array of 48 elements containing numbers 0 to 47. The colors corresponding to the numbers are fixed, so a visual representation can be computed from the permutation, and vice versa.
I found it very useful to store the state as a mapping from the coordinates of the center of the cubelet outside the face to the color. So, for example, the upper face of the front-top-right cubelet is state[1, -1, 2]
. So moves are done by just applying rotations to the indices.
You can see a simple simulator I wrote using it here: https://github.com/noamraph/cube