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.