Recreational mathematics with colored 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.
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
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.
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:
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:
- we do not know which set of cubes is optimal for this task
- Robert did not take color permutations on the faces
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.
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.
These unfolded views of cubes are missing in my set:
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.
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 BGRYGBSwap 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
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:
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.
19+In case one cube is fixed in position 22 only two movements are required to move the other cubes to that position as well:11: 21+14: 22+16: 23+12: 24+15: 435102 534120 321054 240513 250431341520351402230145425031524013------ ------ ------ ------ ------ 103254 103254 103254 103254 103254
19+Any of the turns 9, 10, 11, 12, 14, 15, 16, 17 or 18 is a combination of two moves.18: 20+16: 21+9: 23+10: 24+17: 435102 103254 534120 240513 250431153420230145143502504231405213------ ------ ------ ------ ------ 321054 321054 321054 321054 321054
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+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.3: 21+6: 23+5: 24+2: 435102 534120 240513 250431514302415320052413042531------ ------ ------ ------ 230145 230145 230145 230145
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+In each of these cases the sum of all the turns made over the cubes is 8.23: 10+6: 11+5: 12+19: turns: 3 + 1 + 1 + 3 = 8 143502 504231 341520 425031240513415320052413435102------ ------ ------ ------ 301245 301245 301245 301245 pos. 4 OR 9+5: 10+21: 11+23: 12+3: turns: 1 + 3 + 3 + 1 = 8 143502 504231 341520 425031052413534120240513514302------ ------ ------ ------ 123045 123045 123045 123045 pos. 7 OR 9+12: 10+9: 11+10: 12+11: turns: 2 + 2 + 2 + 2 = 8 143502 504231 341520 425031425031143502504231341520------ ------ ------ ------ 032154 032154 032154 032154 pos. 8 OR 9+10: 10+14: 11+12: 12+18: turns: 2 + 2 + 2 + 2 = 8 143502 504231 341520 425031504231351402425031153420------ ------ ------ ------ 210354 210354 210354 210354 pos. 13 OR 9+15: 10+11: 11+17: 12+9: turns: 2 + 2 + 2 + 2 = 8 143502 504231 341520 425031524013341520405213143502------ ------ ------ ------ 230145 230145 230145 230145 pos. 16 OR 9+2: 10+3: 11+24: 12+21: turns: 1 + 1 + 3 + 3 = 8 143502 504231 341520 425031042531514302250431534120------ ------ ------ ------ 103254 103254 103254 103254 pos. 20 OR 9+24: 10+19: 11+2: 12+6: turns: 3 + 3 + 1 + 1 = 8 143502 504231 341520 425031250431435102042531415320------ ------ ------ ------ 321054 321054 321054 321054 pos. 22 OR 9+17: 10+18: 11+15: 12+14: turns: 2 + 2 + 2 + 2 = 8 143502 504231 341520 425031405213153420524013351402------ ------ ------ ------ 012345 012345 012345 012345 pos. 1
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