Editing Polyomino (section)

==Tiling with polyominoes==
In [[recreational mathematics]], challenges are often posed for [[Tessellation|tiling]] a prescribed region, or the entire plane, with polyominoes,<ref>{{cite book |last=Martin |first=George E. |title=Polyominoes: A guide to puzzles and problems in tiling |url=https://archive.org/details/polyominoesguide00mart_0 |url-access=registration |year=1996 |edition=2nd |publisher=[[Mathematical Association of America]] |isbn=978-0-88385-501-0}}</ref> and related problems are investigated in [[mathematics]] and [[computer science]].

===Tiling regions with sets of polyominoes===
Puzzles commonly ask for tiling a given region with a given set of polyominoes, such as the 12 pentominoes. Golomb's and Gardner's books have many examples. A typical puzzle is to tile a 6×10 rectangle with the twelve pentominoes; the 2339 solutions to this were found in 1960.<ref>{{cite journal |author=C.B. Haselgrove |author2=Jenifer Haselgrove |date=October 1960 |title=A Computer Program for Pentominoes |journal=[[Eureka (University of Cambridge magazine)|Eureka]] |volume=23 |pages=16–18|url=https://www.archim.org.uk/eureka/archive/Eureka-23.pdf}}</ref> Where multiple copies of the polyominoes in the set are allowed, Golomb defines a hierarchy of different regions that a set may be able to tile, such as rectangles, strips, and the whole plane, and shows that whether polyominoes from a given set can tile the plane is [[recursive set|undecidable]], by mapping sets of [[Wang tile]]s to sets of polyominoes.<ref>{{cite journal |last=Golomb |first=Solomon W. |year=1970 |title=Tiling with Sets of Polyominoes |journal=Journal of Combinatorial Theory |volume=9 |pages=60–71 |doi=10.1016/S0021-9800(70)80055-2|doi-access=free }}</ref> 

Because the general problem of tiling regions of the plane with sets of polyominoes is [[NP-complete]],<ref>{{cite journal |author=E.D. Demaine |author2=M.L. Demaine |date=June 2007 |title=Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity |journal=Graphs and Combinatorics |volume=23 |pages=195–208|doi=10.1007/s00373-007-0713-4 |s2cid=17190810 |url=https://link.springer.com/article/10.1007/s00373-007-0713-4}}</ref> tiling with more than a few pieces rapidly becomes intractable and so the aid of a computer is required. The traditional approach to tiling finite regions of the plane uses a technique in computer science called [[backtracking]].<ref>{{cite journal |author=S.W. Golomb |author2=L.D. Baumert |year=1965 |title=Backtrack Programming |journal=Journal of the ACM |volume=12 |issue=4 |pages=516–524 |doi=10.1145/321296.321300|doi-access=free }}</ref> 

In [[Sudoku#Variants|Jigsaw Sudokus]] a square grid is tiled with polyomino-shaped regions {{OEIS|A172477}}.

===Tiling regions with copies of a single polyomino===
Another class of problems asks whether copies of a given polyomino can tile a [[rectangle]], and if so, what rectangles they can tile.<ref>Golomb, ''Polyominoes'', chapter 8</ref> These problems have been extensively studied for particular polyominoes,<ref>{{cite web |url=http://www.math.ucf.edu/~reid/Polyomino/rectifiable_bib.html |title=References for Rectifiable Polyominoes |access-date=2007-05-11 |last=Reid |first=Michael |url-status=dead |archive-url=https://web.archive.org/web/20040116204311/http://www.math.ucf.edu/~reid/Polyomino/rectifiable_bib.html |archive-date=2004-01-16 }}</ref> and tables of results for individual polyominoes are available.<ref>{{cite web |url=http://www.math.ucf.edu/~reid/Polyomino/rectifiable_data.html |title=List of known prime rectangles for various polyominoes |access-date=2007-05-11 |last=Reid |first=Michael |url-status=dead |archive-url=https://web.archive.org/web/20070416210221/http://www.math.ucf.edu/~reid/Polyomino/rectifiable_data.html |archive-date=2007-04-16 }}</ref> [[David A. Klarner|Klarner]] and Göbel showed that for any polyomino there is a finite set of ''prime'' rectangles it tiles, such that all other rectangles it tiles can be tiled by those prime rectangles.<ref>{{cite journal |last=Klarner |first=D.A. |author2=Göbel, F. |year=1969 |title=Packing boxes with congruent figures |journal=Indagationes Mathematicae |volume=31 |pages=465–472}}</ref><ref>{{cite web |url=http://historical.ncstrl.org/litesite-data/stan/CS-TR-73-338.pdf |title=A Finite Basis Theorem Revisited |access-date=2007-05-12 |last=Klarner |first=David A. |date=February 1973 |publisher=Stanford University Technical Report STAN-CS-73–338 |url-status=dead |archive-url=https://web.archive.org/web/20071023221204/http://historical.ncstrl.org/litesite-data/stan/CS-TR-73-338.pdf |archive-date=2007-10-23 }}</ref> Kamenetsky and Cooke showed how various disjoint (called "holey") polyominoes can tile rectangles.<ref>{{cite arXiv |eprint=1411.2699 |title=Tiling rectangles with holey polyominoes|last=Kamenetsky |first=Dmitry | author2=Cooke, Tristrom |date=2015|class=cs.CG}}</ref>

Beyond rectangles, Golomb gave his hierarchy for single polyominoes: a polyomino may tile a rectangle, a half strip, a bent strip, an enlarged copy of itself, a quadrant, a strip, a [[half plane]], the whole plane, certain combinations, or none of these. There are certain implications among these, both obvious (for example, if a polyomino tiles the half plane then it tiles the whole plane) and less so (for example, if a polyomino tiles an enlarged copy of itself, then it tiles the quadrant). Polyominoes of size up to 6 are characterized in this hierarchy (with the status of one hexomino, later found to tile a rectangle, unresolved at that time).<ref>{{cite journal |last=Golomb |first=Solomon W. |year=1966 |title=Tiling with Polyominoes |journal=Journal of Combinatorial Theory |volume=1 |pages=280–296 |issue=2 |doi=10.1016/S0021-9800(66)80033-9|doi-access=free }}</ref>

In 2001 [[Cris Moore|Cristopher Moore]] and John Michael Robson showed that the problem of tiling one polyomino with copies of another is [[NP-complete]].<ref>{{cite web |last1=Moore |first1=Cristopher |author-link1=Cris Moore |last2=Robson |first2=John Michael |title=Hard Tiling Problems with Simple Tiles |year=2001 |url=http://www.santafe.edu/media/workingpapers/00-03-019.pdf |archive-url=https://web.archive.org/web/20130617140921/http://www.santafe.edu/media/workingpapers/00-03-019.pdf |url-status=dead |archive-date=2013-06-17 }}</ref><ref>{{citation|first=Ivars|last=Petersen|title=Math Trek: Tiling with Polyominoes|date=September 25, 1999|journal=[[Science News]]|url=http://www.sciencenews.org/pages/sn_arc99/9_25_99/mathland.htm|access-date=March 11, 2012|archive-url=https://web.archive.org/web/20080320031732/http://www.sciencenews.org/pages/sn_arc99/9_25_99/mathland.htm|archive-date=March 20, 2008|url-status=live|df=mdy-all}}.</ref>

===Tiling the plane with copies of a single polyomino===
[[File:Conway criterion false negative nonominoes.svg|thumb|180px|The two tiling nonominoes not satisfying the Conway criterion.]]
Tiling the plane with copies of a single polyomino has also been much discussed. It was noted in 1965 that all polyominoes up to hexominoes<ref>{{cite journal |last=Gardner |first=Martin |date=July 1965 |title=On the relation between mathematics and the ordered patterns of Op art |journal=[[Scientific American]] |volume=213 |issue=1 |pages=100–104|doi=10.1038/scientificamerican1265-100 }}</ref> and all but four heptominoes tile the plane.<ref>{{cite journal |last=Gardner |first=Martin |date=August 1965 |title=Thoughts on the task of communication with intelligent organisms on other worlds |journal=[[Scientific American]] |volume=213 |issue=2 |pages=96–100|doi=10.1038/scientificamerican0865-96 }}</ref> It was then established by David Bird that all but 26 octominoes tile the plane.<ref>{{cite journal |last=Gardner |first=Martin |date=August 1975 |title=More about tiling the plane: the possibilities of polyominoes, polyiamonds and polyhexes |journal=[[Scientific American]] |volume=233 |issue=2 |pages=112–115|doi=10.1038/scientificamerican0875-112 }}</ref> Rawsthorne found that all but 235 polyominoes of size 9 tile,<ref>{{cite journal |last=Rawsthorne |first=Daniel A. |year=1988 |title=Tiling complexity of small ''n''-ominoes<br/>(''n''<10) |journal=Discrete Mathematics |volume=70 |pages=71–75 |doi=10.1016/0012-365X(88)90081-7|doi-access=free }}</ref> and such results have been extended to higher area by Rhoads (to size 14)<ref>{{cite book |last=Rhoads |first=Glenn C. |title=Planar Tilings and the Search for an Aperiodic Prototile |year=2003 |publisher=PhD dissertation, Rutgers University}}</ref> and others. Polyominoes tiling the plane have been classified by the symmetries of their tilings and by the number of aspects (orientations) in which the tiles appear in them.<ref>Grünbaum and Shephard, section 9.4</ref><ref>{{cite journal |last=Keating |first=K. |author2=Vince, A. |year=1999 |title=Isohedral Polyomino Tiling of the Plane |journal=[[Discrete & Computational Geometry]] |volume=21 |pages=615–630 |doi=10.1007/PL00009442 |issue=4|doi-access=free }}</ref>

The study of which polyominoes can tile the plane has been facilitated using the [[Conway criterion]]: except for two nonominoes, all tiling polyominoes up to size 9 form a patch of at least one tile satisfying it, with higher-size exceptions more frequent.<ref>{{cite journal |last=Rhoads |first=Glenn C. |year=2005 |title=Planar tilings by polyominoes, polyhexes, and polyiamonds |journal=Journal of Computational and Applied Mathematics |volume=174 |pages=329–353 |doi=10.1016/j.cam.2004.05.002 |issue=2|bibcode=2005JCoAM.174..329R |doi-access=free }}</ref>

Several polyominoes can tile larger copies of themselves, and repeating this process recursively gives a [[rep-tile]] tiling of the plane. For instance, for every positive integer {{mvar|n}}, it is possible to combine {{math|''n''<sup>2</sup>}} copies of the L-tromino, L-tetromino, or P-pentomino into a single larger shape similar to the smaller polyomino from which it was formed.<ref>{{citation
 | last = Niţică | first = Viorel
 | contribution = Rep-tiles revisited
 | location = Providence, RI
 | mr = 2027179
 | pages = 205–217
 | publisher = American Mathematical Society
 | title = MASS selecta
 | year = 2003
 | mode = cs1}}</ref>
{{Clear}}

===Tiling a common figure with various polyominoes===
[[Image:PentominoCompatibilityTW.svg|thumb|A minimal compatibility figure for the T and W [[pentomino]]es.]]
The ''compatibility problem'' is to take two or more polyominoes and find a figure that can be tiled with each. Polyomino compatibility has been widely studied since the 1990s. Jorge Luis Mireles and Giovanni Resta have published websites of systematic results,<ref>[https://web.archive.org/web/20091027093922/http://geocities.com/jorgeluismireles/polypolyominoes/ Mireles, J.L., "Poly<sup>2</sup>ominoes"]</ref><ref>{{Cite web |url=http://www.iread.it/Poly/ |title=Resta, G., "Polypolyominoes" |access-date=2010-07-02 |archive-url=https://web.archive.org/web/20110222051130/http://www.iread.it/Poly/ |archive-date=2011-02-22 |url-status=live }}</ref> and Livio Zucca shows results for some complicated cases like three different pentominoes.<ref>{{Cite web |url=http://sicherman.net/rosp/triplep.html |title=Zucca, L., "Triple Pentominoes" |access-date=2023-04-20 }}</ref> The general problem can be hard. The first compatibility figure for the L and X pentominoes was published in 2005 and had 80 tiles of each kind.<ref>{{cite book  |last1=Barbans |first1=Uldis |last2=Cibulis |first2=Andris |last3=Lee |first3=Gilbert |last4=Liu |first4=Andy |last5=Wainwright |first5=Robert |contribution=Polyomino Number Theory (III) |editor-last=Cipra |editor-first=Barry Arthur|editor-link = Barry Arthur Cipra |editor2-last=Demaine |editor2-first=Erik D. |editor3-last=Demaine |editor3-first=Martin L. |editor4-last=Rodgers |editor4-first=Tom |title=Tribute to a Mathemagician |place=Wellesley, MA |publisher=A.K. Peters |year=2005 |pages=131–136 |isbn=978-1-56881-204-5}}</ref> Many pairs of polyominoes have been proved incompatible by systematic exhaustion. No algorithm is known for deciding whether two arbitrary polyominoes are compatible.