POLYOMINO_ENUMERATE
Enumerate Polyominoes


POLYOMINO_ENUMERATE, a C++ program which enumerates chiral, fixed and free polyominoes of moderate order.

POLYOMINO_ENUMERATE does not compute anything; it simply stores a list of counts for polyominoes of orders 0 through 28, and when given a particular order, returns the corresponding number of polyominoes.

A polyomino is formed by connecting a number of unit squares. The order of a polyomino is the number of squares used in its formation. When we ask how many polyominoes there are of a specific order, we must state whether we distinguish two polyominoes which differ only in reflection or rotation.

For "chiral" or "one-sided" polyominoes, we do not regard rotations as producing a distinct polyomino;

for "fixed" polyominoes, reflections and rotations can produce a polyomino that is regarded as distinct;

For "free" polyominoes, we do not regard reflections or rotations as producing a distinct polyomino;.

Counts are given for chiral, fixed, and free polyominoes. Note, also, that for orders of 7 and more, the counts include polyominoes that have "holes".

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

POLYOMINO_ENUMERATE is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

PENTOMINOES, a C++ library which provides some utilities for manipulating pentominoes.

POLYOMINO_CONDENSE, a C++ program which cleans up a matrix that represents a polyomino by setting all nonzero entries to 1, and removing initial and final rows and columns of zeros.

POLYOMINO_EMBED, a C++ library which is given matrices defining a region R and a polyomino P, and determines the number of possible embeddings of the polyomino into the region, and the translations necessary to achieve them.

POLYOMINO_INDEX, a C++ library which is given a matrix defining a polyomino P, and determines a correspondingly shaped matrix which contains an index for each nonzero entry in P.

POLYOMINO_LP_WRITE, a C++ program which writes an LP file describing a (binary) integer programming problem related to the tiling of a region R by copies of polyomino shapes, with possible reflections and rotations.

POLYOMINO_TRANSFORM, a C++ program which applies reflection and rotation transforms to the matrix that represents a polyomino.

Reference:

  1. Solomon Golomb,
    Polyominoes: Puzzles, Patterns, Problems, and Packings,
    Princeton University Press, 1996,
    ISBN: 9780691024448

Source Code:

Examples and Tests:


Last revised on 27 May 2018.