събота, 2 ноември 2019 г.

Some Fully Solved Heptiamond Shapes

The twenty-four Heptiamonds can form many interesting shapes but it takes a lot of time to discover all solutions for most of them. Here I will present only three shapes for which I have been able to calculate all solutions.
List of shapes on this page:

Hexagon with Seven Holes

This shape has been discovered by J.H.Hindriks and be seen on his website or on David Goodger's Puzzler. It has exactly 686 solutions that took my computer more nearly 24 hours to calculate. The shape has axial and six-rotary symmetry which means that each solution has 12 symmetric twins. With these in mind, it is easy to see that the X piece can be placed in just seven different positions. Each of them leads to solutions, as is shown below.
First position for X piece -- 87 solutions.

Second position for X piece -- 10 solutions (least of all positions).

Third position for X piece -- 68 solutions.

Fourth position for X piece -- 19 solutions.

Fifth position for X piece -- 228 solutions.

Sixth position for X piece -- 12 solutions.

Seventh solution for X piece -- 262 solutions (most of all positions). The solution on Puzzler belongs to this category.

Hexagon with Seven Holes - Second Form

This shape is also an invention of J.H.Hindriks but unlike the previous one, there are only four possible positions for the X piece. On the other hand, the total number of solutions is nearly ten times bigger: 6002.

First position for X piece gives 1494 solutions.

Second position for X piece gives 2799 solutions, which is the biggest number.

Third position for X piece gives the least number of solutions, only 415.

Fourth position for X piece gives 1295 solutions.

Gasket with Three Holes

This shape comes from Puzzler and it has three very big holes which leads to a very smaller number of solutions. In fact, there are only 9 of them. Further more, these divide into three groups of, one of just one solution, and two of four solutions each. I have shown below a representative of each group. Symmetric regions, which can be rotated to give the other solutions in each group, are coloured.

Mirror reflections of the two red regions give three more solutions in each case. In his list of terms, J.H.Hindriks calls the upper region a Clover Leaf and the lower one a Gemstone. Notice that the only difference between these two groups is the three-piece regions in the lower left corner, composed of the G, N and T pieces in two distinctively different ways.

This solution forms a group on its own.

A Tetrahex Twin Shape 

David Goodger has remarked that the total surface of the twenty-four Heptiamonds is exactly equivalent to 28 hexagons each comprising six triangles. This means that shapes formed with the Tetrahexes can be copied with Heptiamonds. It would be interesting to the have the complete list of such shapes. I think it would be of human size. For the time being, I took a Tetrahex shape with a unique solution and high symmetry (discovered by Abaroth and present on Puzzler too). It turned out that the Heptiamond twin has exactly three solutions, which is the least I know for a Heptiamond shape at all. Are there symmetric Heptiamond shapes with just one solution?
Abaroth's Tetrahex shape and its unique solution is on the right. On the left is one solution with Heptiamonds and another one, which can be transformed by mirroring the red regions. All in all, only three Heptiamond solutions.

понеделник, 21 октомври 2019 г.

Solutions analysis for Hexiamonds champion shape


The availability of computer solvers for polyforms has led to the possibility to know exactly how many solutions every shape has (except for large sets of polyforms where even computers need too much time). As Eric Harshbarger points it out in his article, this opens new fields of investigation, namely searching for the shape with most solutions for each set of polyforms. It is useful to name such shapes Champion shapes. They are not difficult to find for small polyform sets, such as the tetrominoes, the pentiamonds or even the tetrahexes.
 Polyform set  Champion shapesNumber of solution




Studying champion shapes seems to me an important point of the more general study of a particular polyform set. In fact, searching for champion shapes have been performed for Pentominoes and Hexiamonds, by Aad van de Wetering and by Michael Reid and Patrick Hamlyn respectively, yielding results with 16720 and 14600 solutions. Although there isn't any proof these are actually the champion shapes for the respective sets, probabilities for this being so are high. It seems fare to me to name these shapes after the persons who discovered them.

 Polyform set  Champion shapesNumber of solution
van de Wetering's shape
 Reid-Hamlyn's shape

Champion shapes study

The first step in studying champion shapes is obviously just finding them. I don't know of any other method than educated guess. Some properties of champion shapes are easy to formulate:
(1) they are assymetrical; in fact, symmetry reduces the number of unique solutions;
(2) they are compact, tending to be slightly elongated;
(3) their borders are overall straight but one or two little protrusions allow for fitting gnarled pieces.

Things get much more interesting once the actual solutions are looked at. Even for very small polyform sets which allow for little combination, remarkable relationships between individual solutions can be observed, as illustrated by the Pentiamonds on fig. 1.
Fig. 1. Pentiamonds champion shape #1: two of the solutions are related by the mirror reflection of a region of two pieces.
If we assign a number to each solution and if we represent them as the nodes of a graph and the relations caused by symmetric regions as the edges of this graph, we obtain fig. 2 for the Tetrominoes champion shape (graph visualized with https://graphonline.ru).
Fig. 2. Graph representation of the relations between the solutions for Tetrominoes champion shape. Note that every solution is related to at least one other. Solutions form groups which are seen here as unconnected subgraphs.
For bigger polyform sets, there are solutions which are related in other ways than symmetric regions transformation. This has been studied mostly for Pentominoes and, precisely, for rectangle shapes. I have already provided information on the topic when I analysed the relations between the solutions to a mutilated chessboard problem for Pentominoes. I have also published an analysis of the Tetrahexes champion shape (in Bulgarian); at its end is a graph representation of all the solutions and the relations between them. With the present post I want to share my findings about Reid-Hamlyn's shape.

Reid-Hamlyn's shape analysis

As with the chessboard problem, I analyse only symmetric and swappable regions, both exemplified on fig. 3.
Fig. 3. Reid-Hamlyn solution #7000. Yellow regions are swappable while the gray one is symmetric.
The total number of solutions being 14600, I couldn't afford to compare them one by one in pairs in order to determine whether there are some interesting relations. What I did instead was the following:
(1) Scan all solutions to determine whether they contain symmetric regions;
(2) Scan all solutions to determine whether they contain swappable regions;
(3) Perform transformations on the results of (1) and (2) to determine to what solutions they lead.


I found that the 14600 solutions form 3514 groups, containing from 1 to 1679 solutions. These results are summarized on fig. 4. It is worth noting that among small groups, those with an even number of elements are more numerous than those with an odd number of elements (groups of just one element are obviously an exception to this).

Groups are sorted by decreasing number of solutions and then number. Thus, group #1 contains 1679 solutions, group #2 has 289 and so on; groups of the same size are numbered arbitrarily.
Fig. 4. Number of groups plotted against size of group. Noth axes use logarithmic scale. Only one group has more than 1000 members (1679); second in size group contains just 289 solutions. 1348 solutions are isolated and form groups on their own while 1022 solutions are grouped in pairs.

Symmetric regions

Summarized data on symmetric regions is presented below.

Numbers of solutions with symmetric regions
                        Regions per solution
Pieces per region
5 4 3 2 1 0 Region shapes
2 1 36 462 2726 6089 5286 14
21 371 1656 4341 8211 65

32 543 3146 10880 77

2 324 2066 12209 82

11 133 1531 12926 55

1 102 1821 12677 69

26 438 1282 12855 39

75 2410 11751 27
10 364 14236 1

For completeness, the table contains information on numbers of solutions which do not contain symmetric regions. There is only one solution which contains five different symmetric regions of two pieces:
Fig. 5. Solution #4373 contains five symmetric regions of two pieces. Some of them overlap. Notice, on the left, a symmetric regions of three pieces (Bar, Hexagon and Butterfly).
There is only one symmetric region shape of 10 pieces. It is contained in 364 solutions. This large number is due to the various ways the shape can be formed.
Fig. 6. Solution #172 contains a symmetric region of 10 pieces.
There is some anomaly regarding symmetric regions of 8 pieces: there are 26 solutions which contain three such regions and only one solution containing three symmetric regions of 7 pieces. Looking at the actual solutions provides an easy explanation.
Fig. 7. Solution #7792 is the only one to contain three symmetric regions of seven pieces. Notice that just one piece (Signpost, up right corner) doesn't belong to any of these.

In fact, all solutions with three symmetric regions of eight pieces contain a big side 3 hexagon; the symmetric regions are subsets of this hexagon: each time a symmetrically situated piece is omitted as can be seen on fig. 8.
Fig. 8. Omitting the yellow pieces, one at a time, strips the big hexagon to a symmetric regions of eight pieces.

Swappable regions

Numbers of solutions with swappable regions
                             Pairs per solution
Pieces per region
5 4 3 2 1 0 Regions shapes
2 1 15 236 596 4277 9475 49

5 388 14207 34

204 14396 14
5 1 14599 1

Surprisingly, there is a solution which contains five pairs of swappable regions, all of them formed of two pieces:
Fig. 9. Solution #7993 and its five pairs of swappable regions.
There is exactly one pair of swappable regions of five pieces:
Fig. 10. Solutions #5189 and #11727 are the only pair linked by the swapping of regions of five pieces.

Group #1 structure

It is important to understand how a single group can contain five times more solutions that the second in size. This is due to an appearance of the side 3 hexagon that was already mentioned above. In fact, this hexagon can be fitted within Reid-Hamlyn's shape in an unique way which fixes the Sphinx piece and brings into existance a trapezium that can be formed with the use of a unique pair of pieces (Yacht and Lobster).
Fig. 11. The only possible way to fit the side 3 hexagon within Reid-Hamlyn's shape. Obviously, the trapezium can be mirrored.
There are exactly 51 possible ways to fill the big hexagon and these break down into eight groups of very unequal sizes: the biggest one contains 40 solutions, the second one 4, the third just 2 and the five left contain single solutions. The biggest group is partially so because of a smaller side 2 hexagon, as shown on fig. 12a.

Fig 12a. A smaller side 2 hexagon within the bigger one.

Since the trapezium can be mirrored and the hexagon can be rotated six times at 60° and be mirrored itself, the eight aforementioned groups will lead, for Reid-Hamlyn's shape, to groups of at least 24 times bigger sizes: 40 × 24 = 960, 4 × 24 = 96, 2 × 24 = 48 and 1 × 24 = 24 respectively. It is not obvious that the 40 elements group for the big hexagon is the chief responsible for the size of the 1679 elements group for Reid-Hamlyn's shape. The additional solutions in this group are linked by transformations that break the side 3 hexagon. The way this happens is easier to see for an isolated solution for the big hexagon. One such is shown on fig. 12b: it gives rise to group #50, containing 28 solutions, represented by the graph on fig. 13.
Fig. 12b. Isolated solution for the big hexagon.
Fig. 13. Graph representation of group #50. Only rotations at 60° of the hexagon in fig. 12 are represented (arrows).
The vertical links on fig. 13 result from mirroring the trapezium. Solutions #2776 and #2775 (up in the middle) and #8742 and #8741 (at the right) result from transformation that involve the Sphinx piece; these break the side 3 hexagon but preserve the trapezium, as illustrated on fig. 14 below.
Fig. 14. Mirroring the gray region breaks the hexagon but preserves the trapezium.
Group #1 is so big because of the rich structure of the hexagon it contains. When this hexagon is broken, there are still symmetric regions within it which are preserved, one of which can be the smaller hexagon shown on fig. 12a. See below for a chain of transformations within group #1.
Fig. 15. Solution #14338 (at the left) contains a symmetric region (in gray) which breaks the big hexagon but preserves the smaller one (in yellow). This leads to solution #14542 (in the middle) which now has its one symmetric regions (in gray); its transformation moves the trapezium, preserving it within solution #14539 (at the right) for further transformations that will expand group #1.


As has been seen, the key to Reid-Hamlyn's shape plethora of solutions is that it includes a side 3 hexagon in a way leaving space for a further symmetric region (a small trapezium). Further more, it is important that this hexagon contains, on its own, another hexagon. In fact, every hexagonal regions leads to 11 more solutions, obtained via rotation and mirroring.  Unsurprisingly, just changing the Sphinx position leads to another solution rich shape (13881 solutions, fig. 16).
Fig. 16. Shape with 13881 solutions, i.e. 719 less than Reid-Hamlyn's. The only difference is the position of the little protrusion on the right which allows for a different position of the Sphinx piece.
It is necessary to study in a similar way other champion shapes (for instance, van de Wetering's one) in order to gain deeper knowledge of the way they function. Hexagons turn out to be the key to success in the case of the Hexiamonds but we shouldn't forget that this is particularly favoured by the number of elements in each piece (six) which allows to construct side 2 and side 3 hexagons. This is not the case for Heptiamonds where no hexagon is possible. Investigation in Heptiamonds shapes is greatly obstructed by the enormous number of the solution they have. It doesn't seem unlikely that Heptiamonds champion shape has more than one million solutions.

Appendix: Interesting group structures

Although this doesn't help understand how Reid-Hamlyn's shape manages to have so many solutions, it is still interesting to show some small groups structures because of their aesthetic value.

When a group contains two symmetric regions which do not interect (but one of them can be totally included within the other one) this leads to a square group, such as #886:
Fig. 17. Shown above is solution #388 which contains two symmetric regions. On the right is the structure of group #886 to which it belongs.
Three independent regions lead to a cube structure. If we have four independent binary transformations, we obtain a tesseract (4D hypercube) structure, as in group #102 which contains three symmetric regions and a pair of swappable regions included within the symmetric ones:
Fig. 18. Solution #7126 contains three symmetric regions and a pair of swappable ones (marked with red dots). It belongs to group #102 which has tesseract structure.
Many groups contain agglomerates of cubes. But there can also be junctions of tesseracts, as in group #41.
Fig. 19. In group #41 two tesseracts share a cube while one of them shares a square with a cube (on the top). To this cube is attached a tail of four squares.
Two other kinds of groups could be studied: string and ring groups. Strings are solutions linked by transformations that destroy one another transformation creating a new one. Rings are similar to strings except that there are no end solutions containing one unique transformation.
Fig. 20. Group #898 is a ring of three elements and group #136 contains a ring of five solutions.

събота, 14 септември 2019 г.

Макроструктури въ пъзлитѣ отъ рода на пентомината и хексиамантитѣ

Въ търсене какво да се реди съ пъзлитѣ на рода на пентомината и хексиамантитѣ, първата идея, която хрумнала, била за прости форми съ симетрична форма, като най-симетричнитѣ форми сѫ най-престижни. Така напримѣръ, отъ пентомината се редятъ правоѫгълници, защото квадратитѣ сѫ невъзможни съ 60 квадратчета. Възможенъ е квадратътъ 8 × 8 съ дупка 2 × 2 точно въ центъра, но формитѣ съ дупка сѫ второразрядни. При хексиамантитѣ е невъзможна фигура съ шесть оси на симетрия, но пъкъ голѣма популярность има форма, която може да бѫде завъртѣна шесть пѫти на по 60° (вж. фиг. 1, въ лѣво). Едностраннитѣ хексиаманти, за които сѫществува форма съ шесть оси на симетрия, сѫ изслѣдвани дори по-рано отъ самите хексиамантитѣ, най-вѣроятно именно поради наличието на тази форма (вж. фиг 1, въ срѣдата). При хептиамантитѣ такава форма сѫщо сѫществува и сѫщо е популярна (фиг. 1, въ дѣсно). 

Фиг. 1. Формата въ срѣдата нѣма дупка, дебело очертаниятъ шестоѫгълникъ е участваща въ пъзела фигурка.
Слѣдъ като се провѣри осѫществимостьта на разнообразнитѣ симетрични форми, правятъ се опити въ областьта на макроструктуритѣ, за които искамъ да говоря: редятъ се форми, които сѫ съставени отъ голѣми блокове, които сѫ на свой редъ по възможность симетрични. Така напримѣръ, при фигуркитѣ съставени отъ квадрати се пробватъ форми, съставени отъ по-голѣми квадрати. Желателно е да се използватъ всички фигурки отъ набора, но това не винаги е възможно. Пентомината могатъ да образуватъ максимумъ петь голѣми квадрата съ страна три и обща площь 45 квадратчета. Тази задача се нарица трипликация или, казано по-просто, утрояване (фиг. 2).
Фиг. 2. Примѣръ за утрояване на пентомино, взетъ отъ сайта https://www.cimt.org.uk/resources/puzzles/pentoes/penttrip.htm.
Нѣщата ставатъ особено интересни при фигуркитѣ съставени отъ триѫгълници и шестоѫгълници. Да вземемъ за примѣръ хексиамантитѣ. Тѣхната обща площь е 72 триѫгълничета, но 72 = 6 × 12 = 24 × 3, слѣдователно трѣбва да се пробватъ форми, съставени отъ дванадесеть шестоѫгълника съ страна едно или отъ три шестоѫгълника съ страна двѣ. Оказва се, че и двѣтѣ възможности сѫ осѫществими, както се вижда по-долу.

Фиг. 3. Горната форма е съставена отъ дванадесеть шестоѫгълника съ страна едно, а долната отъ три със страна двѣ. 
Формитѣ, образувани отъ тритѣ голѣми шестоѫгълника, обаче, сѫ чисто и просто тритѣ трихекса. Така се появява една връзка между фигурки отъ триѫгълници и отъ шестоѫгълници, въ което нѣма нищо изненадващо, защото един шестоѫгълникъ може да бѫде разложенъ на шесть триѫгълника.

Нѣщата ставатъ още по-интересни при хептиамантитѣ, защото тамъ се появава връзка отъ по-високо ниво. Фигуркитѣ сѫ 24, всѣка състояща се отъ седемь триѫгълничета, което дава обща площь отъ 168 (колкото часоветѣ въ една седмица). Но 168 = 6 × 28 = 24 × 7, което означава, че трѣбва да се провѣрятъ форми съставени отъ 28 макро шестоѫгълника съ страна едно или отъ седемь макро шестоѫгълника съ страна двѣ. Рѣшения сѫществуватъ и въ двата случая: за седемь шестоѫгълника съ страна двѣ вж. фиг. 1, въ дѣсно, а за 28 шестоѫгълника съ страна едно фиг. 4.
Фиг. 4. Двадесеть и осемь шестоѫгълника съ страна едно могатъ да бѫдатъ покрити съ двадесеть и четиритѣ хептиаманти.
Красивото въ случая съ малкитѣ макро шестоѫгълници е, че броятъ имъ съотвѣтства на общата площь на тетрахексоветѣ. Формата отъ фиг. 4 може да се нареди съ тѣхна помощь по начина, показанъ на фиг. 5.

Фиг. 5. Това рѣшение отъ тетрахексове е единствено.
Колкото и елегантна да е тази връзка между хептиамантитѣ и тетрахексоветѣ, смѣтамъ, че тя е напълно случайна и нѣма нѣкакво по-дълбоко обяснение отъ чистия "капризъ на числата", който опрѣдѣля, напримѣръ, кое число да е просто и кое съставно. Провѣрка въ Онлайнъ енциклопедията на поредицитѣ отъ цѣли числа (фигурки отъ триѫгълници безъ дупки, фигурки отъ шестоѫгълници), показва, че единствената друга такава връзка е между единия дихексъ и тритѣ тетриаманта, които обаче не могатъ да се подредятъ въ формата на два слѣпени шестоѣгълника.

Макро структури сѫ възможни и при полихексоветѣ. 28-тѣ тетрахексове могатъ да се подредятъ въ четири голѣми шестоѫгълника, както е показано на фиг. 6.

Фиг. 6. Четиритѣ макро шестоѫгълника могат да бѫдатъ подредени само въ формата на посоченитѣ три тетрахекса, увеличени двойно. Първото рѣшение е уникално, за втората форма има десеть рѣшения, а за третата двѣ.
Въ малкитѣ комплекти хексове не сѫществуватъ други интересни макроструктури (отъ шестоѫгълници или триѫгълници).