A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling.
Polyominoes have been used in popular puzzles since at least 1907, and the enumeration of pentominoes is dated to antiquity.[1] Many results with the pieces of 1 to 6 squares were first published in Fairy Chess Review between the years 1937 and 1957, under the name of "dissection problems." The name polyomino was invented by Solomon W. Golomb in 1953,[2] and it was popularized by Martin Gardner in a November 1960 "Mathematical Games" column in Scientific American.[3]
Related to polyominoes are polyiamonds, formed from equilateral triangles; polyhexes, formed from regular hexagons; and other plane polyforms. Polyominoes have been generalized to higher dimensions by joining cubes to form polycubes, or hypercubes to form polyhypercubes.
In statistical physics, the study of polyominoes and their higher-dimensional analogs (which are often referred to as lattice animals in this literature) is applied to problems in physics and chemistry. Polyominoes have been used as models of branched polymers and of percolation clusters.[4]
Like many puzzles in recreational mathematics, polyominoes raise many combinatorial problems. The most basic is enumerating polyominoes of a given size. No formula has been found except for special classes of polyominoes. A number of estimates are known, and there are algorithms for calculating them.
Polyominoes with holes are inconvenient for some purposes, such as tiling problems. In some contexts polyominoes with holes are excluded, allowing only simply connected polyominoes.[5]
- ^ Golomb (Polyominoes, Preface to the First Edition) writes "the observation that there are twelve distinctive patterns (the pentominoes) that can be formed by five connected stones on a Go board ... is attributed to an ancient master of that game".
- ^ Golomb, Solomon W. (1994). Polyominoes (2nd ed.). Princeton, New Jersey: Princeton University Press. ISBN 978-0-691-02444-8.
- ^ Gardner, M. (November 1960). "More about the shapes that can be made with complex dominoes (Mathematical Games)". Scientific American. 203 (5): 186–201. doi:10.1038/scientificamerican1160-186. JSTOR 24940703.
- ^ Whittington, S. G.; Soteros, C. E. (1990). "Lattice Animals: Rigorous Results and Wild Guesses". In Grimmett, G.; Welsh, D. (eds.). Disorder in Physical Systems. Oxford University Press.
- ^ Grünbaum, Branko; Shephard, G.C. (1987). Tilings and Patterns. New York: W.H. Freeman and Company. ISBN 978-0-7167-1193-3.