A polyomino is a
plane geometric figure formed by joining one or more equal
square
In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90-degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length adj ...
s edge to edge. It is a
polyform
In recreational mathematics, a polyform is a plane (mathematics), plane figure or solid compound constructed by joining together identical basic polygons. The basic polygon is often (but not necessarily) a convex polygon, convex plane-filling pol ...
whose cells are squares. It may be regarded as a finite
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
of the regular
square tiling
In geometry, the square tiling, square tessellation or square grid is a regular tiling of the Euclidean plane. It has Schläfli symbol of meaning it has 4 squares around every vertex.
Conway called it a quadrille.
The internal angle of the s ...
.
Polyominoes have been used in popular
puzzle
A puzzle is a game, Problem solving, problem, or toy that tests a person's ingenuity or knowledge. In a puzzle, the solver is expected to put pieces together (Disentanglement puzzle, or take them apart) in a logical way, in order to arrive at th ...
s since at least 1907, and the enumeration of
pentomino
Derived from the Greek word for ' 5', and "domino", a pentomino (or 5-omino) is a polyomino of order 5, that is, a polygon in the plane made of 5 equal-sized squares connected edge-to-edge. When rotations and reflections are not considered to ...
es is dated to antiquity. Many results with the pieces of 1 to 6 squares were first published in ''
Fairy Chess Review
''Fairy Chess Review'' () was a magazine that was devoted principally to fairy chess problems, but also included extensive original results on related questions in mathematical recreations, such as knight's tours and polyominoes (under the title o ...
'' between the years 1937 to 1957, under the name of "
dissection
Dissection (from Latin ' "to cut to pieces"; also called anatomization) is the dismembering of the body of a deceased animal or plant to study its anatomical structure. Autopsy is used in pathology and forensic medicine to determine the cause o ...
problems." The name ''polyomino'' was invented by
Solomon W. Golomb in 1953, and it was popularized by
Martin Gardner
Martin Gardner (October 21, 1914May 22, 2010) was an American popular mathematics and popular science writer with interests also encompassing scientific skepticism, micromagic, philosophy, religion, and literatureespecially the writings of Lewis ...
in a November 1960 "
Mathematical Games
A mathematical game is a game whose rules, strategies, and outcomes are defined by clear mathematical parameters. Often, such games have simple rules and match procedures, such as Tic-tac-toe and Dots and Boxes. Generally, mathematical games ne ...
" column in ''
Scientific American
''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many famous scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it. In print since 1845, it i ...
''.
Related to polyominoes are
polyiamond
A polyiamond (also polyamond or simply iamond, or sometimes triangular polyomino) is a polyform whose base form is an equilateral triangle. The word ''polyiamond'' is a back-formation from ''diamond'', because this word is often used to describe ...
s, formed from
equilateral triangle
In geometry, an equilateral triangle is a triangle in which all three sides have the same length. In the familiar Euclidean geometry, an equilateral triangle is also equiangular; that is, all three internal angles are also congruent to each othe ...
s;
polyhexes, formed from regular
hexagon
In geometry, a hexagon (from Ancient Greek, Greek , , meaning "six", and , , meaning "corner, angle") is a six-sided polygon. The total of the internal angles of any simple polygon, simple (non-self-intersecting) hexagon is 720°.
Regular hexa ...
s; and other plane
polyform
In recreational mathematics, a polyform is a plane (mathematics), plane figure or solid compound constructed by joining together identical basic polygons. The basic polygon is often (but not necessarily) a convex polygon, convex plane-filling pol ...
s. Polyominoes have been generalized to higher
dimension
In physics and mathematics, the dimension of a Space (mathematics), mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any Point (geometry), point within it. Thus, a Line (geometry), lin ...
s by joining
cubes
In geometry, a cube is a three-dimensional space, three-dimensional solid object bounded by six square (geometry), square faces, Facet (geometry), facets or sides, with three meeting at each vertex (geometry), vertex. Viewed from a corner it i ...
to form
polycube
upAll 8 one-sided tetracubes – if chirality is ignored, the bottom 2 in grey are considered the same, giving 7 free tetracubes in total
A puzzle involving arranging nine L tricubes into a 3×3 cube
A polycube is a solid figure formed by j ...
s, or
hypercube
In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, ...
s to form polyhypercubes.
In
statistical physics
Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the Mathematics, mathematical tools for dealing with large populations ...
, the study of polyominoes and their higher-dimensional analogs (which are often referred to as lattice animals in this literature) is applied to problems in physics and chemistry. Polyominoes have been used as models of
branched polymers and of
percolation
Percolation (from Latin ''percolare'', "to filter" or "trickle through"), in physics, chemistry and materials science, refers to the movement and filtering of fluids through porous materials.
It is described by Darcy's law.
Broader applicatio ...
clusters.
Like many puzzles in recreational mathematics, polyominoes raise many
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many app ...
problems. The most basic 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
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s 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
In topology, a topological space is called simply connected (or 1-connected, or 1-simply connected) if it is path-connected and every path between two points can be continuously transformed (intuitively for embedded spaces, staying within the spac ...
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 (
translation
Translation is the communication of the Meaning (linguistic), meaning of a #Source and target languages, source-language text by means of an Dynamic and formal equivalence, equivalent #Source and target languages, target-language text. The ...
,
rotation
Rotation, or spin, is the circular movement of an object around a '' central axis''. A two-dimensional rotating object has only one possible central axis and can rotate in either a clockwise or counterclockwise direction. A three-dimensional ...
,
reflection Reflection or reflexion may refer to:
Science and technology
* Reflection (physics), a common wave phenomenon
** Specular reflection, reflection from a smooth surface
*** Mirror image, a reflection in a mirror or in water
** Signal reflection, in ...
or
glide reflection
In 2-dimensional geometry, a glide reflection (or transflection) is a symmetry operation that consists of a reflection over a line and then translation along that line, combined into a single operation. The intermediate step between 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.
, Iwan Jensen has enumerated the fixed polyominoes up to ''n'' = 56 – approximately 6.915.
Free polyominoes were enumerated in 2007 up to ''n'' = 28 by Tomás Oliveira e Silva, and in 2012 up to ''n'' = 45 by Toshihiro Shirakawa.
Symmetries of polyominoes
The
dihedral group
In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ge ...
''D''
4 is the
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
of
symmetries
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
(
symmetry group
In group theory, the symmetry group of a geometric object is the group of all transformations under which the object is invariant, endowed with the group operation of composition. Such a transformation is an invertible mapping of the ambient ...
) 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''
4. 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''
4 may correspond to only 4, 2 or 1 fixed polyominoes. Mathematically, free polyominoes are
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
es of fixed polyominoes under the group ''D''
4.
Polyominoes have the following possible symmetries;
[Redelmeier, section 3] 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''
2 (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 (2) (also known as the
Klein four-group
In mathematics, the Klein four-group is a Group (mathematics), group with four elements, in which each element is Involution (mathematics), self-inverse (composing it with itself produces the identity)
and in which composing any two of the three ...
)
**symmetry with respect to both diagonal directions, and hence also 2-fold rotational symmetry: ''D''
2 (7)
**4-fold rotational symmetry: ''C''
4 (8)
*1 fixed polyomino for each free polyomino:
**all symmetry of the square: ''D''
4 (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''
2
**4-fold rotational symmetry: ''C''
4
*1 one-sided polyomino for each free polyomino:
**all symmetry of the square: ''D''
4
**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''
2
**symmetry with respect to both diagonal directions, and hence also 2-fold rotational symmetry: ''D''
2.
The following table shows the numbers of polyominoes with ''n'' squares, sorted by symmetry groups.
Algorithms for enumeration of fixed polyominoes
Inductive algorithms
Each polyomino of order ''n''+1 can be obtained by adding a square to a polyomino of order ''n''. This leads to algorithms for generating polyominoes inductively.
Most simply, given a list of polyominoes of order ''n'', squares may be added next to each polyomino in each possible position, and the resulting polyomino of order ''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 (without requiring that all polyominoes of order ''n'' be stored in order to enumerate those of order ''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 to generate symmetric polyominoes separately (by a variation of this method) and so determine the number of free polyominoes by
Burnside's lemma
Burnside's lemma, sometimes also called Burnside's counting theorem, the Cauchy–Frobenius lemma, the orbit-counting theorem, or the Lemma that is not Burnside's, is a result in group theory that is often useful in taking account of symmetry when ...
.
Transfer-matrix 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 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 function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
s, 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
gigabyte
The gigabyte () is a multiple of the unit byte for digital information. The prefix ''giga'' means 109 in the International System of Units (SI). Therefore, one gigabyte is one billion bytes. The unit symbol for the gigabyte is GB.
This defini ...
s 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
:
where ''λ'' = 4.0626 and ''c'' = 0.3169. 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
:
exists. In other words, ''A
n''
grows exponentially
Exponential growth is a process that increases quantity over time. It occurs when the instantaneous rate of change (that is, the derivative) of a quantity with respect to time is proportional to the quantity itself. Described as a function, a q ...
. The best known lower bound for ''λ'', found in 2016, is 4.00253. The best known upper bound, not improved since the 1970s, is .
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 . Using this equation, one can show 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, which was subsequently improved by Barequet and Shalah to 4.5252.
Free polyominoes
Approximations for the number of fixed polyominoes and free polyominoes are related in a simple way. A free polyomino with no
symmetries
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
(rotation or reflection) corresponds to 8 distinct fixed polyominoes, and for large ''n'', most ''n''-ominoes have no symmetries. Therefore, the number of fixed ''n''-ominoes is approximately 8 times the number of free ''n''-ominoes. Moreover, this approximation is exponentially more accurate as ''n'' increases.
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
Convex or convexity may refer to:
Science and technology
* Convex lens, in optics
Mathematics
* Convex set, containing the whole line segment that joins points
** Convex polygon, a polygon which encloses a convex set of points
** Convex polytope ...
, but is similar to the definition used for the
orthogonal convex hull
In geometry, a set is defined to be orthogonally convex if, for every line that is parallel to one of standard basis vectors, the intersection of with is empty, a point, or a single segment. The term "orthogonal" refers to corresponding C ...
. 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.
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, column (or row) convex polyominoes, and convex polyominoes have been effectively enumerated by area ''n'', as well as by some other parameters such as perimeter, using
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
s.
A polyomino is
equable if its area equals its perimeter. An equable polyomino must be made from an
even number
In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is a multiple of two, and odd if it is not.. For example, −4, 0, 82 are even because
\begin
-2 \cdot 2 &= -4 \\
0 \cdot 2 &= 0 \\
41 ...
of squares; every even number greater than 15 is possible. For instance, the 16-omino in the form of a 4 × 4 square and the 18-omino in the form of a 3 × 6 rectangle are both equable. For polyominoes with fewer than 15 squares, the perimeter always exceeds the area.
Tiling with polyominoes
In
recreational mathematics
Recreational mathematics is mathematics carried out for recreation (entertainment) rather than as a strictly research and application-based professional activity or as a part of a student's formal education. Although it is not necessarily limited ...
, challenges are often posed for
tiling
Tiling may refer to:
*The physical act of laying tiles
*Tessellations
Computing
*The compiler optimization of loop tiling
*Tiled rendering, the process of subdividing an image by regular grid
*Tiling window manager
People
*Heinrich Sylvester The ...
a prescribed region, or the entire plane, with polyominoes, and related problems are investigated in
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
.
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. Where multiple copies of the polyominoes in the set are allowed, Golomb defines a hierarchy of different regions that a set may be able to tile, such as rectangles, strips, and the whole plane, and shows that whether polyominoes from a given set can tile the plane is
undecidable, by mapping sets of
Wang tile
Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems. They are modelled visually by square tiles with a color on each side. A set of such tiles is selected, an ...
s to sets of polyominoes.
Because the general problem of tiling regions of the plane with sets of polyominoes is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
, tiling with more than a few pieces rapidly becomes intractable and so the aid of a computer is required. The traditional approach to tiling finite regions of the plane uses a technique in computer science called
backtracking
Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...
.
In
Jigsaw Sudokus a square grid is tiled with polynomino-shaped regions .
Tiling regions with copies of a single polyomino
Another class of problems asks whether copies of a given polyomino can tile a
rectangle
In Euclidean plane geometry, a rectangle is a quadrilateral with four right angles. It can also be defined as: an equiangular quadrilateral, since equiangular means that all of its angles are equal (360°/4 = 90°); or a parallelogram containi ...
, and if so, what rectangles they can tile. These problems have been extensively studied for particular polyominoes, and tables of results for individual polyominoes are available.
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. Kamenetsky and Cooke showed how various disjoint (called "holey") polyominoes can tile rectangles.
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
half plane
In geometry, a half-space is either of the two parts into which a plane divides the three-dimensional Euclidean space.
If the space is two-dimensional, then a half-space is called a half-plane (open or closed). A half-space in a one-dimensional ...
, the whole plane, certain combinations, or none of these. There are certain implications among these, both obvious (for example, if a polyomino tiles the half plane then it tiles the whole plane) and less so (for example, if a polyomino tiles an enlarged copy of itself, then it tiles the quadrant). Polyominoes of orders up to 6 are characterized in this hierarchy (with the status of one hexomino, later found to tile a rectangle, unresolved at that time).
In 2001
Cristopher Moore
Cristopher David Moore, known as Cris Moore, (born March 12, 1968 in New Brunswick, New Jersey)[Curriculum vitae](_blank) and John Michael Robson showed that the problem of tiling one polyomino with copies of another is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
.
Tiling the plane with copies of a single polyomino
![Conway criterion false negative nonominoes](https://upload.wikimedia.org/wikipedia/commons/1/17/Conway_criterion_false_negative_nonominoes.svg)
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 and all but four heptominoes tile the plane. It was then established by David Bird that all but 26 octominoes tile the plane. Rawsthorne found that all but 235 polyominoes of order 9 tile, and such results have been extended to higher orders by Rhoads (to order 14) 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.
The study of which polyominoes can tile the plane has been facilitated using the
Conway criterion
In the mathematical theory of tessellations, the Conway criterion, named for the English mathematician John Horton Conway, is a sufficient rule for when a prototile will tile the plane. It consists of the following requirements:Will It Tile? Try ...
: except for two nonominoes, all tiling polyominoes up to order 9 form a patch of at least one tile satisfying it, with higher-order exceptions more frequent.
Several polyominoes can tile larger copies of themselves, and repeating this process recursively gives a
rep-tile
In the geometry of tessellations, a rep-tile or reptile is a shape that can be dissected into smaller copies of the same shape. The term was coined as a pun on animal reptiles by recreational mathematician Solomon W. Golomb and popularized by ...
tiling of the plane. For instance, for every positive integer , it is possible to combine 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.
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, and Livio Zucca shows results for some complicated cases like three different pentominoes. 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. 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
Sudoku (; ja, 数独, sūdoku, digit-single; originally called Number Place) is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row ...
puzzle use nonomino-shaped regions on the grid. The video game ''
Tetris
''Tetris'' (russian: link=no, Тетрис) is a puzzle video game created by Soviet software engineer Alexey Pajitnov in 1984. It has been published by several companies for multiple platforms, most prominently during a dispute over the approp ...
'' is based on the seven one-sided tetrominoes (spelled "Tetriminos" in the game), and the board game ''
Blokus
Blokus ( ) is an abstract strategy board game for two to four players, where players try to score points by occupying most of the board with pieces of their colour. The board is a square regular grid and the pieces are polyominoes. It was designe ...
'' uses all of the free polyominoes up to pentominoes.
Etymology
The word ''polyomino'' and the names of the various orders of polyomino are all back-formations from the word ''
domino
Dominoes is a family of tile-based games played with gaming pieces, commonly known as dominoes. Each domino is a rectangular tile, usually with a line dividing its face into two square ''ends''. Each end is marked with a number of spots (also ca ...
'', a common game piece consisting of two squares, with the first letter ''d-'' fancifully interpreted as a version of the prefix ''di-'' meaning "two." The name ''domino'' for the game piece is believed to come from the spotted masquerade garment ''domino'', from Latin ''dominus''.
Oxford English Dictionary
The ''Oxford English Dictionary'' (''OED'') is the first and foundational historical dictionary of the English language, published by Oxford University Press (OUP). It traces the historical development of the English language, providing a com ...
, 2nd edition, entry ''domino''
Most of the
numerical prefix
Numeral or number prefixes are prefixes derived from Numeral (linguistics), numerals or occasionally other numbers. In English and many other languages, they are used to coin numerous series of words. For example:
* unicycle, bicycle, tricycle (1 ...
es are Greek. Polyominoes of order 9 and 11 more often take the Latin prefixes ''nona-'' (nonomino) and ''undeca-'' (undecomino) than the Greek prefixes ''ennea-'' (enneomino) and ''hendeca-'' (hendecomino).
See also
*
Percolation theory
In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected ...
, the mathematical study of random subsets of integer grids. The finite connected components of these subsets form polyominoes.
*
Young diagram In mathematics, a Young tableau (; plural: tableaux) is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups and ...
, a special kind of polyomino used in number theory to describe integer partitions and in group theory and applications in mathematical physics to describe representations of the symmetric group.
*
Blokus
Blokus ( ) is an abstract strategy board game for two to four players, where players try to score points by occupying most of the board with pieces of their colour. The board is a square regular grid and the pieces are polyominoes. It was designe ...
, a board game using polyominoes.
*
Squaregraph
In graph theory, a branch of mathematics, a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with three or fewer neighbors is incident to an unbound ...
, a kind of undirected graph including as a special case the graphs of vertices and edges of polyominoes.
Notes
External links
Online polyomino solvers
An open source java based polyomino solverAn interactive polyomino-tiling application
Publications
Karl Dahlke's polyomino finite-rectangle tilings*
ttp://www.statslab.cam.ac.uk/~grg/books/hammfest/19-sgw.ps A paper describing modern estimates (PS)*
MathPages – Notes on enumeration of polyominoes with various symmetries*
Tetrads' by Karl Scherer,
Wolfram Demonstrations Project
The Wolfram Demonstrations Project is an organized, open-source collection of small (or medium-size) interactive programs called Demonstrations, which are meant to visually and interactively represent ideas from a range of fields. It is hos ...
.
Various solving algorithms descriptionsRosettacodefree polyomino generators in various programming languages
{{Authority control
Polyforms
Recreational mathematics
Mathematical games