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

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
• Homework? Or real-world problem...
– sdg
Apr 3, 2012 at 12:09
• You may be interested in the source code of that Rubik's Cube Solver. Apr 3, 2012 at 12:24
• I am pretty sure that a cube's number of sides should be 6 Apr 3, 2012 at 15:09
• I'd be curious to see a model of Rubik's Cube flattened so I could see all the sides simultaneously. Hmm, I'm tempted to write that now. It could be the shape of a T or even endlessly tiled if possible (I haven't thought the latter through). Apr 3, 2012 at 21:25
• I feel tempted to quote Eric Evans, "Models are neither right, nor wrong. They are simply more or less useful" (quote probably not 100% correct as it is cited from memory)
– Pete
May 11, 2012 at 8:30

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!

• even a real Rubik's cube doesn't have any inner mini-cubes
– jk.
Apr 3, 2012 at 12:17
• This will work but your algorithm will probably be inordinately complex to accomodate such a simple data structure. Apr 3, 2012 at 14:19
• As long as you know how the six surfaces are "threaded" together Which is exactly what a more robust data structure will give you. I think we are arguing for the same thing. An array sides, and a side being an array of blocks, however there is a lot of interesting properties about sides and blocks that help figure out that "threading" Don't really like that term because it can be confused with multi-threading ;) Apr 3, 2012 at 14:42
• @maple_shaft "Which is exactly what a more robust data structure will give you." I don't know about that: a data structure with more "structure" to it would necessarily bring about additional incidental complexity related to setting up, maintaining, and accessing individual parts of that structure. It is hard to say what would be more complex - implementing ugly shifts on a plain array with some corner cases plus a "free ride" on accessing individual cells, or a structure with a somewhat less complex shifts and somewhat more complex reads. Apr 3, 2012 at 15:02
• As someone who has actually written programs to manipulate a Rubik's Cube, I took the simple approach of using six two-dimensional arrays, one per face. It's true that you have to implement some fundamental operations on the cube that are a little annoying, but after that you are free to forget about the representation. It was never a problem for me. I often wondered how other representations would work from a performance perspective, but never felt burdened from a coding perspective. Apr 3, 2012 at 16:05

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.

• agree that each block would need to have unique properties. but wouldn't transformation be tedious because you have to update the references to the adjacent blocks and your list of lists . maybe its better to just have an unordered list of blocks that you can query. and you just update the adjacent block references when you perform a transformation. If you want a list of all blocks in a face then you could query your list for all adjacent blocks to the center block(s), right?
– Mel
Apr 4, 2012 at 7:41
• @Mel It is possible to do it either way, but after talking with dasblinkenlight I actually think that his approach would be less complex. I wish that his answer had more votes than mine. I am not all that good with algorithms and the most efficient one, I just really like rubiks cubes and collect them (over 40 different kinds from all over the world). Apr 4, 2012 at 11:16
• Although dasblinknenlight's answer the simplest solution, I'm awarding you the bounty because I like the fact your answer includes some of the logic that would be needed for such a data structure, and the different block attributes May 14, 2012 at 13:25
• This data model is more true to reality but it makes some of the simple operations that you would like to do harder than they should be - Just getting the state of the cube would require traveling recursively through lists of cubes which is cumbersome.
– Ziv
May 4, 2015 at 10:30
• @Ziv True, however the question was asking about the data structure and not necessarily about the algorithms. May 4, 2015 at 12:57

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.

• Classic "you don't want to start from here" advice! Apr 4, 2012 at 1:07
• 9 years later, jumping in: If your goal is to generate random cube states for human solvers which will be used for serious events, it's generally accepted to generate a random state for the cube and check if it's valid, rather than performing n turns on the cube. The former is more random than the first, though I'm not sure exactly why. Mar 21, 2021 at 10:27

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.
• I've found that this sort of implementation works best to represent the cube in a 3D graphics program. The matrix multiplication makes it possible to animate the layer rotations. See this github repo for an example implementation of this approach. I'm considering that to add a solver to my 3D cube, I'll need an algorithm and data structure from one of the other answers. Apr 23, 2016 at 18:44

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

• the most straightforward way of know whether a cube is solvable is to solve it. Well, using the model you suggest I guess that's true. But if you use a model closer to @maple_shaft's and track rotations, you can quickly test if a 3x3x3 cube is solvable by verifying sum of edge flips mod 2 is 0 and corner rotations mod 3 is 0. Then check the parity of the permutation by counting edge swaps and corner swaps (needed to get back to solved), their sum mod 2 must be 0 (total parity even). These are the necessary and sufficient tests to prove the cube is solvable. Apr 29, 2013 at 8:31

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

• For point 2, instead of starting with a random cube and checking if it is solvable. I would start with a solved cube, and perform n random actions on the cube to get it into a random state. Apr 3, 2012 at 16:48
• Yes, absolutely, that is the most simple way to generate a configuration that is physically possible to solve. Starting with an arbitrary configuration and determining whether it is solveable is definitely a separate but related problem. Apr 3, 2012 at 17:41
• You conjecture that there might be "fancy techniques" for determining if a cube is one that can be solved; in fact there are. If you disassemble a cube but keep the stickers on, and then reassemble the cube, you do not necessarily get a cube that is solvable; in fact, odds are one to twelve against that you have a solvable cube. You can determine if you are in a solvable state through a parity analysis of the edges and corners; you do not actually have to try to solve the cube. Apr 3, 2012 at 20:06
• Here's a brief overview of the three kinds of cube pairity properties that must be preserved for the cube to be solvable. ryanheise.com/cube/cube_laws.html. Apr 3, 2012 at 20:40
• I posted that question in the match stackexchange site and got really nice answers: math.stackexchange.com/questions/127577/…
– Mel
Apr 5, 2012 at 9:46

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:

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.

• You can buy a 17x17 cube! It does have some mechanical compromises, but it is isomorphic to the real thing. Apr 3, 2012 at 22:19

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.

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.

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.

• this doesn't seem to offer anything substantial over points made and explained in prior 11 answers
– gnat
Sep 23, 2016 at 6:03