POLYOMINO_EMBED
Embed a Polyomino in a Region

POLYOMINO_EMBED, a MATLAB 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.

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 MATLAB version.

Related Data and Programs:

polyomino_embed_test

Source Code:

• polyomino_embed_list.m, for each possible embedding, lists the translation necessary to to apply to the polyomino.
• polyomino_embed_list_test.m
• polyomino_embed_number.m, reports the number of ways a polyomino can be embedded in a region.
• polyomino_embed_number_test.m
• polyomino_print.m, prints a polyomino.
• timestamp.m, prints the YMDHMS date as a timestamp.