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 orders of polyomino 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

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 order n can be found by inductive exhaustive search. Given a list of polyominoes of order n, take each polyomino in turn, embed it in an n x n square, surround that square with a collar of cells to create an n+2 x 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 x n+1 square contains a candidate polyomino of order n+1. If this configuration has not been encountered before, it is added to the list of polyominoes of order n+1. Comparison with the polyominoes of order 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 x 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 order of polyomino, but this becomes computationally expensive for high orders. For example finding all the dodecominoes using this algorithm consumes nearly 90 seconds of CPU time on a 1GHz pentium.

See also: tiling