Polyomino
[1] 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,[2] and it was popularized by Martin Gardner in a November 1960 "Mathematical Games" column in Scientific American.
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.
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 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 may check for symmetries after creating each n-omino.
Andrew Conway[18] first implemented a TMA in the 90s, and calculated 25 terms of the fixed polyomino sequence (A001419 in the OEIS).
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.
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.
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.
Theoretical arguments and numerical calculations support the estimate for the number of fixed polyominoes of size n where λ = 4.0626 and c = 0.3169.
[24] To establish a lower bound, a simple but highly effective method is concatenation of polyominoes.
Using this equation, one can show λ ≥ (An)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 inductive method of enumerating polyominoes.
Using 2.8 million twigs, Klarner and Rivest obtained an upper bound of 4.65,[25] which was subsequently improved by Barequet and Shalah to 4.5252.
Puzzles commonly ask for tiling a given region with a given set of polyominoes, such as the 12 pentominoes.
A typical puzzle is to tile a 6×10 rectangle with the twelve pentominoes; the 2339 solutions to this were found in 1960.
The traditional approach to tiling finite regions of the plane uses a technique in computer science called backtracking.
[35] In Jigsaw Sudokus a square grid is tiled with polyomino-shaped regions (sequence A172477 in the OEIS).
[39][40] Kamenetsky and Cooke showed how various disjoint (called "holey") polyominoes can tile rectangles.
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).
[42] In 2001 Cristopher Moore and John Michael Robson showed that the problem of tiling one polyomino with copies of another is NP-complete.
For instance, for every positive integer n, it is possible to combine n2 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.
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.
