Polyomino

A polyomino is a plane geometric figure, connected, formed by joining a finite number of unit squares edge-to-edge. It is a polyform whose cells are squares. It may be regarded as a finite and connected 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. Many results with the pieces made 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 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 is applied to problems in physics and chemistry. Polyominoes have been used as models of branched polymers and of percolation clusters.
Polyominoes also appear in commutative algebra. In this context, a polyomino can be used to define a binomial ideal generated by inner 2-minors in a polynomial ring whose variables correspond to the vertices of the polyomino, generalizing classical determinantal ideals of matrices.
Like many puzzles in recreational mathematics, polyominoes raise many combinatorial problems. The most basic one 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.

Enumeration of polyominoes

Free, one-sided, and fixed polyominoes

There are three common ways of distinguishing polyominoes for enumeration:

free polyominoes are distinct when none is a rigid transformation of another. 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. Translating or rotating a one-sided polyomino does not change its shape.
fixed polyominoes are distinct when none is a translation of another. 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, and in 2024 up to n = 70 by Gill Barequet and Gil Ben-Shachar.
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, in 2023 up to n = 50 by John Mason, and in 2025 up to n = 59 by Toshihiro Shirakawa.
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 dihedral group D₄ is the group of symmetries 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 images under the symmetries of D₄. However, those images are not necessarily distinct: the more symmetry a free polyomino has, the fewer distinct fixed counterparts it has. Therefore, a free polyomino that is invariant under some or all non-trivial symmetries of D₄ may correspond to only 4, 2 or 1 fixed polyominoes. Mathematically, free polyominoes are equivalence classes of fixed polyominoes under the group D₄.
Polyominoes have the following possible symmetries; 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 fixed polyominoes for each free polyomino:
*mirror symmetry with respect to one of the grid line directions
*mirror symmetry with respect to a diagonal line
*2-fold rotational symmetry: C₂
2 fixed polyominoes for each free polyomino:
*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₂
*4-fold rotational symmetry: C₄
1 fixed polyomino for each free polyomino:
*all symmetry of the square: D₄.

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.

n	none	mirror 90°	mirror 45°	C₂	D₂ 90°	D₂ 45°	C₄	D₄
1	0	0	0	0	0	0	0	1
2	0	0	0	0	1	0	0	0
3	0	0	1	0	1	0	0	0
4	1	1	0	1	1	0	0	1
5	5	2	2	1	1	0	0	1
6	20	6	2	5	2	0	0	0
7	84	9	7	4	3	1	0	0
8	316	23	5	18	4	1	1	1
9	1,196	38	26	19	4	0	0	2
10	4,461	90	22	73	8	1	0	0
11	16,750	147	91	73	10	2	0	0
12	62,878	341	79	278	15	3	3	3
OEIS sequence

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. 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, 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 to generate symmetric polyominoes separately and so determine the number of free polyominoes by Burnside's lemma.

Transfer-matrix method

Currently, the most effective algorithms belong to the transfer-matrix paradigm. They may be called transfer matrix algorithms for short. Andrew Conway first implemented a TMA in the 90s, and calculated 25 terms of the fixed polyomino sequence. Iwan Jensen refined Conway's methods and implemented a TMA in parallel for the first time in a pair of papers in the early 2000s. He calculated 56 terms. Because of this work, any TMA is sometimes also called Jensen's Algorithm. In 2024, Gill Barequet and his student Gil Ben-Shachar made another improvement by running a TMA on 45° rotation of the square grid, which is an equivalent problem but computationally easier. This approach holds the polyomino-counting record, with 70 terms.
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, 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, is much harder to program than the other methods, and cannot currently be used to count free polyominoes.