Editing Polyomino (section)

===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}}.