Polyomino

From Wikipedia, the free encyclopedia

You have new messages (last change).
The 35 possible hexominoes.
The 35 possible hexominoes.

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, keeping the shape connected, and in such a way that at least one edge of each square coincides with an edge of one of the other squares. Polyominoes with from 1 to 6 squares are called respectively monominoes, dominoes, trominoes (or triominoes), tetrominoes, pentominoes and hexominoes. Related to polyominoes are polyiamonds (formed from equilateral triangles), polyhexes (formed from regular hexagons), and other polyforms.

In some contexts, the definition of a polyomino is relaxed or refined. Sometimes it is requested that polyominoes are simply connected, while on other occasions may have holes (in other words, regions which are not tiled with squares but which are unconnected to the exterior of the polyomino). Sometimes polyominoes are generalised to three or more dimensions by aggregating cubes (polycube)or hypercubes.

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. The game Tetris is based on tetrominoes.

Polyominoes are a source of combinatorial problems, the first being to enumerate polyominoes for various sizes. No formula has been found except for special classes of polyominoes. However, a number of estimates are known, and there are algorithms for counting them.

Contents

[edit] Free, one-sided, and fixed polyominoes

There are three common ways of defining distinct polyominoes:

  • free polyominoes are distinct from each other as long as none is a translation, rotation, or reflection of another
  • one-sided polyominoes are distinct as long as none is a translation or rotation of another
  • fixed polyominoes are distinct as long as none is a translation of another.

The dihedral group D4 is the group of symmetries (symmetry group) of a square. This group contains four rotations and four reflections. It is generated by alternating reflections about the x-axis and about a diagonal. One free polyomino corresponds to at most 8 fixed polyominoes, which are its symmetric images under the symmetries of D4. However, those images are not necessarily distinct: the more symmetry a free polyomino has, the less distinct fixed versions there are. Therefore, a free polyomino which is invariant under some or all non-trivial symmetries of D4 may correspond to only 4, 2 or 1 fixed polyominoes. Mathematically, free polyominoes are equivalence classes of fixed polyominoes under the group D4.

Possible symmetries (with the least number of squares needed in a polyomino):

  • 8 fixed polyominoes for each free polyomino:
    • no symmetry (4)
  • 4 fixed polyominoes for each free polyomino:
    • symmetry with respect to one of the grid line directions (4)
    • symmetry with respect to a diagonal line (3)
    • 2-fold rotational symmetry (4)
  • 2 fixed polyominoes for each free polyomino:
    • symmetry with respect to both grid line directions, and hence also 2-fold rotational symmetry (2)
    • symmetry with respect to both diagonal directions, and hence also 2-fold rotational symmetry (7)
    • 4-fold rotational symmetry (8)
  • 1 fixed polyomino for each free polyomino:
    • all symmetry of the square (1)

[edit] Special polyominoes

A straight polyomino is a polyomino with all of the squares in a line.

A T-polyomino is a polyomino in the shape of a T, with three squares in the crossbar at the top of the T.

An L-polyomino is a polyomino in the shape of an L, formed by adding a single square to a straight polyomino.

A square polyomino is a polyomino in the shape of a square.

A skew polyomino is formed by joining two straight polyominoes of the same length, so that the right end square of one is directly above the left end square of the other.

[edit] Number of polyominoes

We call n the number of squares, and An the number of fixed polyominoes with n squares (possibly with holes). An enumeration gives the following table:

n name number of free polyominoes (sequence A000105 in OEIS) number of free polyominoes with holes (A001419) number of one-sided polyominoes (A000988) An = number of fixed polyominoes (A001168)
1 monomino 1 0 1 1
2 domino 1 0 1 2
3 tromino or triomino 2 0 2 6
4 tetromino 5 0 7 19
5 pentomino 12 0 18 63
6 hexomino 35 0 60 216
7 heptomino 108 1 196 760
8 octomino 369 6 704 2725
9 nonomino 1285 37 2500 9910
10 decomino 4655 195 9189 36446
11 undecomino 17073 979 33896 135268
12 dodecomino 63600 4663 126759 505861

The number of free polyominoes without holes is given by A000104.

As of 2004, Iwan Jensen has enumerated the fixed polyominoes up to n=56: A56 is approximately 6.915×1031. Free polyominoes have been enumerated up to n=28. See the external links for tables containing the known results.

[edit] Algorithms for enumeration of fixed polyominoes

[edit] Inductive exhaustive search

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. In order to compute the number of fixed polyominoes, rotations and reflections must also be accounted for.

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.

[edit] Growth method

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

[edit] Conway's method and Jensen's method

The most modern algorithm for enumerating the fixed polyominoes was discovered by Iwan Jensen. An improvement on Andrew Conway's method, it is exponentially faster than the previous methods (however its running time is still exponential on n).

Both Conway's and Jensen's method involve counting the number of polyominoes that have a certain width. Computing the number for all widths gives the total number of polyominoes. The basic idea behind the method is that possible beginning rows are considered, and then to determine the minimum number of squares needed to complete the polyomino of the given width. Combined with the use of generating functions, this technique is able to count many polyominoes at once, thus enabling it to run many times faster than methods that have to generate every polyomino.

Although it has excellent running time, the tradeoff is that this algorithm uses exponential amounts of memory (many gigabytes 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.

[edit] Asymptotic growth of the number of polyominoes

[edit] Fixed polyominoes

Theoretical arguments and numerical calculations support the estimate

A_n \sim \frac{c\lambda^n}{n}

where λ = 4.0626 and c = 0.3024. 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

\lim_{n\rightarrow \infty} (A_n)^{1/n} = \lambda

exists. In other words, An grows exponentially. The best known lower bound for λ is 3.90. The best known upper bound, not improved since the 1970s, is λ < 4.65.

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 A_nA_m \leq A_{n+m}. Using this equation, one can show \lambda \geq (A_n)^{1/n} 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 Growth 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 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.

[edit] Free polyominoes

Approximations for the number of fixed polyominoes and free polyominoes are related in a simple way. A free polyomino with no symmetries (rotation or reflection) corresponds to 8 distinct fixed polyominoes, and for large n, most polyominoes have no symmetries. Therefore, the number of fixed polyominoes is approximately 8 times the number of free polyominoes. Moreover, this approximation is exponentially more accurate as n increases.

[edit] Special classes of polyominoes

Exact formulas are known for enumerating polyominoes of special classes, such as the class of convex polyominoes and the class of directed polyominoes.

The definition of a convex polyomino is different from the usual definition of convexity. A polyomino is said to be 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 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 polyominoes, and convex polyominoes have been effectively enumerated for all n using generating functions.

[edit] Uses of polyominoes

Polyominoes have fostered significant research in mathematics and are a fertile subject for logic puzzles and recreational mathematics, as a web search for math polyomino puzzle shows. Challenges are often posed for covering (tiling) a prescribed region with polyominoes, or folding a polyomino to create other shapes. Some variants of the Sudoku puzzle use polyomino-shaped regions on the grid.

[edit] Etymology

The word polyomino and the names of the various orders of polyomino are all back-formations from the word domino, a common game piece consisting of two squares, with the do- beginning fancifully analyzed as a version of the prefix di- meaning "two." The origin of the word domino for the game piece is not certain.

Most of the number prefixes are Greek. Polyominoes of order 9 more often take the Latin prefix nona- (nonomino) than the Greek prefix ennea- (enneomino).

[edit] See also

[edit] External links

Retrieved from "http://en.wikipedia.org../../../p/o/l/Polyomino.html"