How to represent a Rubik's Cube in a data structure

Question

If I am attempting to simulate a Rubik's Cube, how would you create a data structure to store the cube's state in memory, with X number of tiles per side?

Things to consider:

• the cube can be of any size
• it is a Rubik's cube, so layers can be rotated

Answer 1

What's wrong with a plain old array of size [6X][X]? You do not need to know about inner mini-cubes, because you do not see them; they are not part of the cube's state. Hide two ugly methods behind a nice-looking and simple to use interface, unit test it to death, and voila, you're done!

Answer 2

It should be noted that I am an avid speed cuber, but I have never tried to programatically represent a Rubik's cube in an algorithm or data structure.

I would probably create separate data structures to capture the unique aspects of each block in a cube.

There are 3 distinct types of blocks on a cube:

1. Corner Block - It has three color faces and three adjacent pieces that it will share a side with at any time.

2. Edge Block - It has two color faces and has 4 adjacent pieces that it will share a side with at any time. In 3x3 blocks it always has 2 center pieces and 2 corner pieces.

3. Center block - In a 3x3 cube this piece is not movable, however it can be rotated. It will always have 4 adjacent edge blocks. In larger cubes there are multiple center blocks that could share with another center block or an edge piece. Center blocks never are adjacent to a corner block.

Knowing this, a Block can have a list of references to other blocks that it touches. I would keep another list of lists, which would be a list of blocks that represent a single cube face and a list that keeps references to every cube face.

Every cube face would be represented as a unique face.

With these data structures it would be pretty easy to write an algorithm that performs a rotation transformation on each face, moving the appropriate blocks into and out of the appropriate lists.

EDIT: Important note, these lists must be ordered of course but I forgot to mention that. For example, if I flip the right side, then the left corner right side block moves to the right corner of the right side and is rotated clockwise.

Answer 3

When I think of this problem, I think of a static cube with the colors moving across it in known patterns. So....

A Cube object contains 6 Side objects that remain fixed indexed 0-5. Each side contains 9 position objects that remain fixed indexed 0-8. Each position contains a color.

For simplicity, handle every action in quarter turn increments. There are 3 axes of rotation, each in 2 possible directions for a total of 6 possible actions on the cube. With this information, it becomes a fairly simple task to map out the 6 possible actions on the cube.

So the color green in side 6, position 3, may move to side 1 position 3, or side 2 position 7, amongst others, depending on the action taken. I haven't explored this enough to find any mathematical translations, but patterns will probably emerge that you can take advantage of in code.

Using the data structure, how can I know if a certain cube in a certain state is solvable? I have been struggling with this question myself and haven't quite found the answer yet.

To do this, never begin with a random cube state. Instead, start with a solved state, and perform n actions programmatically to get the cube into a random starting state. Since you only took legal actions to get to the current state, the cube must be solvable.

Answer 4

you can use a simple array (each element having a 1 to 1 mapping to a square on a face) and simulate each rotation with a certain permutation

you can get away with only 3 essential permutations: rotate a slice with the axis though the front face, rotate the cube around the vertical axis and rotate the cube over the horizontal axis through the left and right faces. all the other moves can be expressed by some concatenation of these three.

the most straightforward way of know whether a cube is solvable is to solve it (find a series of permutations that will solve the cube), if you end up with 2 edges that have swapped place, a single flipped edge, a single flipped corner or 2 swapped corners you have a unxolvable cube

Answer 5

You seem to be asking two separate questions.

1. How to represent a cube with X number of sides?

If you are going to simulate a real-world Rubic's cube, then all Rubik's cubes have 6 sides. I think what you mean is "X number of tiles per dimension per side". Each side of the original Rubic's cube is 3x3. Other sizes include 4x4 (Professor's Cube), 5x5, and 6x6.

I would represent the data with 6 sides, using the "standard" cube solving notation:

• FRONT: the face facing the solver
• BACK
• RIGHT
• LEFT
• UP
• DOWN

Each side is a 2-D array of X by X.

Answer 6

The first condition that it be solveable would be that each piece be present and that colors on each piece can be used to assemble a "sovled" cube. This is a relatively trivial condition whose truth can be determined with a simple checklist. The color scheme on a "standard" cube is defined, but even if you're not dealing with standard cube there are only 6! possible combinations of solved faces.

Once you have all the pieces and colors right, then it is a matter determining if any given physical configuration is solvable. Not all of them are. The most naive way to check this is to run a cube-solving algorithm and see if it terminates with a solved cube. I don't know if there are fancy combinatorial techniques to determine solvability without actually trying to solve the cube.

As for what data structure... that almost doesn't matter. The tricky part is getting the transformations right and being able to represent the cube state in a way that allows you to neatly work with available algorithms in the literature. As Maple-shaft indicated there are three types of pieces. Literature on rubik's cube solving always refer to pieces by their type. Transformations are also represented in common ways (look up Singmaster notation). Also, all solutions that I've seen always refer to one piece as a reference point (usually putting the white center piece on bottom).

Answer 7

I like the idea of @maple_shaft to represent different pieces (mini-cubes) differently: central, edge, and corner pieces carry 1, 2, or 3 colors, respectively.

I'd represent the relationships between them as a (bidirectional) graph, with edges connecting adjacent pieces. Each piece would have an array of slots for edges (connections): 4 slots in central pieces, 4 slots in edge pieces, 3 slots in corner pieces. Alternatively, center pieces may have 4 connection to edge pieces and 4 for corner pieces separately, and/or edge pieces may have 2 connection to center pieces and 2 to corner pieces separately.

These arrays are ordered so that iterating over graph edges always represent 'the same' rotation, modulo the cube's rotation. That is, e.g. for a center piece, if you rotate the cube so that its face is on top, the order of connections is always clockwise. Similarly for edge and corner pieces. This property holds after face rotations (or so it seems to me now).

• Finding pieces belonging to an edge is trivial.
• Finding pieces belonging to a face is trivial.
• Finding faces that are at given direction to given face, or an opposite face, is traversing 2 or 3 well-defined links.
• To rotate a face, update connections of all pieces connected to the face's central piece.

Detection of clearly unsolvable conditions (swapped/flipped edges, swapped corner) if hopefully easy, too, because finding pieces of particular type and their orientation is simple.

Answer 8

How about nodes and pointers?

Assuming there is always 6 faces, and that 1 node represents 1 square on 1 face:

r , g , b
r , g , b
r , g , b
|   |   |
r , g , b - r , g , b
r , g , b - r , g , b
r , g , b - r , g , b

A node has a pointer to each node next to it. A circle rotation just migrates the pointer (Number of nodes/Number of faces)-1 nodes over, in this case 2. Since all rotations are circle rotations, you just build one rotate function. It is recursive, moving each node one space, and checking if it has moved them enough, since it will have collected the number of nodes, and there is always four faces. If not, increment the number of times moved value and call rotate again.

Don't forget it's doubly linked, so update the newly pointed nodes as well. There will always be Height*Width number of nodes moved, with one pointer updated per node, so there should be Height*Width*2 number of pointers updated.

Since all the nodes point to each other, just walk around on circle updating each node as you come to it.

This should work for any sized cube, without edge cases or complex logic. It's just a pointer walk/update.