Polyform tiling

Introduction

A polyomino (word derived from domino) is a geometric plane figure made of the union of finitely many edge-connected squares from the regular square lattice. (Some authors require also that a polyomino be simply connected, i.e. that it have no enclosed holes, but that is not the definition used here.) Polyominoes are common objects in recreational mathematics. An n-omino is a polyomino with n squares; the name is commonly written with a Greek prefix.

Problems with polyominoes commonly involve arranging polyominoes to fill some region, or the whole plane, without gaps or overlaps, subject to some constraints. Sets of the twelve pentominoes in wood or plastic are widely available; traditional problems are to fill a 3 by 20, 4 by 15, 5 by 12 or 6 by 10 rectangle with them; the complete sets of solutions to these problems were determined by computer in the 1960s.

Polyiamonds (word derived from diamond) are shapes analogous to polyominoes, but made up of equilateral triangles taken from the regular tiling by such triangles. Polyhexes (singular variously either polyhex or polyhexe) are shapes analogous to polyominoes, but made up of regular hexagons taken from the tiling by the regular hexagon. Both polyiamonds and polyhexes are widely used in recreational mathematics, similarly to polyominoes. Polykites are shapes analogous to polyominoes, but made up of kites taken from the [3.4.6.4] Laves tiling, and are among less-widely-used types of polyforms.

Problems of filling rectangles with copies of a single polyomino have been much studied; problems of filling other regions, and of filling regions with polyhexes or polyiamonds, have been studied less. This page concerns only tiling the whole plane with copies of a single polyomino, polyhex, polyiamond or polykite.

It is unclear what results on plane polyomino, polyhex and polyiamond tiling were found first by whom, when. Tiling the polyominoes of orders 1 through 6 is easy, and John Conway determined the tiling properties of the heptominoes with the aid of Conway’s criterion. The list of non-tiling octominoes was published by Martin Gardner from correspondence from David Bird. Results through the hexahexes and the 9-iamonds were also published by Gardner from his correspondence with Bird and others. A paper with some results for 9-ominoes is listed below. Other people may have obtained results for higher orders, probably through computer or computer-aided search, but results in this area have not generally been formally published. Even in 1983, when the properties of hexominoes had long been known (the fact that they all tile was published by Martin Gardner in Scientific American, July 1965, page 102), it was possible for a paper to be published showing that they all tiled, as if a new result. (F. W. Barnes, Every hexomino tiles the plane, J. Combin. Inform. System Sci. 8 (1983), no. 2, 113–115; MR 86f:05051.)

From time to time I play with problems in recreational mathematics, sometimes by computer; since the summer of 1996 I have, on and off, written and run various programs to determine tiling properties of polyominoes, polyhexes and polyiamonds. Some of the results here may have been computed by others before being presented here, but the only other substantial computations on such matters I am aware of in recent years are those of Glenn Rhoads. Computations with my programs whose results are shown here were first run on single computers for the lower orders, 1996–2002; then for 20-ominoes through 23-ominoes, 16-hexes through 19-hexes and 22-iamonds through 28-iamonds in parallel at DPMMS, Cambridge during summer 2003; then for higher orders by Paul Church on SHARCNET in 2007. Computations for polykites were run through 24-kites in 2023, and for 22-hexes and 25-kites in 2024.

There is a hierarchy of preferred types of tiling in use here, based on that of Grünbaum and Shephard in Tilings and Patterns. The most preferred type is a tiling by translation (in which the centroids of the tiles will form a lattice; if a shape tiles with translates only then it has a tiling in which the centroids of the tiles form a lattice; this is a non-trivial theorem, and some papers on this subject are listed below). The existence of such a tiling is determined by a condition on the boundary of the shape, similar to the well known Conway criterion. Then come the tilings by 180° rotation, as found by Conway’s criterion. (Many people would look for these first and ignore translation tilings). We now need some terminology: a plane tiling is said to be isohedral if the symmetry group of the tiling acts transitively on the tiles; and n-isohedral if the tiles fall into n orbits under the action of the symmetry group of the tiling. A shape is said to be anisohedral if it tiles, but not isohedrally. So next most preferred are the isohedral tilings; then come the anisohedral tiles, which are probably the most interesting. (Part of Hilbert’s 18th problem supposed that there were no anisohedral tiles in two dimensions (the first was found by Heesch in 1935) and asked for one in three dimensions.) After this are left over the non-tiling shapes. A refinement to the hierarchy used is, for anisohedral shapes, to minimise the number of orbits of tiles; a shape is said to be n-anisohedral, or to have isohedral number n, if it admits a n-isohedral tiling but no m-isohedral tiling for any m < n.

Other hierarchies that have been used in the literature include minimising the number of aspects (orientations) in which a tile appears, using only copies under direct isometries if possible, or minimising the size of a patch of tiles repeating under translation to tile the plane. A variation on the concept of isohedral number is the size of the smallest patch of tiles repeating isohedrally; these numbers are the same for asymmetric tiles, but may differ for some symmetric tiles, in particular where the induced symmetries of tiles in different orbits differ.

Because some investigators consider Conway’s criterion first without regard to tilings by translation (at low orders, almost all of the shapes tiling by translation also tile by 180° rotation), tables are also provided showing, for those shapes tiling by translation, how many do or do not also tile by 180° rotation.

Lists of shapes and tilings (in gzipped PostScript, formatted for A4 paper) are available here; as the order increases, fewer lists are provided; higher-order lists can be provided on request, but the size of the lists increases exponentially and so it is unlikely lists in this form will be of much use, although the raw tiling data may be. The following tables show the numbers of shapes in each class, with links to the lists where appropriate.

If there are problems viewing the PostScript files, first make sure that your browser has not removed the .gz from the name but left the file compressed, or uncompressed the file but saved it under a name ending in .gz. (While I’d like to provide PDF files for wider accessibility, experiment suggests they would be about ten times the size of the gzipped PostScript, which reflects the mathematical structure of the tilings in a more compact way than PDF.) The files for polykites, added more recently, are PDF, as these size considerations have become less significant over time.

Subject to limitations of time and space, my programs can in principle resolve the tiling status of any polyomino, polyhex, polyiamond or polykite that either does not tile, or tiles the plane periodically. My programs would in principle run for ever on an aperiodic monotile. Within the ranges covered by these tables, there are no aperiodic polyominoes, polyhexes or polyiamonds, and two aperiodic polykites, and the tiling status of every shape within the ranges covered by these tables, except for the two aperiodic polykites, could be determined by my programs.

If you find these lists interesting or useful, please let me know.

Tables of tiling results

Polyominoes

Results and listings are provided here through the 25-ominoes.

The following table gives details of k-anisohedral polyominoes of order n.

The following table shows, for those shapes tiling by translation, how many do or do not also tile by 180° rotation.

Polyhexes

Results and listings are provided here through the 22-hexes.

The following table gives details of k-anisohedral polyhexes of order n.

The following table shows, for those shapes tiling by translation, how many do or do not also tile by 180° rotation.

Polyiamonds

Results and listings are provided here through the 30-iamonds.

The following table gives details of k-anisohedral polyiamonds of order n.

The following table shows, for those shapes tiling by translation, how many do or do not also tile by 180° rotation.

Polykites

Results and listings are provided here through the 25-kites. Numbers of anisohedral polykites include aperiodic polykites, but the PDF listings do not. The numbers here relate only to tilings where all tiles are aligned to the same underlying [3.4.6.4] Laves tiling (this means that the 1-kite is not, for the purposes of this table, considered to have a 180° rotation tiling, but does not affect other figures in the tables).

The following table gives details of k-anisohedral polykites of order n.

The following table shows, for those shapes tiling by translation, how many do or do not also tile by 180° rotation.

Polymorphic tiles

A shape is said to be k-morphic if it tiles the plane in exactly k ways. Examples for k-morphic polyominoes for all k from 0 to 10 inclusive have been presented in the literature (mainly by Fontaine and Martin), with infinite families up to k = 9 and a single example (up to similarity) of a 10-morphic tile.

My programs can attempt to determine the number of tilings by a polyomino, polyiamond, polyhex or polykite, whether finite, or an uncountable infinity. However, they cannot handle all shapes within the ranges above. The following in particular cannot be handled:

• aperiodic shapes;
• shapes tiling in a countable infinity of ways (may not exist);
• shapes tiling in finitely many ways, at least one of which is not periodic in two non-parallel directions; and
• shapes tiling in an uncountable infinity of ways, at least one being periodic, but not provable to tile in an uncountable infinity of ways by finding a region or strip that forms part of a periodic tiling and can be filled in more than one way.

A dimorphic 12-omino of the third type (tilings drawn manually, since my programs cannot find or draw tilings with translations in one direction only as symmetries) is shown:
.

My programs have found three new 10-morphic tiles, an 11-omino, a 16-hex and a 19-omino, and an 11-morphic tile, a 19-omino.

These tables show the numerical results obtained on polymorphic polyominoes, polyiamonds and polyhexes. Non-tiling shapes are not included. The columns headed 1 through 11 show the number of shapes of order n found to tile in that number of ways, the column headed ∞ shows the number of shapes found to tile in an uncountable infinity of ways, and the column headed “skipped” shows the number of shapes that tile the plane that were not successfully handled by the program (most probably because they were of the third or fourth type above, or otherwise were too complicated for the program to handle or met the heuristics to detect tiles of those types). The PDF listings do not include any of those “skipped” shapes.

Polyominoes

Polyhexes

Polyiamonds

Enumerating all k-isohedral tilings

My programs can enumerate all k-isohedral tilings by a polyform (that are aligned to the corresponding underlying regular or Laves tiling). This table shows the number of isohedral tilings by n-ominoes for some n (with 2-isohedral tilings also for small n); more details for k-isohedral tilings and data for other kinds of polyform may be added later.

Polyominoes

Algorithms and data structures

The general algorithm used by my programs for determining whether polyforms tile, and how simply, is as follows.

1. List the fixed shapes of a given order, using Redelmeier’s method. We define an (arbitrary) ordering for fixed tiles (first by the dimensions of the box the tile fits in then by lexicographic ordering of the bitstring indicating which cells inside that box are used), for each fixed tile generate all aspects and discard that tile unless it is of the aspect first in the ordering—i.e., we define a canonical aspect for each tile and ignore the non-canonical aspects when they get generated. Checking canonicity isn’t very efficient for pure enumeration (hence why Redelmeier enumerates symmetric shapes separately and gets the enumeration of free shapes as a linear combination of the numbers with various symmetries), but it’s much more efficient than checking for tiling properties 8 or 12 times and then applying linear relations to get the numbers of free shapes tiling in a given way.
2. Eliminate shapes with holes, translation tilings and 180-degree rotation tilings by considering the boundary (Conway’s criterion and the translation criterion).
3. Generate and reduce a list of the possible neighbours of a tile (i.e., of those neighbours that might appear in the tiling). If shape X (standard position and orientation) has a putative neighbour Y, and position P is next to X and not contained in Y, but there is no possible neighbour of X that contains P and does not intersect Y, then Y is not in fact a possible neighbour of X. Applying this appropriately causes most shapes to be found not to tile with no subsequent backtracking search required. (“Appropriately” includes not checking all (Y, P) pairs: since this method is so efficient at showing shapes not to tile, checking all (Y, P) pairs just consumes extra time to little benefit; only P close to Y in fact need to be checked for most of the benefits.) As more information is gained, the list of possible neighbours is reduced further at subsequent stages.
4. Do a backtracking search for isohedral tilings. The programs can also list all isohedral tilings by a given shape if desired, or all k-isohedral tilings.
5. Do a backtracking search to find all ways of surrounding the shape (which don’t include any pair of neighbours previously ruled out). If this generates too many possibilities then it jumps out to a further reduction step of determining exactly which neighbours can occur in a complete surround of a tile, but this rarely occurs.
6. Another reduction of this list based on which neighbours occur in it. Given a tile T and the ways of surrounding T, if some neighbour U of T occurs in none of these surrounds, for any isometry I we may eliminate all surrounds containing IT and IU as not being extensible to a tiling. This may be repeated until the lists of possible surrounds and neighbours stabilise.
7. Check for 2-isohedral and 3-isohedral tilings if there are any possible surrounds left.

8. At this point we have a collection of possible k-fold surrounds of a tile. We do the following to expand to (k+1)-fold surrounds:

   1. Check consistency: each tile within each k-fold surround should individually be surroundable by one of the k-fold surrounds, if that k-fold surround can be extended. Repeat until the list stabilises. (There are optimisations to speed this up when there are a great number of surrounds, and to record tiles found here to be forced.)
   2. Try to surround each tile in the first layer of each k-fold surround with the possible k-fold surrounds, in a backtracking search to extend to (k+1)-fold surrounds. When each is found, determine whether it contains three non-collinear tiles, in the same aspect, the translations between which yield a periodic tiling. If a periodic tiling is found, determine the smallest number of orbits (by now known to be at least 4) with which the shape tiles.

   If the shape tiles periodically, this process will terminate with a tiling. If the process does not terminate (with a periodic tiling or a finding that there are no k-fold surrounds for some k), the shape must tile (by the Extension Theorem), and must be aperiodic. In practice, the programs have internal limits on the size of coordinates of shapes allowed, and will exit if those limits are exceeded; thus any aperiodic tile, or a tile whose simplest periodic tiling is sufficiently complicated, will cause the programs to exit with an error.

A search for k-isohedral tilings starts with a shape in class 1, and looks for neighbours in some position. Such a neighbour is either in an already known class, or in a new class (which we may suppose is the first class not yet used). If a known class, the symmetries of the tiling may force additional tiles to be present. Repeat until all tiles of all classes are surrounded, or a contradiction is found. (In the case of symmetrical tiles, the tiles are initially assumed to have asymmetrical markings, until symmetries are forced. In fact all isohedral tilings can have asymmetrical markings placed on the tiles while staying isohedral, but this does not apply to 2-isohedral and higher tilings.) At least for isohedral tilings this is polynomial in the size of the tile (probably for k-isohedral tilings as well; potentially exponential in k though at least each k-isohedral tiling only gets found k times, once with each class in the centre, not k! times), although this is a different algorithm from that of Keating and Vince. Abstractly, for each k there is a finite set of conditions similar to Conway’s criterion for determining k-isohedral tiling, since the number of types of k-isohedral tiling must be finite for each k. The criteria for isohedral tilings have been listed explicitly.

Bitmaps are maintained to show whether a shape in a given position and aspect is consistent with a shape in standard position and orientation. Initially only intersecting shapes (or possibly pairs of shapes enclosing a hole whose area is not a multiple of the area of the shape) are inconsistent, but as neighbours are found not to be possible in a tiling they are also marked as inconsistent.

The optimisations above reducing sets of possible neighbours are fundamentally incompatible with computing Heesch numbers, although it is possible much weaker versions could be used in that context.

The general algorithms for finding k-morphic tiles (which can’t handle every tile) are thus:

1. Determine ways of surrounding a central tile n times, eliminating as many as possible that can’t occur in a tiling.
2. If for some n we find that each way extends in at most one way (that might occur in a tiling) to surround the tile n+1 times, then we have finitely many tilings, all periodic, and we can straightforwardly list them all. (This fails to find k-morphic tiles where not all tilings are periodic in two directions, such as the 12-omino shown above.)
3. From the patches of tiles we have, find as many tilings as possible (by looking at non-collinear triples of tiles in the same aspect and seeing if the translations between them could be symmetries of a tiling extending that patch). My programs also generate isohedral, 2-isohedral and 3-isohedral tilings at appropriate points to add to this list, and other methods could also be used to find more tilings.
4. From the tilings found so far, take pairs of tilings (possibly the same tiling in different positions or orientations) and lay them on top of each other in each possible relative position and orientation. Form an infinite bipartite graph whose vertices are the tiles of the two tilings and where two vertices are joined if the corresponding tiles overlap. If this graph has a component with more than two vertices and not having translations in two non-parallel directions as symmetries, then the tile has an uncountable infinity of tilings. (Such a component corresponds to a region of a tiling, either finite or an infinite strip, that can be filled in more than one way. This method of showing a tile to have an uncountable infinity of tilings does not appear to work for all tiles with an uncountable infinity of tilings.)

Because of the cases this can’t handle, the programs have heuristics to stop after surrounding too many times or finding too many possible patches without determining how many tilings a tile has.

References

The list here is deliberately very selective, giving general survey references rather than tracking results and terminology back to their original sources.

General references

The first two of these in particular have extensive bibliographies that may be used to find original sources for the older results quoted here.

• Branko Grünbaum and G. C. Shephard, Tilings and Patterns, W. H. Freeman and Company, 1987. MR 88k:52018.

  This definitive and comprehensive work is the essential reference for all tiling enthusiasts to the work done on tilings up to when it was written and the associated literature. It defines standard terminology for the field where previously there was inconsistency and lack of rigour. The Dover edition (2016) has an Appendix with some limited notes on subsequent results; unfortunately there is no comprehensive revision or other comparable work covering the many subsequent developments in tiling more thoroughly.

• Solomon W. Golomb, Polyominoes (second edition), Princeton University Press, 1994. MR 95k:00006.

  Second edition of a classic work, covers much of what is known about tiling regions (not particularly the plane) with polyominoes, and to a lesser extent polyhexes and polyiamonds.

• George E. Martin, Polyominoes: A guide to puzzles and problems in tiling, Mathematical Association of America, 1991 (second edition, 1996). MR 93d:00006.

  This book extensively covers problems of tiling both regions and the whole plane by polyominoes, with special emphasis on polymorphic tiles.

• Brian Wichmann, The World of Patterns, CD and booklet. World Scientific, 2001.
• John Berglund, Anisohedral Tilings Page.
• Geometry Junkyard: Polyominoes.

Tilings by translation

The first two references prove the result that tiling with translates only implies tiling with a lattice of translations for polyominoes, the last proves it for general tiles “homeomorphic to a closed disc and whose boundary is piecewise C², with a finite number of inflection points”.

• H. A. G. Wijshoff and J. van Leeuwen, Arbitrary versus periodic storage schemes and tessellations of the plane using one type of polyomino, Inform. and Control 62 (1984), no. 1, 1–25. MR 86m:68069.
• D. Beauquier and M. Nivat, On translating one polyomino to tile the plane, Discrete Comput. Geom. 6 (1991), no. 6, 575–592. MR 92i:52025.
• D. Girault-Beauquier and M. Nivat, Tiling the plane with one tile, in: Topology and category theory in computer science (Oxford, 1989), 291–333, Papers from the Topology Symposium held in Oxford, June 27–30, 1989. Edited by G. M. Reed, A. W. Roscoe and R. F. Wachter. OUP, 1991. MR 1145780.

Specific results

• Olaf Delgado, Daniel Huson and Elizaveta Zamorzaeva, The classification of 2-isohedral tilings of the plane, Geom. Dedicata 42 (1992), no. 1, 43–117. MR 93d:52028.
• Daniel H. Huson, The generation and classification of tile-k-transitive tilings of the Euclidean plane, the sphere and the hyperbolic plane, Geom. Dedicata 47 (1993), no. 3, 269–296. MR 94i:52018.
• Anne Fontaine and George E. Martin, Polymorphic polyominoes, Math. Mag. 57 (1984), no. 5, 275–283. MR 86h:05042.
• K. Keating and A. Vince, Isohedral polyomino tiling of the plane, Discrete Comput. Geom. 21 (1999), no. 4, 615–630. MR 2000a:05061.
• Daniel A. Rawsthorne, Tiling complexity of small n-ominoes (n < 10), Discrete Math. 70 (1988), no. 1, 71–75. MR 90c:05065.
• D. Hugh Redelmeier, Counting polyominoes: yet another attack, Discrete Math. 36 (1981), no. 2, 191–203. MR 84g:05049.
• Glenn C. Rhoads, Planar tilings by polyominoes, polyhexes, and polyiamonds, J. Comput. Appl. Math. 174 (2005), no. 2, 329–353. MR 2005h:05042.
• Glenn C. Rhoads, Planar tilings and the search for an aperiodic prototile, PhD dissertation, Rutgers University, May 2003.
• John Berglund, Is There a k-Anisohedral Tile for k ≥ 5?, Amer. Math. Monthly 100 (1993), no. 6, 585–588. (In the Unsolved Problems section; not reviewed in MR.)
• David Smith, Joseph Samuel Myers, Craig S. Kaplan and Chaim Goodman-Strauss, An aperiodic monotile, Combinatorial Theory 4 (1) (2024), #6.

Return to my mathematics page
Return to my home page