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

I found an x-y-z coordinate system to be a simple way of addressing a Rubik's cube, and rotation matrices a simple, generic way of implementing the rotations.

I created a Piece class containing a position vector (x, y, z). A Piece can be rotated by applying a rotation matrix to its position (a matrix-vector multiplication). The Piece also keeps tracks of it colors in a tuple (cx, cy, cz), giving the colors facing along each axis. A small amount of logic ensures these colors are updated appropriately during a rotation: a 90 degree rotation in the X-Y plane means we would swap the values of cx and cy.

Because all of the rotation logic is encapsulated in the Piece class, the Cube can store an unordered list of Pieces, and rotations can be done in a generic fashion. To do a rotation of the left face, select all pieces with an x-coordinate of -1 and apply the appropriate rotation matrix to each Piece. To do a rotation of the entire cube, apply the same rotation matrix to every piece.

This implementation is simple and has a couple of niceties:

1. A Piece object's position will change, but its colors do not. This means you can ask for the red-green piece, hang on to the object, do some rotations, and check the same object to see where the red-green piece ended up.
2. Each type of Piece (edge, center, corner) has a unique coordinate pattern. For a 3x3 cube, a corner piece has no zeros in its position vector ((-1, 1, 1)), an edge has exactly one zero ((1, 0, -1)), and a center piece has two zeroes ((-1, 0, 0)).
3. The rotation matrices that work for a 3x3 cube will work for an NxN cube.

Downsides:

1. Matrix-vector multiplication is slower than swapping values in arrays.
2. Linear-time lookups for Pieces by position. You'd have to store Pieces in an external data-structure and update that during rotations for constant-time lookups by position. This defeats some of the elegance of using rotation matrices, and leaks rotation logic into your Cube class. If I was implementing any kind of search-based solving algo, I'd use another implementation.
3. Pattern analysis (during solving) is not as nice as it could be. A Piece has no knowledge of its adjacent Pieces, and analysis would be slow due to the above performance issues.

Answer 5

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

Since you already received great answers, let me add just a detail.

Irrespective of your concrete representation, note that lenses are a very fine tool for "zooming in" on the various parts of a cube. For instance, look at the function cycleLeft in this Haskell code. It is a generic function which cyclically permutes any list of length 4. The code for performing the L move looks like this:

moveL :: Aut (RubiksCube a)
moveL =
    cong cube $ cong leftCols cycleLeft
              . cong leftSide rotateSideCW

Thus cycleLeft operates on the view given by leftCols. Similarly, rotateSideCW, which is a generic function taking a side to a rotated version of it, operates on the view given by leftSide. The other moves can be implemented in similar ways.

The goal of that Haskell library is to create pretty pictures. I think it succeeded:

Answer 8

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 9

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 10

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.

Answer 11

From personal experience using a set to keep track of each rotational part of the cube works well. Each sub cube is in three sets no mater the size of the rubik cube. So to find a sub cube some where on the rubik's cube you just take the intersection of the three sets (the result is one sub cube). To do a move remove the effected sub cubs from the sets involved in the move and then put them back into the sets that take them as a result of the move.

The 4 by 4 cube will have 12 sets. 6 sets for the 6 faces and 6 sets for the six bands that go around the cube. The faces each have 16 sub cubes and the bands each have 12 sub cubs. There are a total of 56 sub cubes. Each sub cube holds information about color and the direction of the colors. The rubik cube itself is a 4 by 4 by 4 array with each element having information consisting of the 3 sets that define the sub cube at that location.

Unlike the other 11 answers this data structure has you using the intersection of sets to define each sub blocks location in the cube. This save the work of having to update the near sub blocks when a change is made.