Entertaining math with colored cubes

Intellectual games, like puzzles, discipline thinking, form thinking culture, the value of which is difficult to overestimate, develop the imagination, and, all these own improvements a person acquires in the most exciting form - in the form of a game.

---

Quite a bit of history

The “Instant Insanity” puzzle is probably one of the most popular for illustrating the applicability of graph theory in solving problems of a similar type. In any case, on youtube you will find many examples of this particular use of it by a considerable number of mathematics teachers. It is difficult to say how long this puzzle has been known for itself, but it was popular enough to draw the attention of one of the members of the University of Cambridge University of Cambridge, who was hiding behind the pseudonym “F.”, back in 1947. De Carteblanche ”(his real name, according to the well-known collector and chronologist of puzzles Robert Stegmann / Rob Stegmann - Cedric AB Smith), and to be noted in the publication of the periodical“ Eureka ”No. 9 (1947) of the society“ The Archimedeans ”. After the publication of the elegant solution of F. De Carteblanche, and to this day, mathematicians find reasons to return from time to time to this problem, and to the class of problems arising from it.

The puzzle itself consists of 4 cubes, painted in 4 colors, which are proposed to be arranged in a row so that on each side of the resulting prism / pyramid all 4 colors are represented. For brevity and convenience, often use the designation for the pyramid "1x1x4".
')
The commercial name "Instant Insanity" stuck with this puzzle in the late 1960s. Her other known trade names are “Tantaliser”, “Crazy Cubes”, and there are about a dozen other, less well-known but fairly common, not a few also clones representing its modifications.

In 1969, the Science and Life magazine, number 2, appeared a small note about this puzzle from Bronislav Ivanovich Koltovy, a well-known popularizer of science, a great fan of puzzles and the author of numerous books on puzzles and entertaining mathematical problems. Later, at least two toy factories in the USSR, in Odessa and Kirov (Vyatka software), produced this puzzle.


Fig. 1. The puzzle, produced in the 1970s by the Vyatka Production Association, Kirov

The puzzle is really very fascinating, since all the features that make this kind of game popular are present in it: it is moderately complex, and has an attractive design - it can be solved in no more than 8 steps, and can be arbitrarily compact.

The puzzle in my photo, which I have been keeping for more than 40 years, is called an “one-solution puzzle” in English-language literature (sometimes the expression “simple solution” is also used). Such a name may not seem the most obvious, and I will explain its origin below.

I will definitely give here a graphic solution of the puzzle, but earlier this I would like to introduce some definitions, which were assigned to simplify further presentation of the material to me.

For what, actually?

Are there many sets of cubes of four, with "one solution"? - I have never met anywhere attempts to make such a calculation, although it is extremely simple, but there were indications of patents that protect the rights of the owners, including both the trading name of the game, and the combination of painted cubes. The thought of making such a calculation came right after the idea of ​​writing a computer version of the puzzle. It may seem that the task of finding all possible combinations of cubes with “one solution” is too narrow, specific, but the approach I used to search for an array of four-element assemblies can be very convenient for describing and formalizing other problems with cubes, and for solving these problems.

Actually the purpose of this article, in addition to entertain the reader with examples of spatial-color transformations of four-element assemblies of cubes, is also to offer the community enthusiastically discussing puzzles like the one in question, a simple, concise and understandable language describing such states , like a cube of an object, instead of a long and painful “sweep number 2, turn around the Z axis, in the right-sided system ..”, etc. Anyone who has to, at least occasionally, tire his imagination while reading like x phrases believe annoyed with the lack of a more concise and expressive techniques describe the state of the object under discussion. Particularly disturbing are the lengthy descriptions of the states of programmers' objects, the mental culture of which is sophisticated by the habit of formalization, logic, and algorithmization.

Let's try to formalize a few simple observations over the cubes.

Some naming conventions and terminology

For ease of use in the future, we index the faces of the cube as follows (see. Fig. 2 ):
0 - the bottom edge, 1 - the front edge, 2 - the upper edge, 3 - back, 4 - the left lateral, 5 - the right lateral .


Fig. 2. Sweep cubes

We describe all possible turns of a cube in its local right-sided coordinate system in which we place 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.


Fig. 3. Indexed Turns

Let us mark the letter with a rotation of 90 degrees around the corresponding axis, a minus sign in front of it indicates that the rotation has been carried out at -90 degrees.

In such a recording form, it is easy to fix the spatial position of the cube, he would not perform an arbitrarily complex sequence of turns: for example, you can rearrange the index sequence for turns (X, X) in the corresponding column “indices” of the table of the order of the original position of the indexes of the cube.

A convenient form of writing is with the transformed indices from top to bottom, from the initial position to the new spatial displacement of the cube.

Graphic solution

Why is it “unique” if the cubes, in strict accordance with the requirements of the puzzle, can obviously form several different spatial combinations?


Fig. 4. Assembled puzzle

Because the “right” puzzle has the only graphical solution !
To repeat the decision of F. De Carteblanche, we need a brief excursion into graph theory, and the knowledge we need is so insignificant that people who have not heard about this area of ​​mathematics will hardly feel new knowledge as “baggage”.

Each cube in the graph representation can be written as a combination of its opposite sides - for example, take the cube with number 27 ( Fig.2 ), its record looks like this: RY / RB / GY.

• The order of writing faces and the colors themselves in the faces does not matter, which directly indicates the invariance of the permutations of the faces of a single cube to the state of solving the puzzle. This fact does not seem to be the most expected, because it is somewhat surprising: changing, for example, two opposite faces of a cube twice, we get the same cube, but in a different spatial position, but changing the faces once or three times, we have a cube completely different, however in combination with the three old set cubes again forms a puzzle, which has a “simple solution”. Let's “revive” this observation by taking the index record: choose cubes with numbers 27, 16, 10, 5 from the table of cubes sweeps. Since faces 4 and 5 of the cube are lateral (by agreement ), it is obvious that the sweeps of these cubes are shown in Fig. 2 in the position of the assembly (decision), adopting the digital designation "red - 0, yellow - 1, blue - 2, green - 3" we write:
  
  [001231] - 27
[112301] - 16
[233011] - 10
[320111] - 5
. 4.

  interchange the opposite faces of the first cube, except for its side faces hidden from the observer: [120031] - but this is the same cube, only at position 230145 (Z, Z); swap the faces with indices 0 and 2: [100231] - the cube in position 210354 (Y, Y) will take the same place in the assembly, except that the lateral faces hidden from the observer have been swapped; swapping the faces with indices 1 and 3, we get the cube [021031], which after turns 032154 (X, X) will also become [001213], as the previous one. The assembly as a whole, meanwhile, as soon as we return the “modified” cube to its former position, will continue to be “solved”.
• Let us pay attention to the turns for numbers 4, 7, 8, 13, 16, 20, 22 from the Indexed Turns Table (Fig. 3) - these are the same turns in which the side faces of the dice do not take part, and all these turns applied to all the cubes of the assembly at the same time, do not break the "solution" of the puzzle. Those. spatially different combinations of cubes, in which a solution to a puzzle can actually be observed ... 8.
  

However, back to the graphs . It is enough for us to imagine the graph as a certain set of vertices (nodes, nodes) that are in connections defined among themselves or, in other words, connected by edges (links, edges). By vertices , in our case, we will assume colors or the colored faces themselves, and as links the physical edge of the cube is appropriate only in the sense of indicating that the two colors chosen on the graph form a pair in the concrete cube implementation in question. If the edge is closed at the same vertex , it is customary to call the graph with such a construction a pseudograph , and the corresponding edge is a loop (loop).

Let us graphically solve the puzzle in Fig. 5: in the line record, the cubes, its components, look like YG / RB / RY, RY / GY / BY, GB / RG / YY, GR / YY / YB . Below each cube we will place its representation in the form of vertices and edges of the corresponding graph , after which we combine all four pseudographs into a single graphic design.

Actually, it is on this intricacies and we have to think to solve the puzzle:

• inside this combined multigraph, it is necessary to distinguish two separate subgraphs (two paths), each of which only once passes through all four color vertices, using each of the 4 edges numbered from 1 to 4-X. Moreover, each vertex must have only two outgoing edges or only both ends of a loop emanating from it. One subgraph will represent a row of cubes in the “puzzle solving” position, facing the observer, the second - a row of cubes in the “top” position. It is obvious that any edge cannot be used in both subgraphs , since cannot simultaneously represent the front and the top of the assembled prism.

Fig. 5. Graphic puzzle solution

It turns out that dividing a multigraph into two subgraphs , observing all these conditions, is possible only in one way. Hence, in fact, there was a stable expression "the only solution."
If each of the cubes in its resulting placement (indexed entry in Fig. 5) is rotated in the sequence XXZ (103254), then we will recognize in this assembly the familiar cubes 27, 16, 10, 5.

Of course, there are sets of cubes of the fourth, which have no single solution, just like those that have too many solutions to make them seem entertaining.
In general, it continues to seem to me that I continue to exploit the borrowed speech stamp - “the only solution” is not the most successful way, but it may be a concise and precise definition for assemblies with the minimum possible number of combinations required by the condition of the problem . Personally for me, any combination of cubes that allows for a larger number of combinations for assembly, rather than the minimum possible, causes some difficulty with its classification.


Fig.6. Assembly example with 24 solutions

Little about complexity

In all the texts I reviewed for this puzzle (Instant Insanity, Tantalizer), studies of its complexity came down to counting the total number of combinations with which you can place cubes in a pyramid, or calculating the probability of finding a solution among the possible combinations of cubes. Moreover, these calculations are sometimes made in such an amazing way that you simply lose yourself trying to penetrate the idea of ​​the author: for example, according to the author (or authors) of the Wikipedia article , the probability of finding a solution to a puzzle is 13824. The figure is the result of the author’s insight. regarding the fact that the order of arrangement of the cubes in the pyramid does not matter, and therefore generates new 24 solutions, and why it’s not bad to divide 24x24x24x24 into these 24 ones, to find the probability ... And this bloop spreads through the network by efforts “pollinators” of the Internet space that do not doubt.

Among the 331776 possible combinations formed by the cubes (naturally, without trying to change their order in the pyramid), only 8 solutions can be found, which will give a probability slightly higher than the calculated by the authors of the Wikipedia article - 41472. And this figure is also found in the same article, but already in relation to the number of configurations that are unique or significant for the search for a solution: it is enough to successively fix the first cube on one of the faces of each of the three pairs of opposite faces, then the number of variants of significant combinations will be 3x 24x24x24 This figure coincides with the probability just because fixing the first cube, we get the only solution in the process of sorting out possible combinations.

Meanwhile, using the form of recording turns in indexed edges, it is easy to show that a solution to the puzzle can be found in no more than 8 steps.

Carefully consider the table in Figure 3: among all the unique spatial arrangements in which each of the cubes can be located, there are 6 locations consisting of 3 turns at 90 degrees, and 11, consisting of 2 turns.

It seems quite logical if, in order to find the greatest number of steps required to solve a puzzle, we take a combination of cubes in the position of solving the puzzle and try changing the spatial distribution of each die to model the combination that is “remote” from the solution - i.e. “Equidistant” from combinations into which an “assembly” could go if all turns were simultaneously applied to the turns for numbers 4, 7, 8, 13, 16, 20, 22 from the table Fig.3.

Let's start with a study of what consequences the use of 3-fold turns (numbers from 19 to 24 in the table) will have for each of the cubes: the total combinations of 6 3-step turns, as applied to our case, can be made up of 15:
<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 turns in these combinations is also not significant.
Any of the turns with numbers 20 and 22 immediately leads the cube to which this turn was applied to the position occupied by this cube in one of the 8 puzzle solutions (see above). If we suppose that a cube to which rotation 20 was applied spatially fixed (not needing further rotation), then any cube that is in one of 5 other 3-step positions can be transferred to position 20 in two step: position 19 should be applied to the rotation 11 (19 + 11 → 20), to 21 + 14 → 20, 22 + 16 → 20, 23 + 12 → 20, 24 + 15 → 20 (we simply rearrange the indices of the faces of the initial position in accordance with indications of the added rotation):
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 the event that we fix a cube to which we applied rotation number 22, possible transitions for other cubes may look like this:
19 + 18 → 22, 20 + 16 → 22, 21 + 9 → 22, 23 + 10 → 22, 24 + 17 → 22.

So we needed only six actions to reach the solution.

Only one of the 15 3-step combinations contains neither the 20th rotation from the rotation table, nor the 22nd. - This is a set of <19,21,23,24>. Perhaps the duration of the steps to the solution, in this spatial arrangement, will be different:
rotate the cube in position 19 (X, X, Y) to position 16 (Z, Z): 19 + 1 (Y) → 16 (we made only one turn, turning the cube 90 degrees around the Y axis); for the remaining three cubes, we also need only one operation per cube to translate it into position 16 (Z, Z):
19 + 3 → 18, 21 + 6 → 18, 23 + 5 → 18, 24 + 2 → 18. - In this case, it took only 4 turns to move to the position of the assembled solution.

It remains to look intently at what 2-step rotary combinations promise us, in which we immediately give up turning behind numbers 8, 13 and 16, since any of them fixes one of the cubes in the solution position, and take, for example, for our analysis of the sequence <9,10,11,12> - this sequence can be transferred to any of the 8 decision positions (see above) as a result of the following operations, easily located using the table:

9 + 23 (X, Y, Y) → 4, 10 + 6 (-Y) → 4, 11 + 5 (-X) → 4, 12 + 19 (X, X, Y) → 4 or
9 + 5 (-X) → 7, 10 + 21 (X, X, -Z) → 7, 11 + 23 (X, Y, Y) → 7, 12 + 3 (Y) → 7 or
9 + 12 (X, -Z) → 8, 10 + 9 (X, Y) → 8, 11 + 10 (X, Z) → 8, 12 + 11 (X, -Y) → 8 or
9 + 10 (X, Z) → 13, 10 + 14 (Y, Z) → 13, 11 + 12 (X, -Z) → 13, 12 + 18 (-X, -Y) → 13 or
9 + 15 (Y, -X) → 16, 10 + 11 (X, -Y) → 16, 11 + 17 (Z, -Y) → 16, 12 + 9 (X, Y) → 16 or
9 + 2 (X) → 20, 10 + 1 (Y) → 20, 11 + 24 (X, Z, Z) → 20, 12 + 21 (X, X, -Y) → 20 or
9 + 24 (X, Z, Z) → 22, 10 + 19 (X, X, Y) → 22, 11 + 2 (X) → 22, 12 + 6 (-Y) → 22 or
return to the initial position by reverse turns, - in any of these cases, the sum of all the turns performed on the dice is equal to 8 .

So how many of them?

I didn’t want some combination of cubes to become familiar to the player in the mobile version of my puzzle, and didn’t hope that 24 variants of possible repainting a set of cubes could mislead inquiring minds for a long time.
In addition, it’s just interesting to yourself: how many total unique combinations of four-color cubes of 4th exist, which are combinations with “one solution”, and which are not “repainting” themselves?

You can simply take all 68 possible colorings of the cubes (this is exactly the number of colorings in the 4th color indicated by the Burnside Lemma ) and by simple search “for 4th out of 68th” all these combinations can be found (by checking them for “uniqueness” and “repainting ") - this method, however, does not differ in grace and promises to be very time-consuming machine calculation (more than 30 times from the one adopted by me, as later shown by comparison). It seemed to me optimal to build immediately possible combinations of cubes by the 4th. In addition, a close look at the index form of recording the spatial positions of the cube (Table, Fig. 3) allows for some optimization of this sorting:

• writing through the indices makes it easy to determine which color patterns of the cube coloring cannot be found in assemblies with a “single” (minimum set of puzzle matching combinations) solution: 12 cubes used by Rob Stegmann in his set of 56 are just not suitable for such assemblies therefore, groups 5 and 6, in its classification, have not appeared anywhere in “simple” solutions .
• By eliminating the “useless” color models even before the stage of modeling the assemblies of 4 cubes themselves, it is possible to significantly reduce the time for iterating over combinations of cubes for assemblies.
• It is appropriate to use these filters, as in puzzles with a three-color coloring of cubes (there are also such, but here we do not consider them), and in the case of a four-color coloring.

Fig.7. Invalid sequences

It is easy to see from Fig. 7 that cubes having oppositely painted opposite or adjacent non-lateral faces, as well as cubes whose filling of the lateral faces repeats the painting of any of the non-lateral faces cannot be present in assemblies with “one solution”, t .to. generate new, additional solutions.

It should be noted that completely “fit” cubes easily create assemblies that do not meet the criterion of “uniqueness of solution”: for example, the combination in Fig.6, in which the synchronous placement of assembly cubes in any of its 24 possible spatial positions leaves the assembly “solved” , formed just "fit" cubes with numbers 25, 17, 15, 23.

“Not repainted” assemblies with “one solution” accumulated 1073 in a time slightly longer than a minute of my computer's work, and these 46 cubes, of which all these assemblies are combined, are presented in Fig. 2. I was somewhat discouraged that in this set there are no 10 more cubes, the coloring of which I intended to see, because they fully met the requirements I had formulated. Then I added them first to the array of "my" cubes and drove away the usual " spiteful brute force " - as a result, the generated array of assemblies continued to remain a number in 1073, only the set of cubes used for these assemblies changed: four cubes from the "new" ones were added to my set, but ousted two previously existing ones in the set of dice ... The same result was obtained for an array of 68 cubes, generated exclusively from the principle of the uniqueness of coloring.
The magic number is 1073.

Repainting

All 1073 assemblies I found are unique, none of them can be turned into any other repainting and turning of the cubes. At the same time, any other assemblies combined from the 46 cubes listed in the table will be only isomorphic derivatives of these 1073 assemblies previously recorded.

How this happens can be seen from the following example.

Let's create an assembly with “one solution” from the cubes we have (all sweeps from Fig. 2 ) - this set is absent among the 1073 final sample assemblies, but this is quite a playable, one-way puzzle.

[001233] - 29
[123300] - 30
[230121] - 17 XX-Y (534120)
[312000] - 32

The assembly is shown in the solution position. Repaint its facets as follows: yellow - in blue, blue - in yellow, otherwise 1 - 2, 2 - 1:

[002133] - XXZ (103254)] : [001233] - 29
[213300] - XXZ (103254)] : [123300] - 30
[130212] - XXZ (103254)] : [312021] - 46
[321000] - XXZ (103254)] : [230100] - 31

That is, in this example, it was not possible to create a new entity by repainting (any assemblies formed from the set shown in Fig. 2 are already taken into account among the existing 1073's) - the assembly we repainted is not included in the final set of 1073 unique puzzles, but can be made up of those 46 cubes, which served as material for all puzzles. However, such an assembly will be only an example of isomorphism, since by an ordinary substitution of colors, it turns into another assembly (from other cubes) already taken into account by us. Nevertheless, the "repainting" creates a considerable amount of "unrecognizable" looking puzzles. On the R.Stegmann site there are enough examples of isomorphically homogeneous Instant Insanity puzzles.

"What follows from this?"

It will be extremely annoying if the culture of intellectual leisure gives way to a contemplative leisure culture. I hope that their peaceful coexistence is possible.