Product Code Database
A polyomino is a Shape formed by joining one or more equal 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 since at least 1907, and the enumeration of is dated to antiquity.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". 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, and it was popularized by Martin Gardner in a November 1960 "Mathematical Games" column in Scientific American.
Related to polyominoes are , formed from equilateral triangles; polyhexes, formed from regular ; and other plane . Polyominoes have been generalized to higher by joining cubes to form , or 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.
Like many puzzles in recreational mathematics, polyominoes raise many combinatorial problems. The most basic is enumeration 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 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.
The following table shows the numbers of polyominoes of various types with n cells.
| 1 | ||||||
| 2 | ||||||
| 6 | ||||||
| 19 | ||||||
| 63 | ||||||
| 216 | ||||||
| 760 | ||||||
| 2,725 | ||||||
| 9,910 | ||||||
| 36,446 | ||||||
| 135,268 | ||||||
| 505,861 | ||||||
| OEIS sequence | ||||||
Fixed polyominoes were enumerated in 2004 up to n = 56 by Iwan Jensen, and in 2024 up to n = 70 by Gill Barequet and Gil Ben-Shachar. (2024). 9781611977929, Society for Industrial and Applied Mathematics. ISBN 9781611977929
Free polyominoes were enumerated in 2007 up to n = 28 by Tomás Oliveira e Silva, in 2012 up to n = 45 by Toshihiro Shirakawa, and in 2023 up to n = 50 by John Mason.
The above OEIS sequences, with the exception of A001419, include the count of 1 for the number of null-polyominoes; a null-polyomino is one that is formed of zero squares.
Polyominoes have the following possible symmetries;Redelmeier, section 3 the least number of squares needed in a polyomino with that symmetry is given in each case:
In the same way, the number of one-sided polyominoes depends on polyomino symmetry as follows:
The following table shows the numbers of polyominoes with n squares, sorted by symmetry groups.
| 1 | ||||||||
| 0 | ||||||||
| 0 | ||||||||
| 1 | ||||||||
| 1 | ||||||||
| 0 | ||||||||
| 0 | ||||||||
| 1 | ||||||||
| 2 | ||||||||
| 0 | ||||||||
| 0 | ||||||||
| 3 | ||||||||
| OEIS sequence |
Most simply, given a list of polyominoes of size n, squares may be added next to each polyomino in each possible position, and the resulting polyomino of size n+1 added to the list if not a duplicate of one already found; refinements in ordering the enumeration and marking adjacent squares that should not be considered reduce the number of cases that need to be checked for duplicates.Golomb, pp. 73–79 This method may be used to enumerate either free or fixed polyominoes.
A more sophisticated method, described by Redelmeier, has been used by many authors as a way of not only counting polyominoes (without requiring that all polyominoes of size n be stored in size to enumerate those of size n+1), but also proving upper bounds on their number. The basic idea is that we begin with a single square, and from there, recursively add squares. Depending on the details, it may count each n-omino n times, once from starting from each of its n squares, or may be arranged to count each once only.
The simplest implementation involves adding one square at a time. Beginning with an initial square, number the adjacent squares, clockwise from the top, 1, 2, 3, and 4. Now pick a number between 1 and 4, and add a square at that location. Number the unnumbered adjacent squares, starting with 5. Then, pick a number larger than the previously picked number, and add that square. Continue picking a number larger than the number of the current square, adding that square, and then numbering the new adjacent squares. When n squares have been created, an n-omino has been created.
This method ensures that each fixed polyomino is counted exactly n times, once for each starting square. It can be optimized so that it counts each polyomino only once, rather than n times. Starting with the initial square, declare it to be the lower-left square of the polyomino. Simply do not number any square that is on a lower row, or left of the square on the same row. This is the version described by Redelmeier.
If one wishes to count free polyominoes instead, then one may check for symmetries after creating each n-omino. However, it is fasterRedelmeier, section 4 to generate symmetric polyominoes separately (by a variation of this method)Redelmeier, section 6 and so determine the number of free polyominoes by Burnside's lemma.
As a rule, TMAs are much faster than the previous methods, but still run in time that is exponential in n. Roughly, this is achieved by fixing a width (in the diagonal case, a diagonal width), and counting polyominoes that fit in rectangles of that width. If this is done, it is only necessary to keep track of a polyomino's boundary, and since multiple polyominoes can correspond to a single boundary, this approach is faster than one generating every polyomino. Repeating this for every width gives every polyomino.
Although it has excellent running time, the tradeoff is that this algorithm uses exponential amounts of memory (many of memory are needed for n above 50), is much harder to program than the other methods, and cannot currently be used to count free polyominoes.
where λ = 4.0626 and c = 0.3169. However, this result is not proven and the values of λ and c are only estimates.
The known theoretical results are not nearly as specific as this estimate. It has been proven that
exists. In other words, An grows exponentially. The best known lower bound for λ, found in 2016, is 4.00253. The best known upper bound is .
To establish a lower bound, a simple but highly effective method is concatenation of polyominoes. Define the upper-right square to be the rightmost square in the uppermost row of the polyomino. Define the bottom-left square similarly. Then, the upper-right square of any polyomino of size n can be attached to the bottom-left square of any polyomino of size m to produce a unique ( n+ m)-omino. This proves . Using this equation, one can show for all n. Refinements of this procedure combined with data for An produce the lower bound given above.
The upper bound is attained by generalizing the inductive method of enumerating polyominoes. Instead of adding one square at a time, one adds a cluster of squares at a time. This is often described as adding twigs. By proving that every n-omino is a sequence of twigs, and by proving limits on the combinations of possible twigs, one obtains an upper bound on the number of n-ominoes. For example, in the algorithm outlined above, at each step we must choose a larger number, and at most three new numbers are added (since at most three unnumbered squares are adjacent to any numbered square). This can be used to obtain an upper bound of 6.75. Using 2.8 million twigs, Klarner and Ron Rivest obtained an upper bound of 4.65, which was subsequently improved by Barequet and Shalah to 4.5252.
The definition of a convex polyomino is different from the usual definition of Convex set, but is similar to the definition used for the orthogonal convex hull. A polyomino is said to be vertically or column convex if its intersection with any vertical line is convex (in other words, each column has no holes). Similarly, a polyomino is said to be horizontally or row convex if its intersection with any horizontal line is convex. A polyomino is said to be convex if it is row and column convex.
A polyomino is said to be directed if it contains a square, known as the root, such that every other square can be reached by movements of up or right one square, without leaving the polyomino.
Directed polyominoes, column (or row) convex polyominoes, and convex polyominoes have been effectively enumerated by area n, as well as by some other parameters such as perimeter, using generating functions.
A polyomino is equable shape if its area equals its perimeter. An equable polyomino must be made from an even number of squares; every even number greater than 15 is possible. For instance, the 16-omino in the form of a 4 × 4 square and the 18-omino in the form of a 3 × 6 rectangle are both equable. For polyominoes with 15 squares or fewer, the perimeter always exceeds the area..
Because the general problem of tiling regions of the plane with sets of polyominoes is NP-complete, 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.
In Jigsaw Sudokus a square grid is tiled with polyomino-shaped regions .
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).
In 2001 Cris Moore and John Michael Robson showed that the problem of tiling one polyomino with copies of another is NP-complete..
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.
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 , it is possible to combine 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.
|
|
