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.
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 nominoes (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 xaxis 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
Search Encyclopedia

Featured Article

