Animal enumerations on the {4,4} Euclidean tiling

Introduction

The animals on the {4,4} regular tiling of the Euclidean plane are called polyominoes, a name coined by Solomon Golomb in 1953 [1]. An alternative name would be square animals, since the {4,4} regular tiling is composed of squares. Each polyomino may be equal to its mirror image (achiral) or different from its mirror image (chiral). The vast majority of the polyominoes do not have any kind of symmetry.

Redelmeier [2] developed an algorithm to enumerate the polyominoes of a given area, counting all their possible orientations (called fixed polyominoes). He developed another program to enumerate the polyominoes of a given area with a predefined symmetry (axial, rotational, mirror image). By combining the results of the different enumerations it is possible to infer the number of polyominoes with different shapes, ie., disregarding orientation and mirror images (called free polyominoes). Using 8 months of CPU time, he was able to count the number of polyominoes with areas up to 24. In 1998, with the help of some friends (who donated computational power), I managed to extend this to areas up to 28. In 2000 there occurred a spectacular progress in the enumeration of fixed polyominoes of a given area, with Jensen and Guttmann [3] reporting results for areas up to 46 (the current computational limit appears to be area 56; see the appendix of [4] and the notes attached to the POLYNUM and POLYSAVE programs kindly made available by Donald E. Knuth, who was the first to obtain correct results for area 47). The number of free polyominoes, however, only appears to be known up to area 28 (see results below).

In 2014 I developed a program capable of classifying each free polyomino according to its number of holes and their areas. The program uses an algorithm similar to the parallel version of the Redelmeier algorithm [5]. For each area, the fixed polyominoes were generated, and only those in canonical form (one representative of each free polyomino) were classified. The program was relatively fast, and since it was possible to run it in parallel, it was possible to collect data up to area 28.

Tables with counts of the number of polyominoes (December 28, 2015)

The following table presents counts of the number of polyominoes classified according to Redelmeier's symmetry classes [2].

The following table presents counts of the number of polyominoes classified according to their number of holes.

References

Additional links

• The geometry junkyard polyomino entry.
• Hyperbolic Planar Tesselations.
• Uniform tilings in hyperbolic plane.