POLYOMINO_EMBED
Embed a Polyomino in a Region


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.

A region R is a subset of an MRxNR grid of squares.

A polyomino P is a subset of an MPxNP grid of squares.

Both objects are represented by binary matrices, with the property that there are no initial or final zero rows or columns.

For this computation, we regard P as a "fixed" polyomino; in other words, no reflections or rotations will be allowed.

An "embedding" of P into R is an offset (MI,NJ) such that

  P(I,J) = R(I+MI,J+NJ) 
  for 1 <=  I <=    MP, 1 <=  J <=    NP, and 
  for 0 <= MI <= MR-MP, 0 <= MJ <= NR-NP.
We can detect an embedding simply by taking what amounts to a kind of dot product of P with a corresponding subregion of R.

Licensing:

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

Languages:

POLYOMINO_EMBED 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_ENUMERATE, a C library which enumerates chiral, fixed and free polyominoes up to a moderate order.

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 01 May 2018.