Tiling the Chessboard with a 2×2 hole with pentominoes: relationships between the solutions

In his wonderful book Polyominoes Solomon W. Golomb tells the story of one of the first pentomino patterns to be solved using a computer. Indeed, in 1958 Dana S. Scott, professor of philosophy at Stanford University in California programmed the MANIAC computer to solve the chessboard with a middle hole pattern that is shown on fig. 1 below.

Fig. 1. Chessboard with removed center, comprising 60 squares that can be tiled by the 12 pentominoes.

Of all the "mutilated" chessboards that can be tiled with the pentominoes that one is certainly the most beautiful and symmetric (these terms are not synonymous). In addition, as Dana S. Scott found, it has the advantage of having only 65 basically different solutions, compared to more than 5000 when the missing square is situation at one of the angles of the chessboard.

On his website, Gareth Rees has an article about solving that same puzzle using Donald Knuth's Dancing links. The nice thing about having just five dozens of solutions is that you can show them on a single screen and Gareth Rees has had the good idea to produce a SVG image of all them in a 5×13 rectangle.

A classification of the solutions has already been used by Dana S. Scott when he wrote his programme some 60 years ago. It is based on an observation: there are only three basically different ways to place the X pentomino on the mutilated board. All other possible placements can be reduced to these three by reflecting or rotating the board.

Fig. 2. All possible placements of the X pentomino and which lead to 19, 26 and 20 solutions, from left to right.

We could look at each of the three groups of solutions, formed that way, and for each find the pentomino with the least number of basically different placements, then iterate the operation thrice and find another pentomino and so on. In the end, we would have a tree structure containing all solutions as its leaves. This could be useful for performing various search operation over all solutions.

On closer observation, one notices that some solutions contain regions with remarkable shapes, such as the 3×3 rectangle on fig. 3. Such configurations may seem unique at first sight but it is soon obvious that there is quite a lot of them since symmetric shapes can be reflected and rotated. By apply these operations on the grey rectanble, we obtain three more solutions.

Fig. 3. A solution containing a remarkable region.

Wilfred J. Hansen has studied such relationships between the solutions for the 6×10 rectangle (2339 in all). As can be seen in his article, he examines three kinds of transformations that relate solutions: (1) reflecting or rotating a symmetric subpattern; (2) exchanging two subpatterns with the same shape; (3) rearranging two pieces that form the same subpattern in two ways.

Fig. 4. By switching both grey subpatterns we obtain a new solution.

Fig. 5. The F and N pentominoes can tile the coloured subpattern in two distinct ways.

Hansen's study produces 911 classes for the 2339 solutions, 421 classes containing a single solution and a single class with 50 solutions lie at the opposite sides of this classification. 

Others have studied the problem much deeper. Adrian Smith's pages contain all relationships for all rectangles tiled with pentominoes (3×20, 4×15, 5×12 and 6×10). However, he considers more transformation than Hansen. Smith extends Hansen's (3) to shapes tiled by three sub-subpatterns (each of which can be just a single pentomino). Examples can be seen on Smith's website.

I think Hansen's (3) and its extension by Smith are not acceptable and will try to explain my reasoning. 

The essential difference between two solutions is the arrangement of the pieces that form it. Necessarily, there are always common pieces between solutions, the ones left being rearranged. I don't see a reason to limit Hansen's (3) to groups of 2 or 3 pentominoes and the different choices made by himself and Smith proove the arbitrariness of the numbers. But if we extends the limit to 12, all solutions would fall in the same class and whole classification will be pointless. Rearranging a subset is an operation over individual pieces and not over subsets since the geometry of the pieces matters. The other two transformation, explored by Hansen, relie only on subset geometry and the actual pieces that form them do not matter anymore. That is precisely why within a subset the relative position of pieces shouldn't be changed: the pieces are considered glued one to each other and forming a "superpiece", that can be moved, rotated or reflected on its own. It is my understand that classification must explore units of higher order, as is the case in biology. Species are grouped in families and when families are classified, individual species within them are nomore studied as such, only their common characteristics are taken into account.

It might seem at first that Hansen's (2) is also depended on numbers: why do not look for more than two regions with the same shape, that can be swapped? Obviously, if this ever happens, it will be very rare, but still it is worth discussing. The thing is that all such cases would be a combination of two subsets swaps and will anyway fall into the same class.

Fig. 6. This pattern is tiled with the 12 hexiamonds but can be used to think on pentominoes, too. It contains three subpatterns with the same shape. Swapping any two of them will not affect the third. A chain of such swapping can lead to a complete distinct pattern. The same holds true for higher numbers of same shape subpatterns.

For all these reasons, I'll stick to Hansen's (1) and (2) in studying the solution to the mutilated chessboard. In addition, I will consider as distinct transformation a flipping and a rotation under (1) and, furthemore, when many rotations are possible, I'll only consider the one with the smallest angle clockwise (this is relevant only for subpatterns with two axes of symmetry which can be rotated at 90°, 180° and 270°).

The computer programme that I wrote for solving this problem of classification follows the guidelines presented in Hansen's article, but only on an abstract level. My programme treates the problem in a geometry independant way which means that (1) it can deal with pentominoes as well as with hexiamonds or tetrahexes; (2) it is very slow. For the analysis of the mutilated chessboard it needed 35 minutes, which amounts to 123 ms per pair of solutions (there are 65×64×8 / 2 such pairs because each solution has to be compared to all symmetric variants of all the other solutions, avoiding double checks).

For the purposes of this text, solutions have been numbered from 0 to 64 in an arbitrarily way. I will present the classes that they form under the two transformations discussed above using the graph chart, that is shown on fig. 7. Links between solutions correspond to transformations.

Fig. 7. Relations between the solutions to the mutilated chessboard problem.

In his article Hansen speaks briefly about the "bushiness" of classes, i.e. the degree of interconnection of solutions. As he points out, some classes are linear (the longest one here is the chain 44 - 43 - 50 - 51), while others are denser (like the square 0 - 1 - 2 - 3 which is topologically equivalent to a tetrahedron).

It is worth discussing the way these relations are produced within the classes. On fig. 3 can be seen solution 0. Three transformations apply to the grey rectangle: a vertical and a horizontal flip and a rotation at 180°. These correpond to the three edges that join at each vertex of a tetrahedron.

The other square class is produced by two transformations, each of them connecting two solutions. As they do not overlap, all four possibilities exist.

Fig. 8. Unlike the tetrahedron class, there is no single transformation linking the opposite corners of this square. Howerver, each of the two transformation (swapping the grey and yellow subpatterns or reflecting the big grey one) can be applied to each of the four solutions in the class.

The most interesting class is obviously the biggest one. It contains three different sub-classes: a square, a cube and, surprisingly, a pentagon.

Whilst the square and the cube are produced by, respectively, two and three independently operating transformations, the pentagonal ring is an odd mixture of a swapping and four reflections of four different symmetric subpatterns as can be seen in fig. 9.

Fig. 9. A transformation of the grey subpatterns (a reflection or a swapping) leads to the next solution, clockwise.

Solution classes and mathematical groups

To a person not well acquainted with Group Theory, it looks plausible that solution classes are groups in the mathematical sense. However, it turns out that this is generally not true.

A mathematical group is a set of elements on which an operation ☼ can be applied for every pair of elements, this operation resulting in another element of the set (closure), such that (a ☼ b) ☼ c = a ☼ (b ☼ c) (associativity), there exists an element U which acts as 1 in multiplication and for each element of the set a ☼ U = U ☼ a = a (U is the identity element) and each element has an inverse a ☼ b = U.

I got inspired by the Rubik's Cube group. The elements of the group are not the states of the cube but series of transformations (rotations). The operation under which those form a group is the composition operation, i.e. subsequently applying two series of rotations yields another series of rotations. It can be checked that, if we include the empty series, the set and the operation thus defined form a group.

Similarly, let's define a set of series of transformations of the solutions for our puzzle. For some classes these will form groups if and only if each transformation can be applied to each solution that is included in the class (like the tetrahedron class or the square class in fig. 8). However, classes as the pentagonal ring or the string class in fig. 10 contain transformations which apply only to particular solutions and thus the very first condition for a group is not satisfied.

Fig. 10. The longest string class. Applying a transformation to coloured subpatterns leads to the solution to the right.

Thus, classes are groups when they contain: (1) a single solution; (2) a pair of solutions; (3) four solutions linked in a square by only two transformations or in a tetrahedron by three transformations; (4) eight solutions linked in a cube by three transformations; (5) any other configurations that are not present in the case that I have studied and remain unknown to me.

All other classes are actually composed of groups that happen to be linked by random transformations. This is particularly clear in the case of the pentagonal ring which links a square and a cube to form the biggest class for the mutilated chessboard (16 solutions).

Outside the realm of polyominoes

Polyominoes are squary and they cannot produce patterns with symmetries other that reflection about one or two (perpendicular) axes and rotation at 90° or 180° around a centre of symmetry. Polyiamonds and polyhexes, however, have richer symmetry capacities. This means that they can produce more classes of solutions that are groups, namely triangular and hexagonal prisms and chains of such prisms, where the vertices of each prism are linked to the ones of another prism, the bases being parallel.

Fig. 11. Group of solutions, produced by the rotations at 60° clockwise of a hexagonal subpattern (arrows) and the reflections of the same subpattern about one of its axes of symmetry (six parallel edges).

Even if these sets of pieces can produce groups with higher order of symmetry, the overall situation remains exactly the same: solution classes are either groups (in the mathematical sense) or randomly linked groups.

Fig. 12. A complex cluster of groups, that result from a pattern formed by the tetrahexes. One observes three cubes with plenty of common elements, two interconnected triangular prisms (one to the left, the other one to the right) and three pairs, two of which connect the prisms to one of the cubes.

I voluntarily cut it at this point, hoping that further development will follow.

References

Adrian Smith's website, containing his classification of solutions for all rectangles formed by pentominoes: http://www.abasmith.co.uk/pentanomes/pentanomes.html.
Wilfred J. Hansen's article about the classification of the solutions for the 6×10 rectangle: http://www.cs.cmu.edu/~wjh/papers/hexclass.html.
Gareth Rees' website listing all solutions to the mutilated chessboard problem: http://garethrees.org/2015/11/09/exact-cover/.
Donald E. Knuth (2000). ‘Dancing Links’. In J. Davies, B. Roscoe, and J. Woodcock (editors). Millennial Perspectives in Computer Science. Basingstoke: Palgrave Macmillan. pp. 187–214.
Solomon W. Golomb (1996). Polyominoes. Second edition.  Princeton University press.
Ed Pegg Jr.'s website, from which I learnt about the pattern on fig. 6: http://www.mathpuzzle.com/iamond.htm.

Тетрахекс-89

За тетрахексовете, втората форма по брой решения ще наричам тетрахекс-89, или дори ТХ-89. Вече споменах за неѭ, но без да се впускам в подробности. След като приспособих програмата си, за да разпределя сама решенията във фигури, станѫ възможно да разгледам по-отблизко и тази форма. В случайът е интересно да се опитаме да разберем как шампионът при тетрахексовете успѣва да надвие над ТХ-89.

Фиг. 1. Тетрахекс-89.

Изготвих диаграма, която представя всички решения, но без да ги показва. Всѣка точка на фиг. 2 представлява едно решение, а връзките сѫ трансформации. Връзките с посока сѫ ротации на 120° по часовниковата стрелка. Те сѫ възможни единствено при наличие на участък с три оси на симетрия, освен централната симетрия (повечето участъци с централна симетрия имат само една ос на симетрия, поради което е възможна ротация само на 180°, трансформация, която наричах завъртане; липсата на централна симетрия, но наличие на осева, води до възможност за трансформацията отразяване, която е най-често срещаната). Когато за две решения съществуват две различни трансформации, които ги превръщат едно в друго, това е отбелѣзано с цифрата 2 върху връзката (става въпрос за размѣна на подучастъци на участък, който си има симетрия; двете трансформации се оказват еквивалентни).

Фиг. 2. Отношения между решенията за ТХ-89. За добра четимост на числата, трѣбва да се кликне на картинката.

Какви наблюдения могѫт да се направѭт въз основа на диаграмата? Най-напред, изолираните решения сѫ повече, отколкото при ТХ-120, а именно 11 срещу 8. Най-голѣмата група обаче е с по-малка мощност (16 срещу 29 при ТХ-120). Както и при ТХ-120, сѫществува само една група с участък, който може да се върти на 120°, но при ТХ-120 този участък сѫществуваше в две различни разновидности. При ТХ-89 той води до групата долу в дѣсно на диаграмата, която съдържа нещо като триѫгълна призма включваща шест решения, към която се прикачват две разклонения, едното кѫсо и съдържащо само едно решение (16), а другото нишковидно, от две решения (8 и 85). Най-голѣмата (16 реш.) и втората (10 реш.) групи съдържат трансформации, които не водѭт до нови решения, а образуват квадратите с пресечени диагонали. На всичкото отгоре, в групата с 10 решения имаме двойни връзки, което сѫщо е загуба на потенциални нови решения. 

Да разгледаме по-отблизо нѣкои елементи от диаграмата.

В група I (горнийът лѣв ѫгъл на диаграмата) имаме първи квадрат с пресечени диагонали. Той се дължи на участъкът, представен на фиг. 3, и който има две оси и център на симетрия.

Фиг. 3. Участъкът, чиито три трансформации пораждат само четири решения.

Резултатът от последователното прилагане на двете отражения около осите обаче е еквивалентен на отразяването около центърът на симетрия. Така вместо 2³ имаме 2⁴ решения, породени от този участък.

В група II (долу в лѣво на общата диаграма) имаме различна ситуация, съответстваща на другийът квадрат с диагонали в диаграмата на фиг. 2.

Фиг 4. Сивийът и жълтийът участъци могѫт да се разменѭт. Въпреки че и двата имат осева симетрия, единствено жълтийът поражда нови решения при завъртане.

Ако жълтийът участък на фиг. 4. сѫщо имаше несиметричен вѫтрешен строеж, конфигурацията щеше да поражда 8 решения, положение, което присѫстваше в ТХ-120.

Ред е на група III, която съдържа участъкът с три оси на симетрия. Нека отбележим, че при наличие на повече от една ос на симетрия, пресечната им точка е център на симетия. Затова един участък може да породи 1, 2, 4 или 6 различни решения, без промѣна във вѫтрешнийът си строеж.

Решаващ в случайът се явява вѫтрешнийът строеж на участък, който присѫтства в решенията както на ТХ-89, така и на ТХ-120, и който съм показал на фиг. 5.

Фиг. 5. Участъците с три оси на симетрия в решенията на ТХ-89 и ТХ-120.

Решаща е сивата част, която при ТХ-89 е вѫтрешно симетрична и отразяването ѝ не води до промѣна, докато при ТХ-120 е обратното. Поради тази особеност ТХ-89 губи шест решения.

Ако обобщим изводите за трите най-големи групи при ТХ-89, загубата на потенциални решения е 4 + 4 + 6 = 14. Без тези загуби, ТХ-89 щеше да се казва ТХ-112 и от ТХ-120 щѣхѫ да ѭ делѭт само осем решения.

Искам да обърнѫ внимание и на звездовидната група от четири решения в най-долнийът десен ѫгъл на общата диаграма. За разлика от съседната ѝ квадратна група, в неѭ работѭт три трансформации, т.е. с една повече, но несъвместими помежду си: става въпрос за три частично застѫпващи се симетрични участъка.

Фиг. 6. Три частично застѫпващи се симетрични участъка в звездовидната група. Общата и за трите фигурка е отбелѣзана в жълто (Пчела).

Ако два участъка не се застѫпвахѫ или единийът застѫпваше другийът напълно, групата щеше да съдържа пет решения; ако нито два от трите участъка не се застѫпвахѫ частично, решенията щѣха да сѫ осем и да образуват куб в диаграмата.

Форма от тетрахексове с най-много решения

Вече на нѣколко пѫти писах за форми с най-много решения за определен комплект от фигурки (пентомина и хексиаманти). И в двата случая става въпрос за набори от дузина фигурки и за форми с брой решения от пети порядък (10⁵). Когато пуснѫх програмата си да проверява формата на Рийд-Хамлин (за хексиамантите), откриването на 14 600-те решения ѝ отне малко над 20 минути. Ясно е, че нѣма как да правѭ експерименти в това поле, нито пък с набори от повече фигурки, като например хептиамантите. Реших обаче да си поиграѭ с тетрахексовете, които макар и да сѫ само седем, образуват интересни форми.

Наборът от фигурки може да бѫде видѣн тук. 

Избран бе методът на... налучкването. Допуснѫх, че, както е при пентомината и при хексиамантите, формата трѣбва да е сбита и несиметрична. Първото ми предположение се оказа и най-успешното, защото и така не можах да надминѫ 120 решения, които се получават при формата на фиг. 1.

Фиг. 1. Форма със 120 решения, най-доброто, което успѣх да постигнѫ. Вторийът резултат е 89 решения, с преместване на стърчащото шестоѫгълниче на една позиция надолу и в дѣсно.

Тръгнѫх от резултатите от машиннийът анализ на решения и с доста търпение и взиране стигнѫх до следните резултати относно класификацията им:

Група	Брой решения	Брой трансформации
I	29	16* (11* отразявания, 3* завъртания и 2 размени)
II	15	8 (5 отразявания, 2 размени и 1 завъртане)
III	9	9* (6* отразявания, 2* завъртания и 1 размѣна)
IV	7	6* (отразявания)
V	7	6* (отразявания)
VI	5	4 (отразявания)
VII	5	4 (3 отразявания и 1 завъртане)
VIII	5	3 (отразявания)
IX	5	3 (отразявания)
X	3	2 (отразяване и завъртане)
XI	3	2 (отразявания)
XII	3	2 (отразявания)
XIII	2	1 (отразяване)
XIV	2	1 (отразяване)
XV	2	1 (отразяване)
XVI	2	1 (отразяване)
XVII	2	1 (отразяване)
XVIII	2	1 (отразяване)
XIX	2	1 (отразяване)
XX	2	1 (отразяване)
XXI - XXVIII	1	0

Представянето на групите ще започнѫ от долната част на таблицата. Отбелѣзаните със * числа ще бѫдѫт коментирани по-долу.

Независими решения

Те сѫ едва осем, което прави 1/15 или 7% от всички възможности. N° 79 съдържа симетричен участък, който се отразява в самийът себе си. Нѣма как и иначе да бѫде, разбира се, защото ако участъкът не беше с вѫтрешна симетрия, щеше да доведе до свързано решение.

Фиг 2. Осемте решения, които не сѫ свързани с никое друго.

Двойки решения

Те сѫщо сѫ осем. Във всички случаи става въпрос за отразяване на участък, съставен най-често от две фигурки.

Група XX.

Група XIX.

Група XVIII.

Група XVII.

Група XVI.

Група XV.

Група XIV.

Група  ΧΙΙΙ.

Фиг. 3. Единствено групи XV и XVII използват трансформация на участък с повече от две фигурки, като всеки пѫт има подучастък със симетрична форма, но който не може да бѫде въртѣн независимо поради вѫтрешната си симетрия. В половината случаи променящийът се участък е съставен от Вълна + Червей.

Би могло да се зададе следнийът въпрос: какво точно е една трансформация? Две различни трансформации ли сѫ използвани в групи XVI и XIX, при положение, че става въпрос за участъци с еднакви очертания? Струва ми се редно тези две завъртания да бѫдѫт различавани, защото ако решим да дефинираме участъкът само с очертанията му, би излѣзло, че и отбелѣзаните в жълто участи в групи XIII и XX подлежѫт на трансформация. Така всички двойки решения се получават с общо пет различни трансформации, една от които се използва четири пѫти, другите по веднѫж.

Група XVII представлява интерес, защото съдържа симетричен участък, по-голѣм от оцветенийът (ако добавим Гредата). Да, но завъртането на този уголемен участък не би променило положението на Гредата, ето защо тя не се включва в трансформацията.

Тройки решения

И в трите групи има едно решение, върху което могѫт да бѫдѫт приложени две различни трансформации, но върху застѫпващи се участъци. Поради тази причина прилагането на едната трансформация блокира другата и общийът брой решение е не четири, а три. 

Група XII.

Група XI.

Група X.

Фиг. 4. Централното решение, върху което сѫ възможни две трансформации, не е оцветено.

Интересно е, че една от двете трансформации винѫги е отразяване на съчетанието Вълна + Червей, което вече видѣхме четири пѫти в двойните решения. Срещаме и първото завъртане, в група X, която притежава участък с централна симетрия.

Петорки решения

Ако в нѣкоя от предните три групи двете трансформации не засѣгахѫ застѫпващи се участъци, щѣхме да имаме и групи с четири члена. Нещата обаче не стоѭт така и бройът групи от пет решения е по-голѣм от бройът групи с три решения.

Група IX.

Група VIII.

Група VII.

Група VIII.

Фиг. 5. Петорки решения. Нито един случай на участък Вълна + Червей.

Както добре се вижда от картинките на фиг. 5, петорките решения се разпадат на два подтипа: с три трансформации (групи IX и VIII) и с четири трансформации (VII и VIII). Вторийът подтип всѫщност е по-прост: след прилагането на една трансформация става възможно прилагането само на една друга. Получава се верига от трансформации, която обаче не е циклична.

Другийът подтип е по-интересен, защото при него две трансформации върху незастѫпващи се участъци водѭт до четворки решения (представени в квадрат), върху едно от които може да се приложи трета трансформация (представена встрани).

Седморки решения

Тези две групи дават общо 14 решения, което е повече от 10% от общийът брой.

Група V.

Група IV.

Фиг. 6. И при двете седморки се наблюдават големи участъци (в сиво) със симетрични подучастъци (в жълто).

И двете групи функционират по следнийът начин: решенията съдържат голѣм симетричен участък, който съдържа на свой ред два симетрични подучастъка, които се застѫпват помежду си. В рамките на големийът участък, двата малки дават три решения, както вече видѣхме при групи X-XII. Самийът той обаче може да бѫде отразен, което удвоява решенията, към които се прибавя още едно, разрушаващо симетрията на големийът участък.

Поради причините, посочени по-горе, всѣка промѣна на вѫтрешната структура на големийът участък ни принуждава да броим отразяването му като нова трансформация. Ето защо и двете групи имат 6, а не 4 трансформации, колкото бихѫ се получили ако не обръщаме внимание на строежът на големийът участък.

Деветорка решения

Само една група дава девет решения, които представляват 7,5% от общийът брой, повече отколкото всички независими решения взети заедно.

Фиг. 7. Група III, единствената деветорка от решения и появата на първата размѣна на еднакви участъци (трансформация между решения 93 и 98; участъците сѫ показани само за 93).

Група III съчетава две стратегии за получаване на четворки решения: незастѫпващи се симетрични участъци (както при петорките VIII и IX) и симетричен участък в симетричен участък (седморките притежаваха два застѫпващи се участъка в голѣм, което даваше шесторки решения). Първата конфигурация се наблюдава при решения 61, 59, 95, 93, а втората при 98, 57, 90 и 78. Във вторийът случай пак трѣбва да броим три вместо две трансформации, защото отразяването на големийът участък е различно според позицията на подучастъкът. Към това трѣбва да се добавѭт и две завъртания на големийът участък, които свързват 98 със 78 и 90 с 57.

Към тези седем трансформации се добавят още две: едната е отразяването, което свръзва решения 60 и 61, а другата е размѣната на еднакви участъци между 93 и 98. Последната служи за връзка между двете четворки.

Петнадесеторка решения

Тази група съдържа 1/8 или 12,5% от всички решения. Свързаността между решенията е усложнена, което се отразява и на диаграмата, представена на фиг. 8.

Фиг. 8. Всички връзки между решения сѫ показани с черни линии.  Общийът за 89 и 91 участък не е оцветен по специален начин.

Сложността на изображението идва от осморката решения 101, 102, 19, 20, 96, 47, 97, 46, която образува куб. Това се дължи на три трансформации, които могѫт да бѫдѫт прилагани независимо една от друга: две завъртания на участъците с форма на капка (единийът съставен от Пистолет + Арка, оцветен винѫги в жълто, другийът от Пчела + Червей, винѫги в сиво), и размѣната на тези два участъка един с друг. В пет от осемте върха на този виртуален куб се образуват по-големи симетрични участъци. Завъртането на всеки един от тези големи участъци разрушава само едната капка и отразяването на другата създава допълнителна връзка между решенията (18 и 105, най-влѣво, 103 и 104 най-горе и 91 и 70 вѫтре). Към тези общо 6 трансформации (три в кубът и трите отразявания на големи симетрични участъци; завъртането на "оцелѣлата" капка не е нова трансформация) се добавя възможността за размѣна на два участъка в решение 97, което води до 89, както и завъртането на един симетричен участък, общ за 89 и 91 (Перка + Червей + Пистолет), и общо осем трансформации.

Група с най-много решения

Обхващайки почти една четвърт от всички решения, група I е с най-сложна геометрия, както е видно от фиг. 9.

Фиг. 9. Трансформациите, които свръзват нѣкои решения, не сѫ отразени с черти. Става въпрос за четворката 27, 42, 35, 41 и за двойките 31 и 24 и, по-долу, 1 и 5. Трансформацията между 31 и 1 е отбелѣзана встрани от свързващата ги черта.

Групата може да бъде мислена като съставена от две подгрупи, едната отразена с четири вписани квадрата в горната част на фиг. 9, а другата с дванадесетоѫгълникът в долната част. Към дванадесетоѫгълникът трѣбва да се свърже реш. 66, в долнийът лѣв ѫгъл, а към квадратите двойката реш. 24 и 31. Връзката между двете подгрупи се осѫществява посредством двете решения 1 и 5.

Анализът на първата подгрупа е по-лесен. Тя се състои от три свързани в триѫгълник куба. Първийът е образуван на сѫщийът принцип както в група II: два еднакви и взаимозаменяеми участъка, образувани от Вълна + Пчела (сиво) и Пистолет + Арка (жълто), търпѭт поотделно по едно отразяване (решения 27, 42, 35, 41, 28, 26, 34 и 25). Този първи куб има обща стена с друг куб, образуван от три трансформации: завъртане на съчетанието Пистолет + Арка и на две други фигури, една от които напълно обхваща предната, а другата, по-малка, която не се застѫпва с неѭ (решения 28, 26, 34, 25, 4, 7, 3 и 6). Третийът куб има обща стена с вторийът (реш. 3, 34, 25 и 6) и общ рѫб с първийът (34 и 25). В подгрупата действат общо шест трансформации, една от които размѣна.

Нещата сѫ по-заплетени при втората подгрупа, защото тя се основава на форма от три фигурки, която има три оси на симетрия, плюс централна симетрия. За тази форма приемам само две трансформации: завъртане на 120° по посока на часовниковата стрелка и отразяване спрѣмо вертикалната ос на симетрия. Тъй като самата форма търпи трансформация на вѫтрешнийът си строеж, горните трансформации трѣбва да се удвоѭт. Така и в тази подгрупа действат общо пет трансформации.

Ако сведем диаграмите до граф, в който е отбелѣзан просто номерът на всѣко решение, подгрупата съответстваща на дванадесетоѫгълникът ще придобие видът представен на фиг. 10.

Фиг. 10. Подгрупа на дванадесетоѫгълникът. Стрелките съответстват на завъртания.

Трансформацията завъртане, за разлика от всички останѫли, не се анулира при повторение. Това е така, защото формата има тройна симетрия.

Геометрично представяне на връзките между решенията

Както станѫ очевидно от разнообразните фигури, връзките между решенията се поддават на лесна геометрична интерпретация. Единствено изключение е подгрупата на дванадесетоѫгълникът, която остава трудна за възприемане. Всички трансформации, чието двойно прилагане води до анулиране, могѫт да бѫдѫт изобразявани като вектори, чиито представители образуват ребрата на паралелепипеди. Четворките решения, свързани от две трансформации, се превръщат в квадрати, осморките, породени от три трансформации, в кубове.

Фиг. 11. Група II, изобразена като куб, към който сѫ прикачени три успоредника и една отсечка.

Доброто изобразяване позволява лесно да бѫдѫт видени различните трансформации. Така например, от фиг. 11 е видно, че в група II действат седем трансформации, и че една и сѫща свръзва реш. 19 със 101 и 18 със 106, тъй като ребрата между тѣх сѫ успоредни.

Неясно остава как трѣбва да се подходи към завъртането. Би било красиво, ако се намери начин дванадесетоѫгълникът от група Ι да бѫде изобразен като икосаедър или като нѣкое полуправилно пространствено тѣло.

Допълнение от 19 юли 2019. Изобразяване като управилно тѣло е невъзможно, защото трансформациите не сѫ симетрични: ротациите водѭт до тройки от решения, а отразяванията и завъртанията на 180° до двойки, четворки, осморки и (може би) други степени на 2. Дванадесетте решения от група I образуват две триѫгълни призми, чиито съответстващи върхове сѫ свръзани в двойки чрез завъртането на капката вѫтре във въртящийът се участък.

Допълнение от 20 юли 2019. Вече е възможно да качѫ пълната диаграма на връзките между решенията.

Фиг. 12. Връзките между всички решения. Диаграма достойна за съзерцание.

Форма на Рийд-Хамлин

На сайтът на Ед Пег (http://www.mathpuzzle.com/index.html), кѫдето сѫ публикувани и събрани изключително много интересни пъзли, се намира и формата от хексиаманти с най-голѣм брой решения, открита от Майкъл Рийд (Michael Reid) и Патрик Хамлин (Patrick Hamlyn), в отговор на въпрос от Кристофър Монктън (Christopher Monckton), за чийто пъзел от квадрати и триѫгълници вече писах малко. Вече писах и за формата от пентомина с най-голѣм брой решения. Формата на Рийд-Хамлин има 14 600 решения и представена на фиг. 1.

Фиг. 1. Формата, открита от Рийд и Хамлин и за която има 14 600 решения с хексиаманти, най-големийът известен засега брой.

Както и при формата на ван де Ветеринг, впечатление прави липсата на симетрия. Припомням, че симетрията намалява общийът брой принципно различни решения, защото елеминира всички решения получени чрез завъртане или отразяване. За сведение, моята програма намери сто решения за 7,4 секунди, което означава, че намирането на всичките 14 600 решения би ѝ отнело около 20 минути. Нѣкой пѫт ще пробвам, най-малкото за да се уверѭ във верността на числото (и в способностите на програмата си).

Решения, свързани чрез симетричен участък

По-долу прилагам нѣколко примера за свързани решения, по механизъмът, който вече описах. Важните участъци сѫ в сиво.

Фиг. 2. Нѣколко взаимносвързани решения за формата на Рийд-Хамлин. Първите две решения преминават едно в друго чрез отразяване, вторите две чрез завъртане. На третийът ред е показано само едно решение, което съдържа симетричен участък с по-скоро учудващ контур и който може да бѫде отразен, за да получим ново решение.

Програмата ми явно не е толкова глупаво, за колкото ѭ имах, защо намира и симетрични участъци с дупки, като показанийът на фиг. 3.

Фиг. 3. Симетричен участък с дупка в едно от решенията за формата на Рийд-Хамлин. Отразяването му дава ново решение.

И един интересен въпрос: какъв е най-големийът възможен симетричен участък за тази форма? Отговорът изглежда е 60 триѫгълничета/10 фигурки, както съм показал на фиг. 4, получена чрез изрѣзване на несиметричните "излишъци" в изходната форма.

Фиг. 4. Най-голѣм възможен симетричен участък за Рийд-Хамлин. Това разрѣзване само по себе си дава 500 решения за цѣлата форма, които съответстват на 250 принципно различни решения за сивийът участък. Отразяването им дава 500-те за формата.

Възможни сѫ и участъци с многократна симетрия. На фиг. 5 е показан пример с четирикратна симетрия. Сивийът участък може да бѫде нареден по един единствен начин, поради което схемата води до точно четири различни решения за формата на Рийд-Хамлин.

Фиг. 5. Участък с четирикратна симетрия (и завъртане, и отразяване). Възмножно е само едно принципно решение за самийът участък, което води до четири различни за цѣлата форма.

Решения, свързани чрез замѣна на еднакви участъци

По-редки, но не по-малко интересни, сѫ решенията, които съдържат два (или повече!) участъка с еднаква форма. Това позволява участъците да се разменят и по този начин да се извеждат нови решения. За съжаление, програмата ми все още не борави съвършено с тази задача и понѣкога дава лъжливи резултати (а понѣкога може би пропуска истински, което е нѣкак си по-обезпокоително). Все пак, ето нѣколко интересни положения.

Фиг. 6. Всѣко едно от тези две решения съдържа два еднакви по форма участъка, които могѫт да бѫдѫт разменени. Горе е нужно отразяване, а долу просто завъртане 60°.

Случайно намерих и решение с три еднакви участъка. То поражда пет нови решения, чрез всички възможни пермутации на участъците.

Фиг. 7. Три еднакви участъка. Единийът е образуван от шестоѫгълникът и пѫтнийът знак (имена на фигурките), които, подредени по различен начин, дават и сивийът участък горе на фиг. 6.

Вероятно сѫществуват и участъци с четири еднакви участъци, разпределени в две различни двойки. С примери засега не разполагам, нѣмам и идея по какъв програмен пѫт да търсѭ.

Еднаквите участъци на теория могѫт да сѫ с максимален размер от шест фигурки. Заради начинът, по който е направена, моята програма може да търси само до пет. Намирала е обаче само до три фигурки, единственийът пример е показан на фиг. 8.

Фиг. 8. Еднакви участъци, съставени от три фигурки.