14 Дек 2018

Recreational mathematics with colored cubes

blender_cubes

The intellectual games like puzzles discipline a thinking, form a thought culture, the value of which is difficult to overestimate, they develop imagination, and all these personal improvements are acquired of the person in the most entertaining form — in the form of the game.

Instant Insanity

There is very old puzzle in my puzzles’ collection. It comprises four colored cubes. Each of the cubes’ faces are colored with one of the four colors. The objective is to stand cubes in linear arrangement (a rectangular prism) such that all four long sides show each color only once (each face of the pyramid includes all four colors).

Robert Stegmann[1] calls all such puzzle the «Instant Insanity Family» and I will use that name.
The puzzle «Instance Insanity» is easily solved with the help of graph theory. An example of such a decision is often given to students as an illustration of the application of graph theory. There are many articles on the Internet that include similar examples.

assembly
Fig. 1. The puzzle «Insant Insanity»

Cubes can be connected in 244=331776 spatial positions, forming thus 8 combinations being solutions (see Fig. 1). We can reduce the number of combinations for one of the cubes. If we let the first cube occupy only 3 positions, placing it sequentially on each of three opposite faces, then the generated combinations will be 3×243=41472. In the latter case, the solution will be found only one. Thus, the chance of a random decision is 41472.

Every position of Instant Insanity can be solved in eight moves or less. I’ll show it below.

I was interested to learn how many there are different assemblies of four cubes from which on can make this puzzle, and besides how many moves do we need to solve this brainteaser?

We introduce some notation and conventions for use in what follows.

Notations and terms

For convenience of use in the future, we index the faces of the cube as follows (see Fig. 2):
  • 0 — the bottom face,
  • 1 — the front face,
  • 2 — the top face,
  • 3 — the back face,
  • 4 — the left side,
  • 5 — the right side
Figire 1.
Fig. 2. All unfolded views of cubes and index markup

We describe all possible rotations of the cube in its local right-handed coordinate system, in which we arrange the cube so that the centers of the cubes arranged in a row are on the Z-axis, and the X-axis is directed upwards.
We write through the indices of the faces all 24 spatial positions of the cube.

Let’s denote the rotation of the cube around the X axis by an angle of 90 degrees as Rx, the rotation by an angle of -90 degrees is denoted by -Rx. Rotations around other axes will be denoted similarly.
Also we will use the record of the sequence of turns with numbers from 1 to 24 as they are ordered in the table.

Table of rotations
Fig. 3. Rotations and combinations of rotations

In this form of recording, it is easy to fix the spatial position of the cube, even if it has made a complex sequence of rotations: for example, to obtain a sequence of indices for rotations (X, X), you can rearrange faces’ indexes of its initial position in the appropriate order:

042531 X            A convenient form of writing is
042531 X            by placing transformable indexes from
------              top to bottom, from the original
032154 XX           position to the new spatial
                    displacement of the cube

Index record simplifies the graphical solution. After you were able to extract two subgraphs from the multigraph, you can use indexed faces to find the position of the cubes:

graph solution
Fig. 4. The images are steps to graphical solve the puzzle

If we position the first cube in this way: 002113 (RRBYYG), the second one can occupy two positions to match the position of the first cube: 113210 (YYGBYR) or 311201 (GYYBRY). However, the positioning of the third cube finally determines the position of the second cube.

Despite the fact that the graphics solution is unique, every cube corresponds to this graphical scheme in eight positions:

RRBYYG YRRBYG RBYRYG RYBRGY BRRYGY BYRRYG RRYBGY YBRRGY
YYGBYR BYYGYR YGBYYR YBGYRY GYYBRY GBYYYR YYBGRY BGYYRY
GBRGYY GGBRYY BRGGYY GGRBYY RBGGYY RGGBYY BGGRYY GRBGYY
BGYRYY RBGYYY GYRBYY BRYGYY YGBRYY YRBGYY GBRYYY RYGBYY
------ ------ ------ ------ ------ ------ ------ ------
012345 301245 123045 032154 210354 230145 103254 321054

Note that if all the cubes are in position 4, 7, 8, 13, 16, 20 or 22, then this is also a solution.

How many of them?

Let’s look closely at the seventh column of notes to the graphical solution, and find these cubes in the table of Figure 2. These are cubes with numbers 27, 16, 10, 5. They rotate in Figure 1. How many different sets of four cubes are available for this puzzle and are not isomorphic? In other words, how many assemblies are those that can not be obtained from one another by repainting the faces?

No other cubes from the Figure 2 form an isomorphic assembly with the set 27, 16, 10, 5. These 46 cubes generate 1073 different non-isomorphic puzzles.
>R.Stegmann singled out 52 unique graphs for the coloring of the cube. He used «brute force» to find 5160 sets with a single graphical solution. This technique can not be considered good for finding all non-isomorphic sets of four cubes for the following reasons:
  1. we do not know which set of cubes is optimal for this task
  2. Robert did not take color permutations on the faces
The correct method is to generate immediately whole solutions, while checking them for the uniqueness of the coloring. In addition, a close look at the index form of recording the spatial positions of the cube (Fig. 3), allows some optimization of this way.

The index record simplifies the selection of suitable color models. Twelve cubes from the set of R.Stegmann have unsuitable color models, so they are not represented in the final assemlies.

selection
Fig. 5. The selection of suitable color models

You can see from Figure 5 which color schemes are not allowed for cubes. For example, take the cubes with numbers 24 and 21 from R.Stegmann set.

The 24th cube has a graph YY/RR/YG, 
it corresponds to a sequence of YRYRYG: YRYRBG
                                        032154
                                        ------
                                        YRYRGB

The 21st cube has a graph BG/YR/YR, 
it corresponds to a sequence of BYGRRY: BYGRRY
                                        042531
                                        ------
                                        BYGRRY

The cube did not change the build state, although it was rotated. Such a cube should be discarded.
In the Rob Stegman set, only 40 cubes are suitable for creating combinations. They form only 939 nonisomorphic assemblies.

You can see that there are some graphs missing in my set, although some are repeated.

selection
Fig. 6. Admissible graphs and conformances to them in my set

These unfolded views of cubes are missing in my set:

add graphs
Fig. 7. Added cubes

What happens if I add these cubes to my set and repeat the search for combinations? — Nothing very much.
I added 9 cubes with missing schemes to the beginning of my array in order shown Fig.7, and started the program for building assemblies from new array. I got 1073 nonisomorphic assemblies again, but they are all repainted assemblies of the previous result.

For example, consider the assembly formed by 1st and 5th cubes of new array (Fig. 7) and by 3th and 43th cubes of the array shown in Fig. 2:
Fig. 7 1st  cube: RRYGBB                    RRYGBB
Fig. 7 5th  cube: RYBBBG → rotation 524013: GBBRYB
Fig. 2 3th  cube: YYBGRR → rotation 103254: YYGBRR
Fig. 2 43th cube: BGRYGB                    BGRYGB
Swap the blue color for a green one and we get the assembly with cubes 29th, 14th, 3th and 12nd from Fig.2:
RRYGBB G ↔ B → RRYBGG 29th cube from 1st set 
GBBRYB G ↔ B → BGGRYG 14th cube from 1st set
YYGBRR G ↔ B → YYBGRR 3th  cube from 1st set
BGRYGB G ↔ B → GBRYBG 12nd cube from 1st set
New entities are not created. As before, there are only 1073 nonisomorphic assemblies wich match the solution only in 8 spatial positions.

However, some things did not remain the same: the cubes with number 2nd, 3th, 4th, 6th, 8th from added array (Fig.7) and 10th, 29th from first array (Fig.2) aren’t used in new solution sets at all. To build assemblies at this time, only 48 cubes were required, whereas in the first array 46 are enough.

Recolor each of these cubes in 24 ways and get all 24×1073 isomorphic assemblies.

It’s all 204 unique graphs:
all graphs
Fig. 8. Despite the fact that unique puzzles exist 1073, there are only 204 unique graphs

How many moves do we need to solve this puzzle?

This puzzle is interesting to solve in the mind. Is it complicated? Using the recording of rotations in indexed faces, it’s easy to show that solution of puzzle can be found in no more than 8 steps.

Look at the table of rotations (Fig.3): among all the unique spatial arrangements in which each of the cubes can be found, there are 6 locations that are 3 rotations of 90 degrees each, and 11 consisting of 2 consecutive turns. Let’s take the solved combination of cubes and try to simulate a combination as far removed from the solution by changing the spatial placement of each cube. Obviously, this combination must also be equidistant from the combinations to which the assembly goes, when using 4, 7, 8, 13, 16, 20, 22 turns to each cube.

Let’s find out the effect of sequences of three rotations (numbers 19 to 24 in the table) on the position of the cubes of the assembly: on can be only 15 combinations from 6 such turns:
<19,20,21,22> <19,20,21,23> <19,20,21,24>
<19,20,22,23> <19,20,22,24> <19,20,23,24>
<19,21,22,23> <19,21,22,24> <19,21,23,24>
<19,22,23,24> <20,21,22,23> <20,21,22,24>
<20,21,23,24> <20,22,23,24> <21,22,23,24>

The order of the cubes in the assembly does not matter for the solution, so the order of the turns in these combinations is also not significant. Only one of the combinations does not contain turns 20 and 22.
From the above, 20 and 22 are the posions of the solution.

Suppose we moved one of the cubes to position 20. How much moves do to translate other cubes to this position? Any cube in position 19, 21, 22, 23 or 24 can be moved to position 20 in two moves:
19+11: 21+14: 22+16: 23+12: 24+15:
435102 534120 321054 240513 250431
341520 351402 230145 425031 524013
------ ------ ------ ------ ------
103254 103254 103254 103254 103254 
In case one cube is fixed in position 22 only two movements are required to move the other cubes to that position as well:
19+18: 20+16: 21+9:  23+10: 24+17:
435102 103254 534120 240513 250431
153420 230145 143502 504231 405213
------ ------ ------ ------ ------
321054 321054 321054 321054 321054
Any of the turns 9, 10, 11, 12, 14, 15, 16, 17 or 18 is a combination of two moves.
In total, to achieve a solution, we needed only six actions.

Let’s see the set <19,21,23,24>. How many steps should be taken in this case?

Turn the cube in position 19 to position 16. And move other cubes to same position.
From the above, 16 is the posion of the solution.

19+3:  21+6:  23+5:  24+2:
435102 534120 240513 250431
514302 415320 052413 042531
------ ------ ------ ------
230145 230145 230145 230145
Any of the turns 2, 3, 5 or 6 is a simple turn. In this case, to achieve a solution, we needed only four actions.
It’s time to consider combinations of double turns.

We will not consider rotations with numbers 8, 13 and 16, since any of them fixes one of the cubes in the position of the solution. Take, for example, the sequence <9,10,11,12> for the purposes of our analysis. You can translate this sequence into any of the 8 positions of the solution (see above) as a result of the following operations, which are easy to find using the table:

9+23:  10+6:  11+5:  12+19:  turns: 3 + 1 + 1 + 3 = 8
143502 504231 341520 425031
240513 415320 052413 435102
------ ------ ------ ------
301245 301245 301245 301245 pos. 4
OR
9+5:   10+21: 11+23: 12+3:   turns: 1 + 3 + 3 + 1 = 8
143502 504231 341520 425031
052413 534120 240513 514302
------ ------ ------ ------
123045 123045 123045 123045 pos. 7
OR
9+12:  10+9:  11+10: 12+11:  turns: 2 + 2 + 2 + 2 = 8
143502 504231 341520 425031
425031 143502 504231 341520
------ ------ ------ ------
032154 032154 032154 032154 pos. 8
OR
9+10:  10+14: 11+12: 12+18:  turns: 2 + 2 + 2 + 2 = 8
143502 504231 341520 425031
504231 351402 425031 153420
------ ------ ------ ------
210354 210354 210354 210354 pos. 13
OR
9+15:  10+11: 11+17: 12+9:   turns: 2 + 2 + 2 + 2 = 8
143502 504231 341520 425031
524013 341520 405213 143502
------ ------ ------ ------
230145 230145 230145 230145 pos. 16
OR
9+2:   10+3:  11+24: 12+21:  turns: 1 + 1 + 3 + 3 = 8
143502 504231 341520 425031
042531 514302 250431 534120
------ ------ ------ ------
103254 103254 103254 103254 pos. 20
OR 
9+24:  10+19: 11+2:  12+6:   turns: 3 + 3 + 1 + 1 = 8
143502 504231 341520 425031
250431 435102 042531 415320
------ ------ ------ ------
321054 321054 321054 321054 pos. 22
OR
9+17:  10+18: 11+15: 12+14:  turns: 2 + 2 + 2 + 2 = 8
143502 504231 341520 425031
405213 153420 524013 351402
------ ------ ------ ------
012345 012345 012345 012345 pos. 1
In each of these cases the sum of all the turns made over the cubes is 8.

References and external links:

1. Robert Stegmann — Puzzle historian, expert and collector, as well as the host of this years International Puzzle Party in Canada. Rob’s Puzzle Page