Assembling a 4-dimensional Rubik's Cube

We are familiar with the Rubik's Cube puzzle, but, living in three-dimensional space, it is difficult to imagine such a one in four-dimensional. Of course, Rubik did not patent four-dimensional cubes, and we are talking only about the likeness of the Rubik's cube.

Therefore, first I will talk about how I imagine a four-dimensional puzzle.

Tesseract

First, imagine how a three-dimensional cube is obtained. Take a one-dimensional space: everything that we can depict in it is limited to one-dimensional objects, such as a point, a segment, a ray, a line. We draw a segment of unit length AB [0,1]. Now we add the second dimension: the ordinate axis will be directed upwards, and our unit segment AB lies on the abscissa axis, in the Cartesian coordinate system.

Perhaps two-dimensional space is the most common for human understanding, because neither a sphere, nor a cube can be drawn, we are used to depicting them as a projection onto a plane. Well, we have no problems with two-dimensional space, so let's think about how to get a square. So, we take the segment AB (the vertices A (0,0) and B (1,0)) on the abscissa axis, retreat exactly one along the ordinate axis and duplicate the segment, call it CD, with points C (0,1) and D (1,1).

To get the square, we now need to connect the corresponding vertices, that is, connect the vertex A (0,0) with its duplicate C (0,1), and connect the vertex B (1,0) with D (1,1). Now we have the square ACDB. Having understood how this works in two-dimensional space, it will be quite simple to understand how a cube in three-dimensional is obtained. So on the points:

1. Add the third dimension, the applicate axis will be directed in depth.
2. Duplicate ACDB by stepping back one unit along the applicate axis, the vertices are transformed as follows:
A (0,0,0) -> H (0,0,1)
C (0,1,0) -> F (0,1,1 )
D (1,1,0) -> G (1,1,1)
B (1,0,0) -> E (1,0,1)
3. Connect the corresponding vertices of the squares.

Now the reader is morally ready to see the tesseract:



In fact, we duplicate the cube, shifting along the axis of the fourth dimension, and connect the corresponding vertices - you can’t imagine any easier way. For clarity, we will increase the duplicate cube by placing the original cube inside it. Here is such an image is most often used when trying to project a tesseract on a plane:



To emphasize that all segments of the tesseract are single and to show the equal projection, the four-dimensional cube can be represented by animation:



But this is all a saying, and a fairy tale is ahead!

From tesseract to puzzle

Now let's figure out what is a four-dimensional puzzle, and most importantly how to portray it.

As you know, a cube has six faces, therefore, a three-dimensional puzzle has 6 colors. To simplify our life, we will work with a 2x2x2 cube, in particular, it will be very useful for us that the permutations of such a cube are only 3 ^ 6 * 7! = 3674160.



Let's list the faces:
- On the abscissa axis Left-Right, color green-blue.
- Down-Up ordinate, yellow-white.
- On the axis of applicate Front-Back, color red-orange.

Turn on the warp drive and open the wormhole in the fourth dimension!

This is how foreign mathematicians depict a four-dimensional puzzle:



That is, in fact, we just took a three-dimensional 2x2x2 cube, added an axis to the fourth dimension and got the fourth line:
- Along the fourth axis is Ana-Kata, color is purple-gray.

It should be noted that now all groups of 8 colors are three-dimensional facets, and not two-dimensional faces (which had 4 colors). Now, as I imagine exactly the same (mathematically equivalent) four-dimensional cube I:



If we take the inside of the puzzle (that is, a cube consisting of 8 three-color corners), then we simply cut an octahedron from a three-dimensional cube and painted the inner cut surface in purple, as a result, the corners of the cube became tetrahedrons painted in 4 colors. Then we duplicated all the corners of the cube, turned the inner face of the tetrahedra out and painted it gray, resulting in my charm.
Of course, the main difficulty of my work was not using OpenGL to write a program in Delphi depicting the projection of a four-dimensional puzzle, but in developing an algorithm for solving such a puzzle. That is, I had an idea, a mathematical representation, and OpenGL was the only means I knew for displaying three-dimensional graphics.

Facet

Now we will consider what is the rotation of the hyperface. In the described puzzle there are only 8 facets, each of them is a cube. Rotating a hyperface is essentially a rotation of one cube relative to another. For example, the left cube is relative to the right, or the inner is relative to the outer. There are 24 options to rotate the cube, because each of the 6 faces can be rotated on one of the 4 sides. We have 8 such cubes, which means in one move we have 192 invariants of the arrangement of puzzle elements. I will give only a few of them below, under the spoiler.

Assembly

The main assembly sequence was as follows:

1. The heuristic method, which places elements with gray colors at the position of the outer hyperface, called Kata, respectively, all elements with purple colors after this stage will be in the inner hyperface Ana.
2. Orientation of gray colors of the outer hyperface outward.
3. Orientation of the purple colors of the inner hyperface inward.
4. Placement of elements of the external hyperface according to the table of solutions of a three-dimensional 2x2x2 cube (of which there are 3674160 in total).
5. Placement of elements of the inner facet according to the same decision table.

As for the first point, there wasn’t any special difficulties to place the gray outside, the purple inside it was enough to sort it out , well, maybe a little optimized, the whole essence of the algorithm looks like we twist this side, twist the others, rearrange a couple more times, oh, done!

The second stage had algorithmic complexity O (192 ^ 3), but only 256 invariants, so it was decided to compose a permanent table with pre-computed combinations of solutions (in fact, the OLL analog in the Friedrich method for the Rubik's Cube). It has a maximum of 6 moves.

Although the third stage was solved exactly like the second, the exponential complexity of the order of O (192 ^ 4) led to two-day iterations, and the number of invariants was already 65536. It makes a maximum of 8 moves.


But after orienting the colors on the Ana-Kata facets, we reduce the problem to a three-dimensional cube. The fourth stage uses a table of 3674160 invariants, the solution of a three-dimensional cube is a maximum of 11 moves. So the external hypercube is assembled.


For the fifth stage, we use the same solutions of the three-dimensional cube, with the only exception that for each rotation of any face, the inner cube rotates with the necessary side relative to the external for each rotation, as a result, the external, already assembled, facet rotates only its right side and remains always almost assembled.


That is, using tables, the computer now dispensed with microseconds for searching, but only caching the table from the HDD to the RAM takes several minutes when the program is initialized. Well, if there are three tables with pre-calculations at once, the assembly algorithm does not seem complicated anymore.