polyominoes


polyominoes, a MATLAB code which considers polyominoes, and the question of tiling a region R.

A region R is a connected subset of an MRxNR grid of squares. "Holes" are allowed in R.

A polyomino is a shape formed by connecting unit squares edgewise.

Regions and polyominoes can be represented by rectangular matrices, whose entries are 1 for squares that are part of the polyomino, and 0 otherwise.

In a tiling problem, a region R is given, as well as a set of one or more polyominoes. Each polyomino will also have a duplication factor D, indicating how many times it must be used in the tiling. The task is to determine how to arrange the polyominoes so that each cell of R is covered exactly once, and no other cells are covered.

If the tiling is to be done using only a single type of polyomino, this is termed a "monohedral" tiling problem; otherwise it is called "multihedral". Monohedral problems are easier to set up and define, and so this library often provides separate "mono" and "multi" versions of the algorithms.

The approach studied here rewrites this problem as a set of underdetermined algebraic equations. Each equation represents the covering of a particular cell, or the stipulation on the number of times a given polyomino must be used. Each variable corresponds to a particular reflection, rotation, and translation of one of the polyomino shapes.

Very small problems can be solved using the row reduced echelon form of the linear system. In general, however, an integer programming package, such as CPLEX, GUROBI, or SCIP, must be invoked to obtain solutions which are integer, and in fact binary (only 0 or 1 values allowed.)

Licensing:

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

Languages:

polyominoes is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

boundary_word, a MATLAB code which works with a polyomino that is described by a sequence of symbols that indicate how to trace out its boundary.

pariomono, a MATLAB code which considers pariomonoes, which are polyominoes with a checkerboard parity.

polyomino_parity, a MATLAB code which uses parity considerations to determine whether a given set of polyominoes can tile a specified region.

polyominoes_test

Reference:

  1. Marcus Garvie, John Burkardt,
    A new mathematical model for tiling finite regions of the plane with polyominoes,
    Contributions to Discrete Mathematics,
    Accepted, June 2020.
  2. Marcus Garvie, John Burkardt,
    Checkerboard colouring arguments for impossible polyomino tiling problems,
    Discrete and Computational Geometry,
    Accepted, June 2020.
  3. Solomon Golomb,
    Polyominoes: Puzzles, Patterns, Problems, and Packings,
    Princeton University Press, 1996,
    ISBN: 9780691024448

Source code:

Some master functions for a monohedral polyomino tiling problem.

Some master functions for a multihedral polyomino tiling problem:

The general library of polyomino functions:


Last revised on 22 July 2020.