Polyomino, polyhex and polyiamond 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.

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 or polyiamond.

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.

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.)

Subject to limitations of time and space, my programs can in principle resolve the tiling status of any polyomino, polyhex or polyiamond that either does not tile, or tiles the plane periodically. It is a notable unsolved problem whether there exists a single polygon that tiles the plane only non-periodically (such a hypothetical shape being known as aperiodic; my programs would in principle run forever on such a shape). Within the ranges covered by these tables, there are no aperiodic polyominoes, polyhexes or polyiamonds, and the tiling status of every shape within the ranges covered by these tables 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.

nn-ominoesholestranslation180°isohedralanisohedralnon-tilers
11010000
21010000
32020000
45050000
51209 3000
63502411000
710814160303
8369612119922120
9128537213748809198
1046551955222181323441390
111707397978353913381089474
12636004663271217193332222235488
13238591214743179318813178431178448
149019719649686728594213590900696371
153426576425449166212187604304511572721544
161307925518492523741543033976881225810683110
175010790979463804855872831548781138141334494
181926220523384094615466023441065511377429155723774
197426242321430603391850073096983935925542596182769
20287067195060116588857329693445282190553183062257379379
21111230606782513617990876633178591163163376220678587521496
22431918576881046622031517597303165810935424504784932688629235
2316804700772843425174374260654349644736106594310542124568505590
24654999700403179630865835876874317259671939341178202169475147925759
2525572270447647411236990121077433922879555431694933289771815832051949

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

nk = 2k = 3k = 4k = 5k = 6
810000
980100
10413000
118918100
122146200
1340624010
1487424101
15110749100
16221046101
17131660203
18738042700
19545085205
201821186504
2121866199200
2247702135912
2310390149300
242018343241100
2528784182812

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

n180° as welltranslation only
110
210
320
450
590
6240
7410
81210
92121
105202
1177310
122577135
133037142
148081591
15139542667
16321245291
17416956863
1811878435876
1915018834819
20411484161812
21604304272329
221305265454465
231954823651720
2453268903441853
2573316063442733

Polyhexes

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

nn-hexesholestranslation180°isohedralanisohedralnon-tilers
11010000
21010000
33030000
47061000
5220129100
68213639114
733326019733437
81448132097218836381
96572673872717611732717
103049040410548211180325818760
1114355223231468198362985501116439
126831011351768957449721250999565943
1332748267657070011326112356413833033697
141579689742932023920403534100221483514835067
15765818752373965494961127416392655468572633658
1637286810113004323126732236440243818810576356923880
17182223662870641985146046417331643315084971746833634
188934910362381260615638800156044004762862421568532601529
194393916426320465214916475022131842823274451293141868336466
202166510360121093662402627729357396591618839643129325205618704167
21107079330894258228136539416286115421188046717154845551012359995953

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

nk = 2k = 3k = 4k = 5k = 6k = 7k = 8k = 9k = 10
6100000000
7310000000
82772000000
96652000000
10226264000200
113809719310010
128799523200000
13109726714500000
14441939024110000
15377286447200000
169488100282110011
176718171853600110
1840023207456120000
191263026534100100
201272132039593110000
21768367583132220000

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

n180° as welltranslation only
110
210
330
460
5120
6360
7591
82081
937314
10102430
11138088
125966929
136012989
14200613859
153293916557
169171535017
179954046506
18381899256901
19390781256721
2014867461286189
2118568582306003

Polyiamonds

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

nn-iamondsholestranslation180°isohedralanisohedralnon-tilers
11001000
21010000
31001000
43021000
54004000
612084000
7240021201
866024321000
91601011122620
104484622005425103
1111862504625253594
1233341082911162534471192
13923545001875523976290
142616617135394195133928118099
1573983626709410321828054808
16211297219882625179789315343159048
17604107751850240342177345502366
1817363282515906177731752942613671374593
195000593828408079925154236194076218
2014448984269263021923251808101314247811378831
214183573886612870358096140072150432674779
221214192602762404037721631919110794829293006494
23353045291874796630796571467481811264720498
2410284527172753922482382673104082163927916742748062099
2530008006278625936610298047671073634582134512296
26876921672226902856082992036088310970251484536071524897
272566196189883595815850101676603002062545917289205132
28751951666672589304492013381402366136984622569531149268564671
29220605519559799781186320214770128952919416140605019208
3064794362679624643356861734927338448558429458807333739401392287316

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

nk = 2k = 3k = 4k = 5k = 6k = 7k = 8
95010000
1023110000
1143820000
1238810000
1385920001
14274700000
152591371000
163241611100
173261630000
1813441750100
195912510002
20234812540100
2114663240002
2282404360300
2317733440000
2416608121130000
2534084640000
264837262170200
27538657130003
289518911380100
2993515920004
303308332881200500

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

n180° as welltranslation only
210
420
680
8240
10611
1226922
1450138
162121504
1847091468
20149786945
222667511046
24123081115186
26179707119496
28660366677774
3014791142013619

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 or polyhex, whether finite, or an uncountable infinity. However, they cannot handle all shapes within the ranges above. The following in particular cannot be handled:

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:
[Dimorphic 12-omino].

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).

Polyominoes

n1234567891011skipped
10000000000010
20000000000010
30000000000020
40000000000050
510000000000110
600000000000350
766300000000890
820184200100002980
91938414610000007520
10749257412210000020180
113222809148311232001023920
1290261440153224000000128031
13250903645435942543300093682
146374656814165617210000391769
15180669118426658513101000863061
16366557167581128142376200001622576
176831573073314732646392100011132112
1821928166555722262383111100079644417
1929365407281121303609672111136916014
2094440801263633550322684211000255223818
21182994572214464767458901400200339493919

Polyhexes

n12345678910skipped
1100000000000
2000000000010
3000000000030
4000000000070
50000000000220
62000000000750
7288401000002521
8196701340010007700
9108522441710000024255
103869640641410000067380
111378218402123481101089110
1253467510836929310000446613
1311662483576199220440003880930
14349511161466568410600001660889
151094609351741231848100004431423
162260495508541878188324000162640541
174040091785811748269333100064025528

Polyiamonds

n123456skipped
100000010
200000010
300000010
400000030
500000040
6200000100
7000000230
8200000640
918820001110
10621530002610
112846481002100
12491901210014400
131623249307005860
1429953211622030180
1576655071400047220
1615640842371421137250
172275512143401025520
18671852745932020400955
198574128466160073130
202483025394147391021236236
214016737216107200906740

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 (YP) pairs: since this method is so efficient at showing shapes not to tile, checking all (YP) 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.

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 C2, with a finite number of inflection points”.

Specific results


Return to my mathematics page
Return to my home page


Contact: Joseph Myers (jsm@polyomino.org.uk)
Last updated: 19 February 2012