POLYOMINOES, a MATLAB library of functions for the polyomino tiling problem.
Users interested in trying out the library by working throught the problems discusses in the paper might start with the SCRIPTS, which set up sample problems and handle the plotting of solutions.
A gzipp'ed tar file, which contains the contents of this directory, can be downloaded from: http://people.sc.fsu.edu/~jburkardt/m_src/polyominoes.tar.gz
Users interested in specific problems or algorithms can browse below under the Individual Topics section.
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.)
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
CPLEX_SOLUTION_READ, a MATLAB program which extracts solution data from a CPLEX result file; CPLEX can be "fed" by an LP file created by POLYOMINO_MONOHEDRAL_MATRIX or POLYOMINO_MULTIHEDRAL_MATRIX, and the results can be displayed by POLYOMINO_MONOHEDRAL_TILING_PRINT or POLYOMINO_MULTIHEDRAL_TILING_PRINT.
GUROBI_SOLUTION_READ, a MATLAB program which reads a file created by the optimization package GUROBI, representing the solution of a polyomino tiling problem, and writes out a simple ASCII file that can be read by load().
PENTOMINOES, a MATLAB library which provides some utilities for manipulating pentominoes.
POLYOMINO_CONDENSE, a MATLAB 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 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.
POLYOMINO_ENUMERATE, a MATLAB library which enumerates fixed and free polyominoes of orders 0 through 28.
POLYOMINO_INDEX, a MATLAB 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 MATLAB 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_MATRIXSPAN, a MATLAB program which assembles a matrix associated with a polyomino tiling problem.
POLYOMINO_MONOHEDRAL, a MATLAB program which is given matrices defining a region R and a polyomino P, and seeks binary solutions x that represent possible tilings of the region R by the polyomino P.
POLYOMINO_MONOHEDRAL_EXAMPLE_REID, a MATLAB program which sets up and solves the Reid example of a polyomino tiling problem, using copies of a single polyomino P to tile a region R.
POLYOMINO_MONOHEDRAL_MATRIX, a MATLAB program which is given matrices defining a region R and a polyomino P, and returns the linear system A*x=b that must be solved for binary solutions x, that represent possible tilings of the region R by the polyomino P.
POLYOMINO_MONOHEDRAL_TILING_PLOT, a MATLAB library which is given matrices defining a region R and a polyomino P, and a vector X, computed by POLYOMINO_MONOHEDRAL, which represents a tiling of R by P, and creates a graphic plot representation of that tiling.
POLYOMINO_MONOHEDRAL_TILING_PRINT, a MATLAB library which is given matrices defining a region R and a polyomino P, and a vector X, computed by POLYOMINO_MONOHEDRAL, which represents a tiling of R by P, and prints out a representation of that tiling.
POLYOMINO_MONOHEDRAL_VARIANTS, a MATLAB program which computes the distinct variants of a polyomino under reflection and 90 degree rotations.
POLYOMINO_MULTIHEDRAL, a MATLAB library which is given matrices defining a region R and a set of polyominoes P, and seeks binary solutions x that represent possible tilings of the region R by the polyominoes of P.
POLYOMINO_MULTIHEDRAL_EXAMPLE_2X4, a MATLAB program which sets up and solves an example of a polyomino tiling problem, in which a 2x4 rectangle R is to be tiled using several different polyominoes.
POLYOMINO_MULTIHEDRAL_EXAMPLE_OCTOMINO, a MATLAB program which sets up a problem in which an 8x8 square is to be tiled by 8 distinct octominoes.
POLYOMINO_MULTIHEDRAL_EXAMPLE_PENT18X30, a MATLAB program which sets up a problem in which an 18x30 rectangle is to be tiled by 9 copies of each of the 12 distinct pentominoes, and plots a solution computed by GUROBI.
POLYOMINO_MULTIHEDRAL_EXAMPLE_PENTOMINO, a MATLAB program which sets up a problem in which an 8x8 square with 2x2 central hole is to be tiled by the 12 distinct pentominoes.
POLYOMINO_MULTIHEDRAL_MATRIX, a MATLAB library which is given matrices defining a region R and a set of several polyominoes P, and returns the linear system A*x=b that must be solved for binary solutions x, that represent possible tilings of the region R by the polyominoes in P.
POLYOMINO_MULTIHEDRAL_TILING_PLOT, a MATLAB library which is given matrices defining a region R and a set of several polyominoes P, and a vector X which represents a tiling of R by the elements of P, and creates a plot of that tiling.
POLYOMINO_MULTIHEDRAL_TILING_PRINT, a MATLAB library which is given matrices defining a region R and a set of polyominoes P, and a vector X, computed by POLYOMINO_MULTIHEDRAL, which represent a tiling of R by the polyominoes in P. The task is to print out a representation of that tiling.
POLYOMINO_MULTIHEDRAL_VARIANTS, a MATLAB program which computes the distinct variants of one or more polyominoes under reflection and 90 degree rotations.
POLYOMINO_TRANSFORM, a MATLAB program which applies reflection and rotation transforms to the matrix that represents a polyomino.
POLYOMINOES_PRINT, a MATLAB program which prints an array of polyominoes.
SCIP_SOLUTION_READ, a MATLAB program which reads a file created by the integer programming package SCIP, representing the solution of a polyomino tiling problem, and writes out a simple ASCII file that can be read by load().
SCRIPTS, MATLAB scripts that set up sample polyomino tiling problems, and simplify the process of plotting the corresponding solutions.