Polyomino

Geometric shapes formed from squares

“Polyominoes” redirects here. For the book by Solomon Golomb, see Polyominoes: Puzzles, Patterns, Problems, and Packings .

The 18 one-sided pentominoes , including 6 mirrored pairs

A polyomino is a specific type of plane geometric figure , meticulously constructed by joining a finite collection of unit squares edge-to-edge. To qualify as a polyomino , this arrangement of squares must be connected —meaning one can traverse from any square to any other square within the figure by moving only between adjacent edges. Essentially, it stands as a polyform where each constituent cell is a perfect square . One might even conceptualize it as a finite and connected subset meticulously carved out from the infinite expanse of a regular square tiling . It’s a rather precise definition, which, frankly, is more than I can say for most things.

These humble arrangements of squares have been lurking in popular puzzles for quite some time, with their earliest recorded appearances dating back to at least 1907. The initial efforts to enumerate, or count, the distinct configurations of pentominoes —those made from five squares—are, surprisingly, attributed to antiquity. Apparently, people have been finding ways to procrastinate with geometric shapes for millennia. Many of the foundational results concerning pieces composed of one to six squares were first brought to light within the pages of Fairy Chess Review , a niche publication, between the years 1937 and 1957. Here, they were not yet known by their now-famous moniker, but rather as “dissection problems.” The term “polyomino” itself, a rather elegant and fitting name, was coined by the insightful Solomon W. Golomb in 1953. Its journey into wider public consciousness, however, was largely facilitated by the masterful popularizer of mathematics, Martin Gardner , who prominently featured them in his November 1960 “Mathematical Games ” column within the pages of Scientific American .

Beyond the realm of mere squares, the concept of polyforms extends to other fundamental geometric units. Related to polyominoes are polyiamonds , which, as the name subtly suggests, are constructed from equilateral triangles . Similarly, polyhexes are derived from regular hexagons . These all fall under the broader umbrella of various plane polyforms . Furthermore, the concept of polyominoes has been rather predictably generalized into higher dimensions . By joining cubes together in a similar edge-to-edge fashion, one forms polycubes , and extending this further, one can even conceptualize hypercubes forming polyhypercubes. Because, apparently, two dimensions just weren’t enough.

In the more serious and less playful domain of statistical physics , the rigorous study of polyominoes and their higher-dimensional counterparts—often referred to as “lattice animals” in this particular academic jargon—finds practical application in addressing complex problems within physics and chemistry. These geometric constructs have proven useful as tangible models for understanding branched polymers and for analyzing the intricate dynamics of percolation clusters. It seems even abstract shapes can find a job.

Polyominoes also make an unexpected appearance in the intricate world of commutative algebra . Within this specific mathematical context, a polyomino can be ingeniously employed to define a binomial ideal. This ideal is generated by what are known as inner 2-minors within a polynomial ring, where the variables of this ring correspond directly to the vertices of the polyomino . This application serves to generalize the more classical determinantal ideals typically associated with matrices. It’s a rather elegant way to bridge discrete geometry and abstract algebra, though I suspect few would call it “fun.”

Like a great many intriguing puzzles found within recreational mathematics , polyominoes inevitably give rise to a multitude of challenging combinatorial problems. The most fundamental, and perhaps most exasperating, of these is the task of enumerating polyominoes of a predetermined size. Despite considerable effort, no universal, closed-form formula has been discovered to date, except for very specific and constrained classes of polyominoes . While a definitive formula remains elusive, a significant body of sophisticated estimates has been developed, and various algorithms exist that are capable of calculating these numbers, albeit often with considerable computational expense.

It’s worth noting that polyominoes with internal voids, or “holes,” can be quite inconvenient for certain applications, particularly in the realm of tiling problems. Consequently, in many specialized contexts, polyominoes that feature such holes are deliberately excluded from consideration, with the focus reserved exclusively for simply connected polyominoes —those without any interior gaps. Because who needs extra complications, really?

Enumeration of polyominoes

• Free polyominoes with n = 2 to 6
• The single free domino
• The two free trominoes
• The five free tetrominoes
• The 12 free pentominoes , colored according to their symmetry
• The 35 free hexominoes , colored according to their symmetry

Free, one-sided, and fixed polyominoes

When attempting to count or classify polyominoes , mathematicians typically employ three distinct methods of differentiation, each yielding a different count based on how identical shapes are defined. It’s a bit like deciding if two identical twins are the same person or two distinct individuals, depending on how you choose to look at them.

• Free polyominoes are considered distinct only if one cannot be transformed into another through any combination of rigid transformations. This includes translation (sliding), rotation (turning), reflection (flipping over), or even a glide reflection (a reflection combined with a translation). Imagine these pieces as physical objects that can be picked up, rotated, and flipped in three-dimensional space. If, after all that manipulation, they still look different, then they are distinct free polyominoes . Therefore, simply translating, rotating, reflecting, or performing a glide reflection on a free polyomino does not alter its fundamental shape or identity in this classification.
• One-sided polyominoes are a slightly more constrained category. Here, two polyominoes are deemed distinct if one cannot be transformed into the other solely through translation or rotation . The critical distinction from free polyominoes is that these pieces are treated as if they possess an inherent “top” and “bottom” side; they cannot be flipped over. Think of them as designs painted on a sheet of paper. Translating or rotating a one-sided polyomino will not change its shape, but reflecting it would create a distinct piece if the original lacked mirror symmetry.
• Fixed polyominoes represent the most restrictive classification. Under this definition, two polyominoes are considered distinct if one cannot be transformed into the other by translation alone. This means that both flipping and rotating are disallowed; the orientation and position on a grid are paramount. A fixed polyomino maintains its identity only in its precise grid location and orientation. Consequently, merely translating a fixed polyomino will not change its shape, but any rotation or reflection would result in a new fixed polyomino , even if it corresponds to the same free polyomino . It’s the least forgiving definition, for those who appreciate strict adherence to rules.

The table below meticulously presents the counts of polyominoes for various sizes, denoted by n (the number of squares), categorized according to these three distinct types, along with further distinctions for those possessing holes versus those that are simply connected .

The enumeration of fixed polyominoes has been a persistent challenge, pushed to increasingly higher values of n. In 2004, Iwan Jensen made significant strides, successfully enumerating fixed polyominoes up to a size of n = 56. More recently, in 2024, Gill Barequet and Gil Ben-Shachar further extended this impressive computational feat, reaching an enumeration for fixed polyominoes up to n = 70.

The counting of free polyominoes has also seen considerable progress. Tomás Oliveira e Silva managed to enumerate them up to n = 28 in 2007. Toshihiro Shirakawa then pushed this boundary further, reaching n = 45 in 2012. The record was again advanced in 2023 by John Mason, who completed the enumeration up to n = 50. Shirakawa, apparently not content to rest on past laurels, is projected to have reached an enumeration up to n = 59 by 2025. It’s a race, apparently, and the finish line keeps moving.

A small but crucial detail: the OEIS sequences mentioned above—specifically A000105, A000104, A000988, and A001168—include a count of 1 for the “null-polyomino.” This rather abstract entity is defined as a polyomino formed from zero squares. A delightful philosophical quandary, isn’t it? What does nothing look like?

Symmetries of polyominoes

The dihedral group D₄ is the fundamental group of symmetries that define the structural integrity of a square. This group is composed of precisely eight distinct symmetries : four rotational transformations (0°, 90°, 180°, and 270°) and four reflective transformations (across the x-axis, y-axis, and both main diagonals). It can be conceptually generated by simply alternating reflections about the x-axis and about one of the diagonal lines.

A single free polyomino can, in theory, correspond to as many as eight distinct fixed polyominoes . These fixed counterparts are simply the images of the free polyomino under the various symmetries of the D₄ group. However, these images are not necessarily unique. The more inherent symmetry a free polyomino possesses, the fewer truly distinct fixed counterparts it will have. For instance, a highly symmetric free polyomino that remains invariant under some, or even all, of the non-trivial symmetries of D₄ might correspond to only 4, 2, or even a single fixed polyomino . From a mathematical perspective, free polyominoes are essentially equivalence classes of fixed polyominoes under the transformative actions of the D₄ group.

Polyominoes can exhibit the following possible symmetries , with the minimum number of squares required to achieve each symmetry type noted:

• 8 fixed polyominoes for each free polyomino :
  • No symmetry (4 squares): This is the most common case for larger polyominoes , where the shape has no rotational or reflective symmetries at all. It’s unique in every orientation and reflection.
• 4 fixed polyominoes for each free polyomino :
  • Mirror symmetry with respect to one of the grid line directions (4 squares): The polyomino looks the same if reflected across a horizontal or vertical axis, but not both, and lacks rotational symmetry.
  • Mirror symmetry with respect to a diagonal line (3 squares): The polyomino is symmetric only when reflected across one of the two main diagonal axes.
  • 2-fold rotational symmetry: C₂ (4 squares): The polyomino looks the same after a 180° rotation , but not 90° or 270°, and lacks mirror symmetry.
• 2 fixed polyominoes for each free polyomino :
  • Symmetry with respect to both grid line directions, and hence also 2-fold rotational symmetry: D₂ (2 squares) (also known as the Klein four-group ): This implies symmetry across both horizontal and vertical axes, automatically granting 180° rotational symmetry. A rectangle is a simple example.
  • Symmetry with respect to both diagonal directions, and hence also 2-fold rotational symmetry: D₂ (7 squares): Similar to the above, but reflections are across the diagonals, also resulting in 180° rotational symmetry.
  • 4-fold rotational symmetry: C₄ (8 squares): The polyomino looks identical after 90°, 180°, and 270° rotations. It does not necessarily have mirror symmetry.
• 1 fixed polyomino for each free polyomino :
  • All symmetry of the square: D₄ (1 square): This is the highest possible symmetry, meaning the polyomino is invariant under all 8 operations of the dihedral group D₄. Only a single square (the monomino ) achieves this. It’s perfectly balanced, which is more than I can say for most things.

Similarly, the count of one-sided polyominoes is also intricately tied to the inherent symmetries of the free polyomino from which they are derived, as follows:

• 2 one-sided polyominoes for each free polyomino : These cases arise when a free polyomino is distinct from its mirror image.
  • No symmetry
  • 2-fold rotational symmetry: C₂
  • 4-fold rotational symmetry: C₄
• 1 one-sided polyomino for each free polyomino : These are the free polyominoes that are identical to their mirror images, meaning they possess at least one line of reflectional symmetry.
  • 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 provides a detailed breakdown of the number of polyominoes with n squares, meticulously categorized according to their specific symmetry group .

Algorithms for enumeration of fixed polyominoes

The task of counting fixed polyominoes is, as you might expect, not trivial. It requires specific computational strategies, some more elegant than others.

Inductive algorithms

One of the more intuitive approaches to enumerating polyominoes relies on an inductive principle. The core idea is that any polyomino of size n + 1 can be systematically derived by simply appending a single square to an existing polyomino of size n. This fundamental insight forms the basis for a class of algorithms designed to generate polyominoes inductively.

In its most straightforward implementation, this method proceeds as follows: given a complete list of all distinct polyominoes of size n, one can iterate through each of these n-ominoes. For every n-omino, a new square is considered for addition in every vacant position adjacent to its existing squares. The resulting shape, now of size n + 1, is then added to a new list, but only if it has not already been identified as a duplicate. Naturally, refinements in the ordering of the enumeration process and clever marking of adjacent squares that would lead to redundant shapes can significantly reduce the number of duplicate checks required. This general methodology is versatile enough to be employed for the enumeration of either free or fixed polyominoes , depending on the stringency of the duplicate checking.

A more sophisticated and widely adopted method, originally detailed by Redelmeier, has proven invaluable to numerous researchers. This approach not only provides a means of counting polyominoes (without the cumbersome requirement of storing all n-ominoes to generate those of size n + 1) but also facilitates the derivation of rigorous upper bounds on their total number. The underlying principle is elegantly recursive: one begins with a single square, and from this foundational unit, additional squares are incrementally and recursively appended. Depending on the specific implementation details, this method might, by default, count each n-omino n times (once for each square chosen as the initial “root”). However, it can be cleverly arranged to ensure each unique polyomino is counted precisely once.

A common implementation involves adding squares one at a time, but with a specific numbering scheme to avoid duplicates and manage the growth. Starting with an initial square, its adjacent empty positions are numbered, typically in a clockwise fashion (e.g., 1 for the top, 2 for the right, 3 for the bottom, and 4 for the left). A number between 1 and 4 is then chosen, and a square is placed at that corresponding location. Subsequently, any newly adjacent, unnumbered empty squares are assigned numbers, starting from 5. The process continues by selecting a number larger than the previously chosen number, adding a square at that position, and then numbering any new adjacent empty squares. Once n squares have been successfully added, a distinct n-omino has been constructed.

This particular strategy inherently guarantees that each fixed polyomino is counted exactly n times—once for each possible starting square that could have initiated its construction. However, it can be further optimized to count each polyomino only once. This is achieved by imposing a spatial constraint: when starting with the initial square, it is designated as the “lower-leftmost” square of the polyomino (relative to the overall bounding box). Subsequent numbering only applies to empty squares that are not on a lower row than the current square, nor to the left of the current square on the same row. This refined version is precisely the one described by Redelmeier.

Should the objective be to enumerate free polyominoes rather than fixed ones, one would typically perform a symmetry check after each n-omino is generated to determine its equivalence class. However, a more computationally efficient approach involves generating symmetric polyominoes separately (using a variation of this inductive method) and then utilizing Burnside’s lemma to derive the total count of free polyominoes . It’s all about avoiding redundant work, a concept I can certainly appreciate.

Transfer-matrix method

Currently, the pinnacle of algorithmic efficiency for enumerating polyominoes lies within the realm of the transfer-matrix paradigm, often concisely referred to as Transfer Matrix Algorithms (TMAs). Andrew Conway pioneered the implementation of a TMA in the 1990s, a monumental effort that enabled him to calculate the first 25 terms of the fixed polyomino sequence (which can be found as A001419 in the OEIS ). Building upon Conway’s foundational work, Iwan Jensen further refined these methods. In a pair of influential papers published in the early 2000s, Jensen not only implemented a TMA but also ingeniously parallelized it for the first time, pushing the computational boundary to an impressive 56 terms. His contributions were so significant that any TMA is now sometimes respectfully referred to as Jensen’s Algorithm. More recently, in 2024, Gill Barequet and his student Gil Ben-Shachar introduced another notable improvement. They executed a TMA on a 45° rotation of the standard square grid. While this transformation represents an equivalent mathematical problem, it proved to be computationally more tractable. This innovative approach currently holds the record for polyomino -counting, having successfully determined 70 terms of the sequence.

As a general rule, TMAs offer a dramatically faster execution time compared to previous enumeration methods. However, it’s crucial to note that their runtime still scales exponentially with n, meaning they become increasingly demanding as n grows. The core efficiency of TMAs is achieved by fixing a specific width (or, in the diagonal case, a diagonal width) and then systematically counting polyominoes that fit within rectangles of that defined width. By focusing on the boundary of a polyomino rather than its entire internal structure, the algorithm can track multiple polyominoes that share common boundary configurations, thus significantly accelerating the counting process compared to generating every single polyomino individually. This process is then repeated for every possible width to ensure all polyominoes are captured.

Despite their undeniable speed, TMAs come with a significant trade-off: they demand exponential amounts of memory. For values of n exceeding 50, these algorithms can consume many gigabytes of memory, pushing the limits of available computational resources. Furthermore, they are considerably more complex to program than the simpler inductive methods and, as of now, cannot be directly used to count free polyominoes . So, yes, you get speed, but you pay for it in complexity and RAM. Choose your poison.

Asymptotic growth of the number of polyominoes

Understanding how the number of polyominoes grows as n (the number of squares) increases is a fundamental theoretical question. It’s about predicting the shape of infinity, which is always a delightful exercise in futility.

Fixed polyominoes

Both theoretical arguments and extensive numerical calculations converge on an estimated asymptotic formula for the number of fixed polyominoes of size n, denoted as A_n:

A_n ~ cλⁿ / n

Here, λ is estimated to be approximately 4.0626, and c is estimated at around 0.3169. It’s important to underscore that this result remains an unproven conjecture, and the values for λ and c are, at present, merely sophisticated estimates. It’s a good guess, but a guess nonetheless.

The rigorously proven theoretical results, unfortunately, are far less specific than this tantalizing estimate. What has been definitively established is that the following limit exists:

lim_n→∞ (A_n)^1/n = λ

This mathematical statement confirms that A_n indeed grows exponentially as n tends towards infinity. The precise value of λ, however, remains elusive. The current best known lower bound for λ, established in 2016, is 4.00253. Conversely, the best known upper bound for λ is slightly less encouraging, sitting at λ < 4.5252.

To establish a lower bound for λ, a surprisingly simple yet remarkably effective method involves the concatenation of polyominoes . One defines the “upper-right square” of a polyomino as the rightmost square in its uppermost row, and similarly, the “bottom-left square.” With these definitions, it becomes possible to attach the upper-right square of any polyomino of size n to the bottom-left square of any polyomino of size m, thereby producing a unique larger (n + m)-omino. This elegant procedure proves the inequality A_n · A_m ≤ A_n+m. By leveraging this inequality, one can rigorously demonstrate that λ ≥ (A_n)^1/n for all values of n. Further refinements of this concatenation technique, combined with extensive computational data for A_n, are what have yielded the improved lower bound cited above.

The upper bound, on the other hand, is derived by generalizing the inductive method used for enumerating polyominoes . Instead of adding just one square at a time, this more advanced approach involves adding a cluster of squares simultaneously, often metaphorically described as adding “twigs.” By rigorously demonstrating that every n-omino can be constructed as a sequence of these “twigs,” and by establishing limits on the combinations of possible twigs, one can arrive at an upper bound for the number of n-ominoes. For instance, in the inductive algorithm previously outlined, at each step, one must select a larger number, and at most three new numbers are introduced (since a square can have at most three unnumbered adjacent squares). This simple observation alone can be used to derive an initial upper bound of 6.75 for λ. Through more complex analysis involving 2.8 million distinct “twigs,” Klarner and Rivest managed to significantly improve this to an upper bound of 4.65. This was subsequently further refined by Barequet and Shalah, who achieved the current best known upper bound of 4.5252. The pursuit of these values is rather relentless, isn’t it?

Free polyominoes

The approximations for the number of fixed polyominoes and free polyominoes are interconnected in a remarkably straightforward manner. A free polyomino that possesses absolutely no symmetries —neither rotational nor reflectional—corresponds to exactly eight distinct fixed polyominoes . For sufficiently large values of n, the vast majority of n-ominoes exhibit no inherent symmetries . Consequently, the number of fixed n-ominoes is approximately eight times the number of free n-ominoes. Furthermore, this approximation becomes exponentially more accurate as n increases, which is a rather convenient mathematical property.

Special classes of polyominoes

While enumerating all polyominoes remains a combinatorial nightmare, exact formulas do exist for specific, well-behaved classes. It’s always easier when things conform to expectations.

The definition of a “convex polyomino ” diverges somewhat from the standard geometric definition of convexity , instead bearing a closer resemblance to the concept used for the orthogonal convex hull . A polyomino is designated as “vertically convex” or “column convex” if its intersection with any vertical line forms a single, unbroken segment (in simpler terms, each column of squares within the polyomino contains no internal holes or gaps). Analogously, a polyomino is termed “horizontally convex” or “row convex” if its intersection with any horizontal line also forms a continuous segment. A polyomino is then simply considered “convex” if it satisfies both the row and column convexity criteria. It’s a very specific kind of convexity, tailored for the grid.

A polyomino is classified as “directed” if it contains at least one designated square, referred to as the “root,” from which every other square within the polyomino can be reached exclusively through movements of one square “up” or one square “right,” without ever straying outside the boundaries of the polyomino itself. This imposes a strict directional growth constraint.

These specialized categories—namely, directed polyominoes , column (or row) convex polyominoes , and fully convex polyominoes —have been successfully and precisely enumerated not only by their area n but also by other relevant parameters, such as their perimeter. This enumeration is typically achieved through the powerful mathematical tool of generating functions .

Another interesting class is the “equable polyomino .” A polyomino is defined as equable if its numerical area is exactly equal to its numerical perimeter. Intriguingly, an equable polyomino must always be composed of an even number of squares. Furthermore, it has been discovered that any even number of squares greater than 15 can form an equable polyomino . For example, a 16-omino shaped as a 4×4 square has an area of 16 and a perimeter of 16, making it equable. Similarly, an 18-omino configured as a 3×6 rectangle also has an area of 18 and a perimeter of 18. However, for polyominoes with 15 squares or fewer, the perimeter invariably exceeds the area. So, if you’re looking for balance, you need to grow a bit.

Tiling with polyominoes

In the realm of recreational mathematics , challenges involving the precise tiling of a predefined region, or even the entire infinite plane, using polyominoes are frequently posed. These puzzles, seemingly simple, lead to complex problems that are deeply investigated within mathematics and computer science .

Tiling regions with sets of polyominoes

A common type of puzzle involves the task of tiling a specific geometric region with a given, finite set of polyominoes . The classic example, often cited in Golomb’s and Gardner’s seminal works, is the challenge of arranging the twelve pentominoes to perfectly tile a 6×10 rectangle. This particular problem, initially explored in 1960, was found to have precisely 2339 distinct solutions. It’s a testament to the combinatorial explosion that even a seemingly small set of pieces can generate.

When the rules permit the use of multiple copies of the polyominoes within a given set, Golomb introduced a hierarchical classification for the types of regions that a set might be capable of tiling. This hierarchy includes fundamental shapes such as rectangles, infinite strips, and the ultimate challenge: the entire plane. Golomb’s profound work demonstrated that the question of whether an arbitrary set of polyominoes can tile the plane is, surprisingly, undecidable . He achieved this by ingeniously mapping sets of Wang tiles —which are known to exhibit undecidability in tiling problems—to corresponding sets of polyominoes .

Given that the general problem of tiling arbitrary regions of the plane with arbitrary sets of polyominoes is classified as NP-complete , finding solutions for configurations involving more than just a handful of pieces rapidly becomes computationally intractable for humans. Consequently, the assistance of computers becomes not merely beneficial but absolutely essential. The traditional computational approach to solving these finite region tiling problems leverages a well-established technique in computer science known as backtracking . This method systematically explores all possible placements, retracting choices that lead to dead ends until a solution is found or all possibilities are exhausted.

In a more modern context, Jigsaw Sudokus offer a popular variant of the classic number puzzle, where the traditional 3x3 square blocks are replaced by polyomino -shaped regions that tile the main square grid. These regions often correspond to specific sequences (e.g., A172477 in the OEIS ), adding a geometric twist to the logical challenge.

Tiling regions with copies of a single polyomino

Another compelling class of tiling problems investigates whether identical copies of a single given polyomino can perfectly tile a rectangle . If such tiling is possible, the inquiry then extends to determining precisely which dimensions of rectangles can be tiled by that specific polyomino . These problems have been subjected to extensive scrutiny for individual polyominoes , resulting in comprehensive tables of known outcomes for specific shapes.

Klarner and Göbel made a significant theoretical contribution by demonstrating that for any given polyomino , there exists a finite, irreducible set of “prime rectangles” that it can tile. Crucially, all other rectangles that the polyomino can tile can be formed by combining these fundamental prime rectangles. This provides a structural understanding of a polyomino ’s tiling capabilities. More recently, Kamenetsky and Cooke have explored how various disjoint (or “holey”) polyominoes can also be used to tile rectangles, adding another layer of complexity to the problem.

Beyond the specific case of rectangles, Golomb established a broader hierarchy for the tiling abilities of single polyominoes . A polyomino might be capable of tiling a rectangle, a half-strip, a bent strip, an enlarged copy of itself (a characteristic of rep-tiles ), a quadrant, an infinite strip, a half plane , or the entire infinite plane. Alternatively, it might be incapable of tiling any of these. This hierarchy also defines a set of logical implications; for instance, if a polyomino can tile the half plane, it logically follows that it can tile the entire plane. Less obvious implications also exist, such as the finding that if a polyomino can tile an enlarged copy of itself, it can also tile the quadrant. Polyominoes up to size 6 have been thoroughly characterized within this hierarchy, though the tiling status of one particular hexomino remained unresolved for a time, later being confirmed to tile a rectangle.

In 2001, Cristopher Moore and John Michael Robson delivered a rather definitive blow to the hopes of easy solutions by demonstrating that the problem of tiling one polyomino with copies of another is, in fact, NP-complete . So, if you were hoping for a simple general algorithm, you’re out of luck.

Tiling the plane with copies of a single polyomino

The two tiling nonominoes not satisfying the Conway criterion.

The question of which individual polyominoes can tile the entire infinite plane has also been a subject of extensive mathematical discourse and investigation. It was observed as early as 1965 that all polyominoes up to the size of hexominoes, and all but four of the heptominoes, possessed this remarkable property. Further research by David Bird established that all but 26 of the octominoes could tile the plane. Daniel A. Rawsthorne continued this line of inquiry, discovering that all but 235 of the nonominoes (size 9) were capable of tiling the plane. Such results have been systematically extended to polyominoes of higher areas by researchers like Rhoads (up to size 14) and others. Polyominoes that tile the plane have been further classified not only by their inherent symmetries but also by the number of distinct “aspects” or orientations in which the individual tiles appear within the larger tiling pattern.

The study of which polyominoes are capable of tiling the plane has been significantly aided by the application of the Conway criterion . This criterion provides a sufficient, though not necessary, condition for a shape to tile the plane. It has been noted that, with the exception of two specific nonominoes, all tiling polyominoes up to size 9 form a patch of at least one tile that satisfies the Conway criterion. However, as the size of the polyomino increases, the frequency of exceptions to this criterion also tends to rise.

Several polyominoes possess the intriguing ability to tile larger, geometrically similar copies of themselves. When this process is recursively repeated, it generates a rep-tile tiling of the entire plane. For instance, it is known that for any positive integer n, one can combine n² copies of the L-tromino, the L-tetromino, or the P-pentomino to construct a single, larger shape that is geometrically similar to the smaller polyomino from which it was formed. It’s a rather elegant demonstration of self-replication in geometry.

Tiling a common figure with various polyominoes

A minimal compatibility figure for the T and W pentominoes .

The “compatibility problem” introduces another layer of complexity: given two or more distinct polyominoes , the challenge is to discover a common geometric figure that can be perfectly tiled by each of them individually. The study of polyomino compatibility has seen considerable attention since the 1990s. Researchers like Jorge Luis Mireles and Giovanni Resta have meticulously published systematic results on various compatibility pairs on their respective websites. Livio Zucca has even ventured into more intricate scenarios, presenting solutions for challenging cases involving three different pentominoes .

This general problem can be remarkably difficult. For instance, the very first compatibility figure discovered for the L and X pentominoes was not published until 2005, and it required a substantial 80 tiles of each type to form the common shape. Many pairs of polyominoes have been definitively proven to be incompatible through exhaustive computational searches, demonstrating that not all shapes are destined to share a common tiling destiny. Regrettably, no general algorithm is currently known that can determine with certainty whether any two arbitrary polyominoes are compatible. Some things, it seems, just aren’t meant to be.

Polyominoes in puzzles and games

Beyond the purely mathematical and abstract tiling problems, polyominoes have found a vibrant existence in the more accessible realm of recreational mathematics and popular games. Challenges are often devised that require not just tiling, but also folding a polyomino to create other specific three-dimensional shapes.

Martin Gardner , ever the innovator, proposed several engaging and relatively simple games that could be played using a standard set of free pentominoes and a conventional chessboard . These games often involved covering specific areas or strategic placements. In the world of digital entertainment, the wildly popular video game Tetris is fundamentally built upon the concept of polyominoes , specifically utilizing the seven unique one-sided tetrominoes (which the game famously spells as “Tetriminos”). Similarly, the acclaimed board game Blokus strategically employs all of the free polyominoes up to pentominoes as its core game pieces, challenging players to strategically place them on a grid. Even certain variants of the beloved Sudoku puzzle integrate nonomino -shaped regions into their grid layouts, adding a geometric twist to the numerical logic.

Etymology

The term “polyomino ,” along with the specific names for polyominoes of various sizes (such as monomino , tromino , tetromino , etc.), are all clever linguistic constructions known as “back-formations.” These words were derived backwards from the more familiar term “domino ,” which itself refers to a common game piece composed of precisely two squares.

The origin of the word “domino” for the game piece is generally believed to stem from the spotted masquerade garment, also called a “domino,” worn during carnivals and similar events. This garment’s name, in turn, is thought to be derived from the Latin word “dominus,” meaning “master” or “lord.” Despite this rather sophisticated etymological lineage, when constructing the names for polyominoes , the initial letter ’d-’ of “domino” was playfully and fancifully reinterpreted as a variant of the Greek prefix “di-,” which quite literally means “two.” This reinterpretation then allowed for the systematic substitution of other numerical prefixes (like “mono-” for one, “tri-” for three, “tetra-” for four, “penta-” for five, and so on) to denote the number of squares forming the polyomino . It’s a rather charming example of linguistic play, creating a logical system where none originally existed.

See also

• Percolation theory , the rigorous mathematical study of random subsets within integer grids. The finite, connected components that emerge from these subsets often manifest as polyominoes .
• Young diagram , a specific type of polyomino that holds significant importance in number theory for graphically representing integer partitions and in group theory, as well as its applications in mathematical physics, for describing representations of the symmetric group.
• Blokus , a popular abstract strategy board game that centrally features polyominoes as its primary game pieces.
• Squaregraph , a particular kind of undirected graph that includes, as a special case, the graphs formed by the vertices and edges of polyominoes .
• Polycube , the three-dimensional analogue of a polyomino , formed by joining unit cubes face-to-face.