Polyomino

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

• Free polyominoes (n=2 to 6)
• 
  One free domino
• 
  Two free trominoes
• 
  Five free tetrominoes
• 
  12 free pentominoes, colored according to their symmetry
• 
  35 free hexominoes, colored according to their symmetry

Free, one-sided, and fixed polyominoes

There are three common ways of distinguishing polyominoes for enumeration:^[6][7]

• free polyominoes are distinct when none is a rigid transformation (translation, rotation, reflection or glide reflection) of another (pieces that can be picked up and flipped over). Translating, rotating, reflecting, or glide reflecting a free polyomino does not change its shape.
• one-sided polyominoes are distinct when none is a translation or rotation of another (pieces that cannot be flipped over). Translating or rotating a one-sided polyomino does not change its shape.
• fixed polyominoes are distinct when none is a translation of another (pieces that can be neither flipped nor rotated). Translating a fixed polyomino will not change its shape.

The following table shows the numbers of polyominoes of various types with n cells.

Fixed polyominoes were enumerated in 2004 up to n = 56 by Iwan Jensen,^[8] and in 2024 up to n = 70 by Gill Barequet and Gil Ben-Shachar.^[9]

Free polyominoes were enumerated in 2007 up to n = 28 by Tomás Oliveira e Silva,^[10] in 2012 up to n = 45 by Toshihiro Shirakawa,^[11] and in 2023 up to n = 50 by John Mason.^[12]

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.

Symmetries of polyominoes

The

Polyominoes have the following possible symmetries;[13] the least number of squares needed in a polyomino with that symmetry is given in each case:

• 8 fixed polyominoes for each free polyomino:
  • no symmetry (4)
• 4 fixed polyominoes for each free polyomino:
  • mirror symmetry with respect to one of the grid line directions (4)
  • mirror symmetry with respect to a diagonal line (3)
  • 2-fold rotational symmetry: C₂ (4)
• 2 fixed polyominoes for each free polyomino:
  • symmetry with respect to both grid line directions, and hence also 2-fold rotational symmetry: D₂ (2) (also known as the Klein four-group)
  • symmetry with respect to both diagonal directions, and hence also 2-fold rotational symmetry: D₂ (7)
  • 4-fold rotational symmetry: C₄ (8)
• 1 fixed polyomino for each free polyomino:
  • all symmetry of the square: D₄ (1).

In the same way, the number of one-sided polyominoes depends on polyomino symmetry as follows:

• 2 one-sided polyominoes for each free polyomino:
  • no symmetry
  • 2-fold rotational symmetry: C₂
  • 4-fold rotational symmetry: C₄
• 1 one-sided polyomino for each free polyomino:
  • all symmetry of the square: D₄
  • mirror symmetry with respect to one of the grid line directions
  • mirror symmetry with respect to a diagonal line
  • symmetry with respect to both grid line directions, and hence also 2-fold rotational symmetry: D₂
  • symmetry with respect to both diagonal directions, and hence also 2-fold rotational symmetry: D₂.

The following table shows the numbers of polyominoes with n squares, sorted by symmetry groups.

^[14]

Algorithms for enumeration of fixed polyominoes

Inductive algorithms

Each polyomino of size n+1 can be obtained by adding a square to a polyomino of size n. This leads to algorithms for generating polyominoes inductively.

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.^[15] 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 faster^[16] to generate symmetric polyominoes separately (by a variation of this method)^[17] and so determine the number of free polyominoes by Burnside's lemma.

Transfer-matrix method

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

Both Conway's and Jensen's versions of the transfer-matrix 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 can't currently be used to count free polyominoes.

Asymptotic growth of the number of polyominoes

Fixed polyominoes

Theoretical arguments and numerical calculations support the estimate for the number of fixed polyominoes of size n

${\displaystyle A_{n}\sim {\frac {c\lambda ^{n}}{n}}}$

where λ = 4.0626 and c = 0.3169.^[20] 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

${\displaystyle \lim _{n\rightarrow \infty }(A_{n})^{\frac {1}{n}}=\lambda }$

exists. In other words, A_n grows exponentially. The best known lower bound for λ, found in 2016, is 4.00253.^[21] The best known upper bound is λ < 4.5252.^[22]

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 ≤ A_n+m. Using this equation, one can show λ ≥ (A_n)^1/n for all n. Refinements of this procedure combined with data for A_n 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 Rivest obtained an upper bound of 4.65,^[23] which was subsequently improved by Barequet and Shalah to 4.5252.^[22]

Free polyominoes

Approximations for the number of fixed polyominoes and free polyominoes are related in a simple way. A free polyomino with no

The definition of a convex polyomino is different from the usual definition of convexity, 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.^[24]

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,^[25] column (or row) convex polyominoes,^[26] and convex polyominoes^[27] have been effectively enumerated by area n, as well as by some other parameters such as perimeter, using generating functions.

A polyomino is

In recreational mathematics, challenges are often posed for tiling a prescribed region, or the entire plane, with polyominoes,^[29] and related problems are investigated in mathematics and computer science.

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.

In Jigsaw Sudokus a square grid is tiled with polynomino-shaped regions (sequence A172477 in the OEIS).

Tiling regions with copies of a single polyomino

Another class of problems asks whether copies of a given polyomino can tile a rectangle, and if so, what rectangles they can tile.^[34] These problems have been extensively studied for particular polyominoes,^[35] and tables of results for individual polyominoes are available.^[36] Klarner and Göbel showed that for any polyomino there is a finite set of prime rectangles it tiles, such that all other rectangles it tiles can be tiled by those prime rectangles.^[37][38] Kamenetsky and Cooke showed how various disjoint (called "holey") polyominoes can tile rectangles.^[39]

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

Tiling the plane with copies of a single polyomino has also been much discussed. It was noted in 1965 that all polyominoes up to hexominoes^[43] and all but four heptominoes tile the plane.^[44] It was then established by David Bird that all but 26 octominoes tile the plane.^[45] Rawsthorne found that all but 235 polyominoes of size 9 tile,^[46] and such results have been extended to higher area by Rhoads (to size 14)^[47] and others. Polyominoes tiling the plane have been classified by the symmetries of their tilings and by the number of aspects (orientations) in which the tiles appear in them.^[48][49]

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.^[50]

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 n, it is possible to combine n² 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.^[51]

Tiling a common figure with various polyominoes

The compatibility problem is to take two or more polyominoes and find a figure that can be tiled with each. Polyomino compatibility has been widely studied since the 1990s. Jorge Luis Mireles and Giovanni Resta have published websites of systematic results,^[52][53] and Livio Zucca shows results for some complicated cases like three different pentominoes.^[54] The general problem can be hard. The first compatibility figure for the L and X pentominoes was published in 2005 and had 80 tiles of each kind.^[55] Many pairs of polyominoes have been proved incompatible by systematic exhaustion. No algorithm is known for deciding whether two arbitrary polyominoes are compatible.

Polyominoes in puzzles and games

In addition to the tiling problems described above, there are recreational mathematics puzzles that require folding a polyomino to create other shapes. Gardner proposed several simple games with a set of free pentominoes and a chessboard. Some variants of the Sudoku puzzle use nonomino-shaped regions on the grid. The video game Tetris is based on the seven one-sided tetrominoes (spelled "Tetriminos" in the game), and the board game Blokus uses all of the free polyominoes up to pentominoes.

Etymology

The word polyomino and the names of the various sizes of polyomino are all back-formations from the word