Main Page | See live article | Alphabetical index

Polyomino

A polyomino is a shape made by placing a particular number of squares of the same size in distinct locations on a plane in such a way that at least one edge of each square coincides with an edge of one of the remaining squares (ie the squares are simply connected). If the corner of any square touches the edge of another square at any place other than a corner, the result is not a polyomino. For each strictly positive natural number, n, there are a fixed number of distinct such arrangements of the n squares. For this purpose, a reflected form of a polyomino is not usually regarded as distinct from the original.

In some contexts the definition of a polyomino is relaxed. Sometimes polyominoes are generalised to three or more dimensions by aggregating cubes or hypercubes. For some applications mirror image forms are treated as distinct.

The numbers of configurations for small polyominos are listed below.

1 square: monomino: 1 configuration
2 squares: domino: 1
3 squares: triomino or tromino: 2
4 squares: tetromino: 5
5 squares: pentomino: 12
6 squares: hexomino: 35
7 squares: heptomino: 108 (107 excluding configurations with holes)
8 squares: octomino: 369 (361)
9 squares: nonomino: 1285
10 squares: decomino: 4655
11 squares: undecomino: 17073
12 squares: dodecomino: 63600

No formula for finding the exact number of polyominoes with n squares has been found.

Polyominoes composed of seven or more squares may contain holes (ie regions which are not tiled with squares but which are unconnected to the exterior of the polyomino).

Polyominoes have been used in popular puzzles since the late 19th century, but were first studied systematically by Solomon W. Golomb and were popularized by Martin Gardner. Related to polyominoes are polyamonds (formed from equilateral triangles) and polyhexes (formed from regular hexagons).

An Algorithm for Enumerating all n-ominoes (polyominoes of n squares)

The polyominoes of area n can be found by inductive exhaustive search. Given a list of polyominoes of area n, take each polyomino in turn, embed it in an n×n square, surround that square with a collar of cells to create an n+2 × n+2 square. For each vacant cell in that square that is adjacent to at least one occupied cell, fill the cell and strike out a bounding row of vacant cells and a bounding column of vacant cells. The resulting n+1 × n+1 square contains a candidate polyomino of area n+1. If this configuration has not been encountered before, it is added to the list of polyominoes of area n+1. Comparison with the polyominoes of area n+1 already seen must take account of position and symmetry. Position can accounted for by translating the candidate polyomino to the top left corner of the n+1 × n+1 square. Symmetry can be accounted for by noting that the group of symmetries of a square has eight elements and is generated by alternating reflections about the x-axis and about a diagonal.

This procedure can be applied repeatedly starting from the monomino to reach any desired area of polyomino, but this becomes computationally expensive for large areas. For example finding all the dodecominoes using this algorithm consumes nearly 90 seconds of CPU time on a 1GHz pentium.

See also: tiling

External links