How to construct a cubie representation of a rubik’s cube, given an array

Just to get this out of the way, I have seen this, and it is not what I’m looking for.

So, let’s say you are programming a Rubik’s Cube. (I know, very unoriginal, but bored programmers have to do something..) This Rubik’s Cube is defined by an array of six 2-D arrays (one for each face,) and these 2-D arrays’ sizes vary, based on the size of the cube. For instance, if I had a 3x3x3 cube, the array would be 6x3x3. That is, it would have 6 3×3 arrays.

Now, let’s say I wanted to get an array of the cubies which make up this cube. Each cubie is defined by two things (I think..): the colors of it and its location on the cube. For example, if you had a solved cube, one of the cubies would be the red, green, and yellow cubie, and, assuming yours is sitting in the same orientation as mine, that cubie would be the front, right, up cubie.

However, none of this answers my question: how do I go about defining a set of these cubies, given an array of variable sizes. I know, for instance, that the cubie previously mentioned could be defined as cube[0][0][dimension-1], cube[2][0][0], cube[4][dimension-1][dimension-1]. (For a bit of reference, the order in which I define my faces is front, back, right, left, up, down. Hence the 0, 2, and 4, making front, right, and up.)

Anyway, with that said, I’d rather not hard-code all of this and was wondering if there was a simpler way. So, what’s the best way to do something like what I was just describing?

Edit: For clarification, I am trying to get the separate, individual, smaller cubes which make up the Rubik’s Cube as a whole. For instance, the piece with the red, green, and white stickers on it.

There are a few ways to do this.

In addition to the six 3×3 arrays containing the colors of the stickers, you could have a 3x3x3 array representing the solid cubies. (The interior cell of this array can be ignored.) The cells of the 3x3x3 array could then contain integers (or pointers to more detailed objects) describing the original location of each cubie. You just have to make sure you do the appropriate “rotation” of the 3x3x3 array each time you “rotate” the stickers.

Or you could just put everything in one 5x5x5 array. The central 3x3x3 array could represent the solid parts of the cube and the central 3×3 array of cells on each face of the 5x5x5 array could represent the stickers.

Another alternative: just a 3x3x3 array, in which each cell contains a pointer to a structure. The structure identifies the original location of the cubie and the colors and locations of the stickers on its faces. The structure also contains a modifiable integer that describes the orientation of the cubie: a particular value (say, 0) for the orientation the cubie “should” have in a fully-solved cube, and 23 other values representing the other possible orientations of the cubie after a sequence of rotations. You also need a function (which could be a simple table lookup) that says which orientation results from each possible quarter-turn applied to each possible orientation. You will also probably find use for a function that says, for each orientation, what face of the original (orientation 0) cubie is on the top, bottom, left, and so forth. To rotate a slice of the cube, you have to permute the contents of the moving cells, of course, but you also have to correctly modify the orientation of every cubie in the rotated slice (including the cubie in the center of the face for a face rotation, even though the location of the cubie does not move).

It sounds like you might like my answer here: https://softwareengineering.stackexchange.com/a/262847/156217

The basic idea is:

Address the cube in an x-y-z coordinate system, with a center at (0, 0, 0).
A Piece class stores a position (x, y, z) and colors (cx, cy, cz). The Piece knows which sticker colors are on which axis (x, y, or z) but doesn’t know which direction the sticker is facing.
The Cube stores an unordered list of Pieces.
Rotations are done by updating the position and colors of the relevant Pieces.

This is nice because all rotation logic is confined to the Piece class. A Piece doesn’t know its orientation, but it doesn’t need to. The orientation of a Piece is strictly dependent on its position: the corner at (-1, -1, -1) is the LEFT-UP-BACK corner.

Below I use the term sub cubes for your term cubie. For the 4×4 I use the numbers 1 – 56 to model each cubie. I have and array for the colors ie
each entry would look like this “G>GY>YR>R” this one is for a corner cube.
This array will get updated as the moves are made because the colors will be pointing “>” to different fixed sides. For the location of the cubies I use a set of 12 sets – one set for each type of move. 6 sets have 16 cubies in them. And 6 sets have 12 cubies in them. I ID these sets with a 3 letter code. “SBS” for side blue set. The sets get updated as the moves are made. There is a 4×4 array that holds the three three letter codes that define the three sets for the location on the cube. These do not change. I have an enum that connects the 3 letter codes to the index of an array where I keep the sets. I use a matrix rotation algorithm to up date the sets with each move. This involves removing the blocks from the various sets putting them in a 2D array running the rotation algorithm and then putting the blocks into their new homes in the sets.

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.

It all depends on what you want to do. Consider the class eight queens problem in “Algorithms + Data Structures = Programs”. A chess board representation for solving the eight queens problem is a bitset of lenth 8 (index = column number, bit if row is occupied by a queen), two bitsets for the diagonal (row – col and row + col), and a stack for recursion.

The information in one Rubik’s cube orientation is 24 moveable faces, each with a couple of bits of orientation. This can be collapsed a bit with harder math, as some corners are disjoint from edges and some configurations are impossible. In short, a scrambled Rubik’s cube makes a poor encryption key, and a small amount of data if you want to store many configurations.

Then you look at the interface for your solving algorithm and start making time/space/complexity trade-offs. Representing all 3x3x6 exposed faces as colors is high space, high cost of manipulation. In the extreme case, you could store each configuration as the minimum set of moves from an intact cube to that configuration.

Thinking about this can be fun. For a running program, just pick something that does everything you want, isn’t a terrible choice, and run with it.

Filed under: softwareengineering - @ 04:13

Thẻ: algorithms, array

Thiết kế website giá rẻ

Danh mục

How to construct a cubie representation of a rubik’s cube, given an array