Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
share|improve this question
1  
Homework? Or real-world problem... –  sdg Apr 3 '12 at 12:09
3  
You may be interested in the source code of that Rubik's Cube Solver. –  mouviciel Apr 3 '12 at 12:24
18  
I am pretty sure that a cube's number of sides should be 6 –  Simon Apr 3 '12 at 15:09
3  
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). –  Lee Kowalkowski Apr 3 '12 at 21:25
1  
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 '12 at 8:30
show 4 more comments

8 Answers

up vote 29 down vote accepted

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!

share|improve this answer
23  
even a real Rubik's cube doesn't have any inner mini-cubes –  jk. Apr 3 '12 at 12:17
5  
This will work but your algorithm will probably be inordinately complex to accomodate such a simple data structure. –  maple_shaft Apr 3 '12 at 14:19
6  
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 ;) –  maple_shaft Apr 3 '12 at 14:42
6  
@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. –  dasblinkenlight Apr 3 '12 at 15:02
13  
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. –  PeterAllenWebb Apr 3 '12 at 16:05
show 9 more comments

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.

share|improve this answer
    
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 '12 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). –  maple_shaft Apr 4 '12 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 –  Rachel May 14 '12 at 13:25
add comment

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.

share|improve this answer
    
Classic "you don't want to start from here" advice! –  Ergwun Apr 4 '12 at 1:07
add comment

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

share|improve this answer
    
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. –  jimhark Apr 29 '13 at 8:31
add comment

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.

share|improve this answer
    
You can buy a 17x17 cube! It does have some mechanical compromises, but it is isomorphic to the real thing. –  RBerteig Apr 3 '12 at 22:19
add comment

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

share|improve this answer
1  
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. –  Matthew Vines Apr 3 '12 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. –  Angelo Apr 3 '12 at 17:41
2  
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. –  Eric Lippert Apr 3 '12 at 20:06
1  
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. –  Eric Lippert Apr 3 '12 at 20:40
1  
I posted that question in the match stackexchange site and got really nice answers: math.stackexchange.com/questions/127577/… –  Mel Apr 5 '12 at 9:46
show 1 more comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.