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.
Results and listings are provided here through the 25-ominoes.
n | n-ominoes | holes | translation | 180° | isohedral | anisohedral | non-tilers |
---|---|---|---|---|---|---|---|
1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
2 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
3 | 2 | 0 | 2 | 0 | 0 | 0 | 0 |
4 | 5 | 0 | 5 | 0 | 0 | 0 | 0 |
5 | 12 | 0 | 9 | 3 | 0 | 0 | 0 |
6 | 35 | 0 | 24 | 11 | 0 | 0 | 0 |
7 | 108 | 1 | 41 | 60 | 3 | 0 | 3 |
8 | 369 | 6 | 121 | 199 | 22 | 1 | 20 |
9 | 1285 | 37 | 213 | 748 | 80 | 9 | 198 |
10 | 4655 | 195 | 522 | 2181 | 323 | 44 | 1390 |
11 | 17073 | 979 | 783 | 5391 | 338 | 108 | 9474 |
12 | 63600 | 4663 | 2712 | 17193 | 3322 | 222 | 35488 |
13 | 238591 | 21474 | 3179 | 31881 | 3178 | 431 | 178448 |
14 | 901971 | 96496 | 8672 | 85942 | 13590 | 900 | 696371 |
15 | 3426576 | 425449 | 16621 | 218760 | 43045 | 1157 | 2721544 |
16 | 13079255 | 1849252 | 37415 | 430339 | 76881 | 2258 | 10683110 |
17 | 50107909 | 7946380 | 48558 | 728315 | 48781 | 1381 | 41334494 |
18 | 192622052 | 33840946 | 154660 | 2344106 | 551137 | 7429 | 155723774 |
19 | 742624232 | 143060339 | 185007 | 3096983 | 93592 | 5542 | 596182769 |
20 | 2870671950 | 601165888 | 573296 | 9344528 | 2190553 | 18306 | 2257379379 |
21 | 11123060678 | 2513617990 | 876633 | 17859116 | 3163376 | 22067 | 8587521496 |
22 | 43191857688 | 10466220315 | 1759730 | 31658109 | 3542450 | 47849 | 32688629235 |
23 | 168047007728 | 43425174374 | 2606543 | 49644736 | 1065943 | 10542 | 124568505590 |
24 | 654999700403 | 179630865835 | 8768743 | 172596719 | 39341178 | 202169 | 475147925759 |
25 | 2557227044764 | 741123699012 | 10774339 | 228795554 | 31694933 | 28977 | 1815832051949 |
The following table gives details of k-anisohedral polyominoes of order n.
n | k = 2 | k = 3 | k = 4 | k = 5 | k = 6 |
---|---|---|---|---|---|
8 | 1 | 0 | 0 | 0 | 0 |
9 | 8 | 0 | 1 | 0 | 0 |
10 | 41 | 3 | 0 | 0 | 0 |
11 | 89 | 18 | 1 | 0 | 0 |
12 | 214 | 6 | 2 | 0 | 0 |
13 | 406 | 24 | 0 | 1 | 0 |
14 | 874 | 24 | 1 | 0 | 1 |
15 | 1107 | 49 | 1 | 0 | 0 |
16 | 2210 | 46 | 1 | 0 | 1 |
17 | 1316 | 60 | 2 | 0 | 3 |
18 | 7380 | 42 | 7 | 0 | 0 |
19 | 5450 | 85 | 2 | 0 | 5 |
20 | 18211 | 86 | 5 | 0 | 4 |
21 | 21866 | 199 | 2 | 0 | 0 |
22 | 47702 | 135 | 9 | 1 | 2 |
23 | 10390 | 149 | 3 | 0 | 0 |
24 | 201834 | 324 | 11 | 0 | 0 |
25 | 28784 | 182 | 8 | 1 | 2 |
The following table shows, for those shapes tiling by translation, how many do or do not also tile by 180° rotation.
n | 180° as well | translation only |
---|---|---|
1 | 1 | 0 |
2 | 1 | 0 |
3 | 2 | 0 |
4 | 5 | 0 |
5 | 9 | 0 |
6 | 24 | 0 |
7 | 41 | 0 |
8 | 121 | 0 |
9 | 212 | 1 |
10 | 520 | 2 |
11 | 773 | 10 |
12 | 2577 | 135 |
13 | 3037 | 142 |
14 | 8081 | 591 |
15 | 13954 | 2667 |
16 | 32124 | 5291 |
17 | 41695 | 6863 |
18 | 118784 | 35876 |
19 | 150188 | 34819 |
20 | 411484 | 161812 |
21 | 604304 | 272329 |
22 | 1305265 | 454465 |
23 | 1954823 | 651720 |
24 | 5326890 | 3441853 |
25 | 7331606 | 3442733 |
Results and listings are provided here through the 21-hexes.
n | n-hexes | holes | translation | 180° | isohedral | anisohedral | non-tilers |
---|---|---|---|---|---|---|---|
1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
2 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
3 | 3 | 0 | 3 | 0 | 0 | 0 | 0 |
4 | 7 | 0 | 6 | 1 | 0 | 0 | 0 |
5 | 22 | 0 | 12 | 9 | 1 | 0 | 0 |
6 | 82 | 1 | 36 | 39 | 1 | 1 | 4 |
7 | 333 | 2 | 60 | 197 | 33 | 4 | 37 |
8 | 1448 | 13 | 209 | 721 | 88 | 36 | 381 |
9 | 6572 | 67 | 387 | 2717 | 611 | 73 | 2717 |
10 | 30490 | 404 | 1054 | 8211 | 1803 | 258 | 18760 |
11 | 143552 | 2323 | 1468 | 19836 | 2985 | 501 | 116439 |
12 | 683101 | 13517 | 6895 | 74497 | 21250 | 999 | 565943 |
13 | 3274826 | 76570 | 7001 | 132611 | 23564 | 1383 | 3033697 |
14 | 15796897 | 429320 | 23920 | 403534 | 100221 | 4835 | 14835067 |
15 | 76581875 | 2373965 | 49496 | 1127416 | 392655 | 4685 | 72633658 |
16 | 372868101 | 13004323 | 126732 | 2364402 | 438188 | 10576 | 356923880 |
17 | 1822236628 | 70641985 | 146046 | 4173316 | 433150 | 8497 | 1746833634 |
18 | 8934910362 | 381260615 | 638800 | 15604400 | 4762862 | 42156 | 8532601529 |
19 | 43939164263 | 2046521491 | 647502 | 21318428 | 2327445 | 12931 | 41868336466 |
20 | 216651036012 | 10936624026 | 2772935 | 73965916 | 18839643 | 129325 | 205618704167 |
21 | 1070793308942 | 58228136539 | 4162861 | 154211880 | 46717154 | 84555 | 1012359995953 |
The following table gives details of k-anisohedral polyhexes of order n.
n | k = 2 | k = 3 | k = 4 | k = 5 | k = 6 | k = 7 | k = 8 | k = 9 | k = 10 |
---|---|---|---|---|---|---|---|---|---|
6 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
8 | 27 | 7 | 2 | 0 | 0 | 0 | 0 | 0 | 0 |
9 | 66 | 5 | 2 | 0 | 0 | 0 | 0 | 0 | 0 |
10 | 226 | 26 | 4 | 0 | 0 | 0 | 2 | 0 | 0 |
11 | 380 | 97 | 19 | 3 | 1 | 0 | 0 | 1 | 0 |
12 | 879 | 95 | 23 | 2 | 0 | 0 | 0 | 0 | 0 |
13 | 1097 | 267 | 14 | 5 | 0 | 0 | 0 | 0 | 0 |
14 | 4419 | 390 | 24 | 1 | 1 | 0 | 0 | 0 | 0 |
15 | 3772 | 864 | 47 | 2 | 0 | 0 | 0 | 0 | 0 |
16 | 9488 | 1002 | 82 | 1 | 1 | 0 | 0 | 1 | 1 |
17 | 6718 | 1718 | 53 | 6 | 0 | 0 | 1 | 1 | 0 |
18 | 40023 | 2074 | 56 | 1 | 2 | 0 | 0 | 0 | 0 |
19 | 12630 | 265 | 34 | 1 | 0 | 0 | 1 | 0 | 0 |
20 | 127213 | 2039 | 59 | 3 | 11 | 0 | 0 | 0 | 0 |
21 | 76836 | 7583 | 132 | 2 | 2 | 0 | 0 | 0 | 0 |
The following table shows, for those shapes tiling by translation, how many do or do not also tile by 180° rotation.
n | 180° as well | translation only |
---|---|---|
1 | 1 | 0 |
2 | 1 | 0 |
3 | 3 | 0 |
4 | 6 | 0 |
5 | 12 | 0 |
6 | 36 | 0 |
7 | 59 | 1 |
8 | 208 | 1 |
9 | 373 | 14 |
10 | 1024 | 30 |
11 | 1380 | 88 |
12 | 5966 | 929 |
13 | 6012 | 989 |
14 | 20061 | 3859 |
15 | 32939 | 16557 |
16 | 91715 | 35017 |
17 | 99540 | 46506 |
18 | 381899 | 256901 |
19 | 390781 | 256721 |
20 | 1486746 | 1286189 |
21 | 1856858 | 2306003 |
Results and listings are provided here through the 30-iamonds.
n | n-iamonds | holes | translation | 180° | isohedral | anisohedral | non-tilers |
---|---|---|---|---|---|---|---|
1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
2 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
3 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
4 | 3 | 0 | 2 | 1 | 0 | 0 | 0 |
5 | 4 | 0 | 0 | 4 | 0 | 0 | 0 |
6 | 12 | 0 | 8 | 4 | 0 | 0 | 0 |
7 | 24 | 0 | 0 | 21 | 2 | 0 | 1 |
8 | 66 | 0 | 24 | 32 | 10 | 0 | 0 |
9 | 160 | 1 | 0 | 111 | 22 | 6 | 20 |
10 | 448 | 4 | 62 | 200 | 54 | 25 | 103 |
11 | 1186 | 25 | 0 | 462 | 52 | 53 | 594 |
12 | 3334 | 108 | 291 | 1162 | 534 | 47 | 1192 |
13 | 9235 | 450 | 0 | 1875 | 523 | 97 | 6290 |
14 | 26166 | 1713 | 539 | 4195 | 1339 | 281 | 18099 |
15 | 73983 | 6267 | 0 | 9410 | 3218 | 280 | 54808 |
16 | 211297 | 21988 | 2625 | 17978 | 9315 | 343 | 159048 |
17 | 604107 | 75185 | 0 | 24034 | 2177 | 345 | 502366 |
18 | 1736328 | 251590 | 6177 | 73175 | 29426 | 1367 | 1374593 |
19 | 5000593 | 828408 | 0 | 79925 | 15423 | 619 | 4076218 |
20 | 14448984 | 2692630 | 21923 | 251808 | 101314 | 2478 | 11378831 |
21 | 41835738 | 8661287 | 0 | 358096 | 140072 | 1504 | 32674779 |
22 | 121419260 | 27624040 | 37721 | 631919 | 110794 | 8292 | 93006494 |
23 | 353045291 | 87479663 | 0 | 796571 | 46748 | 1811 | 264720498 |
24 | 1028452717 | 275392248 | 238267 | 3104082 | 1639279 | 16742 | 748062099 |
25 | 3000800627 | 862593661 | 0 | 2980476 | 710736 | 3458 | 2134512296 |
26 | 8769216722 | 2690285608 | 299203 | 6088310 | 970251 | 48453 | 6071524897 |
27 | 25661961898 | 8359581585 | 0 | 10167660 | 3002062 | 5459 | 17289205132 |
28 | 75195166667 | 25893044920 | 1338140 | 23661369 | 8462256 | 95311 | 49268564671 |
29 | 220605519559 | 79978118632 | 0 | 21477012 | 895291 | 9416 | 140605019208 |
30 | 647943626796 | 246433568617 | 3492733 | 84485584 | 29458807 | 333739 | 401392287316 |
The following table gives details of k-anisohedral polyiamonds of order n.
n | k = 2 | k = 3 | k = 4 | k = 5 | k = 6 | k = 7 | k = 8 | |
---|---|---|---|---|---|---|---|---|
9 | 5 | 0 | 1 | 0 | 0 | 0 | 0 | |
10 | 23 | 1 | 1 | 0 | 0 | 0 | 0 | |
11 | 43 | 8 | 2 | 0 | 0 | 0 | 0 | |
12 | 38 | 8 | 1 | 0 | 0 | 0 | 0 | |
13 | 85 | 9 | 2 | 0 | 0 | 0 | 1 | |
14 | 274 | 7 | 0 | 0 | 0 | 0 | 0 | |
15 | 259 | 13 | 7 | 1 | 0 | 0 | 0 | |
16 | 324 | 16 | 1 | 1 | 1 | 0 | 0 | |
17 | 326 | 16 | 3 | 0 | 0 | 0 | 0 | |
18 | 1344 | 17 | 5 | 0 | 1 | 0 | 0 | |
19 | 591 | 25 | 1 | 0 | 0 | 0 | 2 | |
20 | 2348 | 125 | 4 | 0 | 1 | 0 | 0 | |
21 | 1466 | 32 | 4 | 0 | 0 | 0 | 2 | |
22 | 8240 | 43 | 6 | 0 | 3 | 0 | 0 | |
23 | 1773 | 34 | 4 | 0 | 0 | 0 | 0 | |
24 | 16608 | 121 | 13 | 0 | 0 | 0 | 0 | |
25 | 3408 | 46 | 4 | 0 | 0 | 0 | 0 | |
26 | 48372 | 62 | 17 | 0 | 2 | 0 | 0 | |
27 | 5386 | 57 | 13 | 0 | 0 | 0 | 3 | |
28 | 95189 | 113 | 8 | 0 | 1 | 0 | 0 | |
29 | 9351 | 59 | 2 | 0 | 0 | 0 | 4 | |
30 | 330833 | 2881 | 20 | 0 | 5 | 0 | 0 |
The following table shows, for those shapes tiling by translation, how many do or do not also tile by 180° rotation.
n | 180° as well | translation only |
---|---|---|
2 | 1 | 0 |
4 | 2 | 0 |
6 | 8 | 0 |
8 | 24 | 0 |
10 | 61 | 1 |
12 | 269 | 22 |
14 | 501 | 38 |
16 | 2121 | 504 |
18 | 4709 | 1468 |
20 | 14978 | 6945 |
22 | 26675 | 11046 |
24 | 123081 | 115186 |
26 | 179707 | 119496 |
28 | 660366 | 677774 |
30 | 1479114 | 2013619 |
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:
.
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).
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ∞ | skipped |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 0 |
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 5 | 0 |
5 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 11 | 0 |
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 35 | 0 |
7 | 6 | 6 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 89 | 0 |
8 | 20 | 18 | 4 | 2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 298 | 0 |
9 | 193 | 84 | 14 | 6 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 752 | 0 |
10 | 749 | 257 | 41 | 2 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 2018 | 0 |
11 | 3222 | 809 | 148 | 31 | 12 | 3 | 2 | 0 | 0 | 1 | 0 | 2392 | 0 |
12 | 9026 | 1440 | 153 | 22 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 12803 | 1 |
13 | 25090 | 3645 | 435 | 94 | 25 | 4 | 3 | 3 | 0 | 0 | 0 | 9368 | 2 |
14 | 63746 | 5681 | 416 | 56 | 17 | 2 | 1 | 0 | 0 | 0 | 0 | 39176 | 9 |
15 | 180669 | 11842 | 665 | 85 | 13 | 1 | 0 | 1 | 0 | 0 | 0 | 86306 | 1 |
16 | 366557 | 16758 | 1128 | 142 | 37 | 6 | 2 | 0 | 0 | 0 | 0 | 162257 | 6 |
17 | 683157 | 30733 | 1473 | 264 | 63 | 9 | 2 | 1 | 0 | 0 | 0 | 111321 | 12 |
18 | 2192816 | 65557 | 2226 | 238 | 31 | 1 | 1 | 1 | 0 | 0 | 0 | 796444 | 17 |
19 | 2936540 | 72811 | 2130 | 360 | 96 | 7 | 2 | 1 | 1 | 1 | 1 | 369160 | 14 |
20 | 9444080 | 126363 | 3550 | 322 | 68 | 42 | 1 | 1 | 0 | 0 | 0 | 2552238 | 18 |
21 | 18299457 | 221446 | 4767 | 458 | 90 | 14 | 0 | 0 | 2 | 0 | 0 | 3394939 | 19 |
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ∞ | skipped |
---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 0 |
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 0 |
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 22 | 0 |
6 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 75 | 0 |
7 | 28 | 8 | 4 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 252 | 1 |
8 | 196 | 70 | 13 | 4 | 0 | 0 | 1 | 0 | 0 | 0 | 770 | 0 |
9 | 1085 | 224 | 41 | 7 | 1 | 0 | 0 | 0 | 0 | 0 | 2425 | 5 |
10 | 3869 | 640 | 64 | 14 | 1 | 0 | 0 | 0 | 0 | 0 | 6738 | 0 |
11 | 13782 | 1840 | 212 | 34 | 8 | 1 | 1 | 0 | 1 | 0 | 8911 | 0 |
12 | 53467 | 5108 | 369 | 29 | 3 | 1 | 0 | 0 | 0 | 0 | 44661 | 3 |
13 | 116624 | 8357 | 619 | 92 | 20 | 4 | 4 | 0 | 0 | 0 | 38809 | 30 |
14 | 349511 | 16146 | 656 | 84 | 10 | 6 | 0 | 0 | 0 | 0 | 166088 | 9 |
15 | 1094609 | 35174 | 1231 | 84 | 8 | 1 | 0 | 0 | 0 | 0 | 443142 | 3 |
16 | 2260495 | 50854 | 1878 | 188 | 32 | 4 | 0 | 0 | 0 | 1 | 626405 | 41 |
17 | 4040091 | 78581 | 1748 | 269 | 33 | 3 | 1 | 0 | 0 | 0 | 640255 | 28 |
n | 1 | 2 | 3 | 4 | 5 | 6 | ∞ | skipped |
---|---|---|---|---|---|---|---|---|
1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
2 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
3 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
4 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 0 |
5 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 |
6 | 2 | 0 | 0 | 0 | 0 | 0 | 10 | 0 |
7 | 0 | 0 | 0 | 0 | 0 | 0 | 23 | 0 |
8 | 2 | 0 | 0 | 0 | 0 | 0 | 64 | 0 |
9 | 18 | 8 | 2 | 0 | 0 | 0 | 111 | 0 |
10 | 62 | 15 | 3 | 0 | 0 | 0 | 261 | 0 |
11 | 284 | 64 | 8 | 1 | 0 | 0 | 210 | 0 |
12 | 491 | 90 | 12 | 1 | 0 | 0 | 1440 | 0 |
13 | 1623 | 249 | 30 | 7 | 0 | 0 | 586 | 0 |
14 | 2995 | 321 | 16 | 2 | 2 | 0 | 3018 | 0 |
15 | 7665 | 507 | 14 | 0 | 0 | 0 | 4722 | 0 |
16 | 15640 | 842 | 37 | 14 | 2 | 1 | 13725 | 0 |
17 | 22755 | 1214 | 34 | 0 | 1 | 0 | 2552 | 0 |
18 | 67185 | 2745 | 93 | 20 | 2 | 0 | 40095 | 5 |
19 | 85741 | 2846 | 61 | 6 | 0 | 0 | 7313 | 0 |
20 | 248302 | 5394 | 147 | 39 | 10 | 2 | 123623 | 6 |
21 | 401673 | 7216 | 107 | 2 | 0 | 0 | 90674 | 0 |
The general algorithm used by my programs for determining whether polyforms tile, and how simply, is as follows.
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:
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:
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.
The list here is deliberately very selective, giving general survey references rather than tracking results and terminology back to their original sources.
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. Unfortunately it has gone out of print and there is no second edition or other comparable work covering the many subsequent developments in tiling.
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.
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^{2}, with a finite number of inflection points”.
Return to my mathematics page
Return to my home page