How would you represent a Rubik's Cube in code?

Question

If you were developing software to solve a Rubik's Cube, how would you represent the cube?

Answer 1

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.

Answer 2

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.

Answer 3

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...

Answer 4

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.

Answer 5

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.

Answer 6

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?

Answer 7

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.

Answer 8

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.

Answer 9

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.