Polyomino Guide, Meaning , Facts, Information and Description
A polyomino is a polyform with the square as its base form. It is constructed by placing a number of identical squares in distinct locations on the plane in such a way that at least one edge of each square coincides with an edge of one of the remaining squares, and all squares are simply connected. If the corner of any square touches the edge of another square at any place other than a corner, the result is not a polyomino. For each strictly positive natural number, n, there are a finite number of distinct such arrangements of the n squares. There are two common ways of defining distinct polyominoes: free polyominos must be different under translation, rotation, and reflection, while fixed polyominos must be different only under translation. Therefore, there are always fewer free polyominos than fixed polyominos.In some contexts the definition of a polyomino is relaxed. Sometimes polyominoes are generalised to three or more dimensions by aggregating cubes or hypercubes. For some applications mirror image forms are treated as distinct.
The numbers of configurations for free polyominoes are listed below.
- 1 square: monomino: 1 configuration
- 2 squares: domino: 1
- 3 squares: triomino or tromino: 2
- 4 squares: tetromino: 5
- 5 squares: pentomino: 12
- 6 squares: hexomino: 35
- 7 squares: heptomino: 108 (including 1 configuration with a hole)
- 8 squares: octomino: 369 (including 6 with holes)
- 9 squares: nonomino: 1285 (37 with holes)
- 10 squares: decomino: 4655 (195 with holes)
- 11 squares: undecomino: 17073 (979 with holes)
- 12 squares: dodecomino: 63600 (4663 with holes)
No formula for finding the exact number of polyominoes with n squares has been found. However, a number of estimates are known, and there are algorithms for counting them; see below for more information.
Polyominoes composed of seven or more squares may contain holes (that is, regions which are not tiled with squares but which are unconnected to the exterior of the polyomino).
Polyominoes have been used in popular puzzles since the late 19th century, but were first studied systematically by Solomon W. Golomb and were popularized by Martin Gardner. Related to polyominoes are polyiamonds (formed from equilateral triangles) and polyhexes (formed from regular hexagons). The game Tetris is based tetrominoes.
| Table of contents |
|
2 Algorithms for enumerating all n-ominoes (polyominoes of n squares) 3 The number of polyominoes 4 See also 5 External links |
Due to the variety of different shapes that polyominoes can have, when studying them it is useful to be able to classify them according to various properties. Basic properties include whether it has holes, its symmetry group (that is, all the ways it can be rotated and reflected to produce a different configuration), the smallest rectangle it can be embedded in, and its perimeter.
Another way of characterizing polyominoes is by a special definition of convexity. A polyomino is said to be column convex if its intersection with any vertical line is convex. In other words, less formally, each column has no holes. Similarly, a polyomino is 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 polymino 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 polyominos, and convex polyominoes have been effectively enumerated for all n using generating functions.
The most obvious method of enumerating the polyominoes, and also one of the slowest, is inductive exhaustive search. Given a list of polyominoes of area n, take each polyomino in turn, embed it in an n×n square, surround that square with a collar of cells to create an (n+2)×(n+2) square. For each vacant cell in that square that is adjacent to at least one occupied cell, fill the cell and strike out a bounding row of vacant cells and a bounding column of vacant cells. The resulting (n+1)×(n+1) square contains a candidate polyomino of area n+1. If this configuration has not been encountered before, it is added to the list of polyominoes of area n+1. Comparison with the polyominoes of area n+1 already seen must take account of position and symmetry, depending on whether fixed or free polyominoes are being counted. Position can be accounted for by translating the candidate polyomino to the top left corner of the (n+1)×(n+1) square. Symmetry can be accounted for by noting that the group of symmetries of a square has eight elements and is generated by alternating reflections about the x-axis and about a diagonal.
This procedure can be applied repeatedly starting from the monomino to reach any desired area of polyomino, but this becomes computationally expensive for large areas. For example finding all the dodecominoes using this algorithm consumes nearly 90 seconds of CPU time on a 1 GHz Pentium.
This method has been used by many authors as a way of not only counting polyominoes, 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. It will count each n-omino n times, once from starting from each of its n squares.
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 1-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. If one wishes to count free polyominoes instead, then one must check for symmetries after creating each n-omino. This algorithm can enumerate the dodecominoes in about 20 seconds on a 1 GHz Pentium. The running time scales proportionally to the number of polyominoes.
This method 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 which is on a lower row, or left of the square on the same row. With this improvement, the running time is divided by n, so it only takes about 1 second to enumerate the dodecominoes.
The most modern algorithm for enumerating the fixed polyominoes was discovered by Iwan Jensen. An improvement on Conway's method, it is exponentially faster than the previous methods (however its running time is still exponential). However, it cannot be used to enumerate the free polyominoes, and it is complex to program and requires enormous amounts of memory.
As of 2004, Jensen has enumerated the fixed polyominoes up to n=56, of which there are approximately . Free polyominoes have been enumerated up to n=28. See the external links for tables containing the known results.
A number of methods of estimating the number of polyominoes have been proposed, but no exact formula is known. Let denote the number of fixed polyominoes (the A is for animal, another name for polyforms). It has been proven that is approximately eight times the number of free polyominoes, with the approximation being exponentially more accurate as n increases. Therefore, obtaining estimates for the fixed polyominoes give us very good estimates for the number of free polyominoes.
Theoretical arguments and numerical calculations support the estimate
where and . However, it should be emphasized that 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, grows exponentially. The best known lower bound for is 3.90. The best known upper bound, not improved since the 1970s, 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, we can attach the upper-right square of any polyomino of size n 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 produce the lower bound given above.
The upper bound is attained by generalizing the Growth Method of enumerating polyominos. 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 there new 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 Rivest obtained an upper bound of 4.65. Undoubtedly, modern computers could carry the calculation to larger twigs, but no better results have been published.
This is an Article on Polyomino. Page Contains Information, Facts Details or Explanation Guide About Polyomino Special classes of polyominoes
Algorithms for enumerating all n-ominoes (polyominoes of n squares)
Inductive exhaustive search
Growth method
Conway's method
Jensen's method
The number of polyominoes
External links