How do you imagine Rubik Cube in code?

Question

If you were developing software for a Rubik Cube solution, how would you imagine a cube?

Answer 1

This ACM document describes several alternative ways of representing a Rubik's Cube and compares them with each other. Unfortunately, I do not have an account to get the full text, but the description says:

Seven alternative Rubik Cube representations are presented and compared: an array of 3 3-x-3 numbers; an array of literals 6 by 3 by 3; 5 by 12 letter matrix; sparse letter matrix; vector of 54 elements; 4-dimensional array; and a nested array of size 3 by 3 by 3. APL functions are given for orientation moves and quarter turns, plus some useful tools for solving the cube.

In addition, this RubiksCube.java file contains a fairly clean view, along with the appropriate code to rotate partitions (if you are looking for real code). It uses an array of cells and faces.

Answer 2

One way would be to focus on visual appearance.

A cube has six faces, and each face is a three-dimensional array of squares. So

Color[][][] rubik = new Color[6][3][3]; 

Then, each move is a method that rearranges a specific set of colored squares.

Answer 3

Separation optimization; make it object oriented. The pseudo-code class designation I used is:

 class Square + name : string + accronym : string class Row + left_square : square + center_square : square + right_square : square class Face + top_row : list of 3 square + center_row : list of 3 square + bottom_row : list of 3 square + rotate(counter_clockwise : boolean) : nothing class Cube + back_face : face + left_face : face + top_face : face + right_face : face + front_face : face + bottom_face : face - rotate_face(cube_face : face, counter_clockwise : boolean) : nothing 

The amount of memory used is so small and the processing is so minimal that optimization is completely unnecessary, especially when you sacrifice the usability of the code.

Answer 4

An interesting cube representation method is used by the Cube Explorer software. Using many clever mathematical methods, this method can represent a cube using only 5 integers. The author explains the math behind his program on his website . According to the author, the presentation is suitable for implementing quick solvers.

Answer 5

There are many ways to do this. Some methods use memory more efficiently than others.

I saw people using an array of 3 x 3 x 3 cubic objects, where the cubic object should store color information (and yes, this center object is never used). I saw how people use 6 arrays, each of which is an array of 3 x 3 cuboids. I saw a 3 x 18 array of cuboids. There are many possibilities.

Probably the biggest problem is how to present the various transformations. The rotation of one face of the physical cube (all the movements of the cube, essentially the rotation of one face) must be represented by replacing around a large number of cubic objects.

Your choice should be what makes sense for any application you write. Perhaps you only make a cube. Maybe there is no user interface. You can solve the cube.

I would select a 3 x 18 array.

Answer 6

There are 20 dice that matter. So one way to do this is with an array of 20 lines. Lines will contain 2 or 3 characters indicating colors. Any single movement affects 7 dice. Thus, you just need a redistribution for each of the six sides.

Note. This solution does not remember the orientation of the logo sticker located on the white center.

By the way, I helped someone make a Rubik cube once, maybe 15 years ago, but I don’t remember how we imagined it.

Answer 7

You can imagine a cube as three vertical circular linked lists that intersect three horizontal linked lists.

Whenever a certain row of a cube rotates, you simply rotate the corresponding pointers.

It will look like this:

 struct cubeLinkedListNode { cubedLinkedListNode* nextVertical; cubedLinkedListNode* lastVertical; cubedLinkedListNode* nextHorizontal; cubedLinkedListNode* lastHorizontal; enum color; } 

In fact, you will not need the 2 'last pointer.

[I did this with C, but it can be done in Java or C # just by using a simple class for cubeLinkedListNode, with each class linking to other nodes. ]

Remember that there are six interconnected circular linked lists. 3 vertical 3 horizontal.

For each rotation, you simply scroll through the corresponding circular linked list, sequentially moving the links of the rotating circle, as well as the connecting circles.

Something like this, at least ...

Answer 8

Short answer: it depends on how you are going to solve the cube. If your solver uses a human method, such as a layered approach or the Friedrich method, then the basic data structure will not matter much. A computer can solve a cube using the human method in a short time (much less than a second) even in the slowest programming languages. But if you intend to solve the cube using a more complex computational method, such as the Thistlethwaite 52-step algorithm, the 29 Reid step algorithm, or the 20 Korf step algorithm, then the data structure and programming language are of utmost importance.

I implemented the Rubik Cube program, which renders a cube using OpenGL, and two different types of solvers (Thistlethwaite and Korf) are built into it. The solver must generate billions of moves and compare each state of the cube billions of times, so the basic structure must be fast. I tried the following structures:

1. Three-dimensional array of characters, 6x3x3. The complexion is indexed as a cube [SIDE] [ROW] [COL]. It was intuitive, but slow.
2. A single array of 54 characters. This is faster than (1), and the line and step are calculated manually (trivially).
3. 6 64-bit integers. This method, in fact, is a bitboard and is much faster than methods (1) and (2). Curl can be performed using bitwise operations, and face comparison can be performed using masks and 64-bit integer comparisons.
4. An array of corner cubes and a separate array of edge cubes. Elements of each array contain the Kubi index (0-11 for edges; 0-7 for angles) and orientation (0 or 1 for edges; 0, 1 or 2 for angles). This is ideal when your solver uses pattern databases.

Extending the method described above (3), each face of the cube consists of 9 stickers, but the center is fixed, so only 8 should be stored. And there are 6 colors, so each color is placed in a byte. Given these color definitions:

 enum class COLOR : uchar {WHITE, GREEN, RED, BLUE, ORANGE, YELLOW}; 

A person may look like this, stored in a single 64-bit integer:

 00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001 

Which is decoded as:

 WGR GB WYO 

The advantage of using this structure is that rolq operators rolq and rorq can be used to move the face. 16-bit rolling results in a 90-degree rotation; rolling 32 bits gives a 180 degree turn. Neighboring items must be stored manually - i.e. After the rotation of the upper face, the upper layer of the front, left, back and right sides must also be moved. Turning your face in this way is really quick. For example, car

 00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001 

16 bit gives

 00000000 00000001 00000000 00000001 00000010 00000011 00000100 00000101 

It is decoded that looks like this:

 WGW YG OBR 

Another advantage is that cube state comparisons in some cases can be performed using some smart bit masks and standard integer comparisons. This can be quite a big acceleration for the solver.

Anyway, my implementation is on github: https://github.com/benbotto/rubiks-cube-cracker/tree/2.2.0 See Model/RubiksCubeModel.{h,cpp} .

Extending the method described above (4), some of the algorithms for the software solution of the Rubik's cube use iterative deepening of the depth search with A *, using template databases as heuristics. For example, Korf’s algorithm uses three template databases: one stores the index and orientation of 8 corner cubes; one stores a pointer and orientation of 6 out of 12 edges; the latter stores the index and orientation of the remaining 6 edges. When using template databases, a quick approach is to save the cube as a set of indices and orientations.

By arbitrarily defining an agreement, edge cubes can be indexed as follows.

 0 1 2 3 4 5 6 7 8 9 10 11 // Index. UB UR UF UL FR FL BL BR DF DL DB DR // Position (up-back, ..., down-right). RY RG RW RB WG WB YB YG OW OB OY OG // Colors (red-yellow, ..., orange-green). 

Thus, the red-yellow edge cube has an index of 0, and the white-green edge cube has an index of 4. Similarly, corner cubes can be indexed as follows:

 0 1 2 3 4 5 6 7 ULB URB URF ULF DLF DLB DRB DRF RBY RGY RGW RBW OBW OBY OGY OGW 

Thus, the red-blue-yellow corner cube has an index of 0, and the orange-green-yellow corner cube has an index of 6.

The orientation of each cube must also be maintained. The edge element can be in one of two orientations (oriented or inverted), while the corner element can be in three different orientations (oriented, rotated once or rotated twice). More information on the orientation of the figures can be found here: http://cube.crider.co.uk/zz.php?p=eoline#eo_detection In this model, the rotation of the face means updating the indices and orientations. This representation is the most difficult because it is difficult for a person (at least for me) to look at a large block of index and approximate numbers and check their correctness. Moreover, this model is much faster than the dynamic calculation of indices and orientations using one of the other models described above, and therefore it is the best choice when using template databases. You can see the implementation of this model here: https://github.com/benbotto/rubiks-cube-cracker/tree/2.2.0/Model (see RubiksCubeIndexModel.{h,cpp} ).

As already mentioned, the program also displays a cube. I used a different structure for this part. I defined the “cubie” class, which is six squares with 1, 2, or 3 colored faces for the center, edge, and corner elements, respectively. The Rubik's Cube consists of 26 dice. Faces rotate using quaternions. The code for cubes and cubes is here: https://github.com/benbotto/rubiks-cube-cracker/tree/2.2.0/Model/WorldObject

If you're interested in my Rubik Cube solution program, there is a high-level video on YouTube: https://www.youtube.com/watch?v=ZtlMkzix7Bw&feature=youtu.be

Answer 9

The rest took a good look at the physical cube, but dealt with the state of the cube ... I would try to use an array of vector transformations to describe the changes in the cube. Thus, you can save the history of the rubiks cube when making changes. And I wonder if you can multiply vectors into a transformation matrix to find the simplest solution?

Answer 10

As a permutation of 48 faces that can be moved. The main turns are also permutations, and permutations can be made up, they form a group.

In such a program, such a permutation will be represented by an array of 48 elements containing numbers from 0 to 47. The colors corresponding to the numbers are fixed, so the visual representation can be calculated from the permutation and vice versa.