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 MIT 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:
polyominoes_test
boundary_word_square,
a MATLAB code which
describes the outline of an object on a grid of squares,
using a string of symbols that represent the sequence of steps
tracing out the boundary.
cplex_solution_read,
a MATLAB code which
extracts solution data from a cplex() result file;
cplex() reads an LP file created by polyomino_monohedral_matrix()
or polyomino_multihedral_matrix(), and the results
are displayed by polyomino_monohedral_tiling_print() or
polyomino_multihedral_tiling_print().
eternity,
a MATLAB code which
considers the eternity puzzle, which considers an irregular dodecagon
shape that is to be tiled by 209 distinct pieces, each formed by 36
contiguous 30-60-90 triangles, known as polydrafters.
gurobi_solution_read,
a MATLAB code 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 to be read by the load() function.
pariomino,
a MATLAB code which
considers pariominoes, which are polyominoes with a checkerboard parity.
polyiamonds,
a MATLAB code which
works with polyiamonds, simple shapes constructed by edgewise
connections of congruent equilateral triangles.
polyomino_parity,
a MATLAB code which
uses parity considerations to determine whether a given set of
polyominoes can tile a specified region.
scip_solution_read,
a MATLAB code 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().
Reference:
-
Marcus Garvie, John Burkardt,
A new mathematical model for tiling finite regions of the plane
with polyominoes,
Contributions to Discrete Mathematics,
Volume 15, Number 2, July 2020.
-
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.
-
LPmake_Figure9a.m,
performs step 1 of a monohedral tiling problem, in which
30 copies of the triomino are to be used to tile the 18x5 rectangle.
This example is depicted in figure 9a of the "Contributions to
Discrete Mathematics" reference paper.
-
LPmake_Figure11.m,
performs step 1 of a monohedral tiling problem, in which
600 copies of a hexomino are to be used to tile the 60x60 square.
This example is depicted in figure 11 of the "Contributions to
Discrete Mathematics" reference paper.
Some master functions for polyomino tiling problems:
The general library of polyomino functions:
-
cell_ij_fill.m,
plots a filled (I,J) cell.
-
file_line_count.m,
returns the number of lines in a file.
-
filename_inc.m
numerically "increments" a file name.
-
grid_add.m,
adds the region, or a polyomino tile, to the current grid.
-
grid_display.m,
displays a rectangular grid of squares with colors.
-
i4_log_10.m,
returns the integer part of the logarithm base 10 of ABS(X).
-
i4_modp.m,
returns the nonnegative remainder of I4 division.
-
i4_wrap.m,
forces an integer to lie between given limits by wrapping.
-
i4mat_indicator.m,
sets up an indicator matrix.
-
i4mat_is_binary.m,
is TRUE if an I4MAT contains only 0 and 1 entries.
-
i4mat_print.m,
prints an I4MAT;
-
i4mat_print_some.m,
prints some of an I4MAT;
-
i4row_neighbors.m,
returns the four neighbors of a grid point.
-
i4row_sorted_insert.m,
inserts an i4row into a sorted i4row array.
-
i4row_sorted_minus.m,
deletes from S any rows occurring also in C.
-
i4row_sorted_search.m,
searches an ascending sorted I4ROW.
-
i4row_take_random.m,
removes a random row from an i4ROW.
-
i4vec_compare.m,
compares two I4VEC's.
-
i4vec_transpose_print.m,
prints an I4VEC "transposed".
-
i4vec2_print.m,
prints a pair of integer vectors.
-
ksub_next4.m,
returns, one at a time, all the K-subsets of a set.
-
pentomino_display.m
displays a particular pentomino in a 5x5 grid.
-
pentomino_matrix.m
returns a 0/1 matrix defining a particular pentomino.
-
pentomino_name.m
given an index between 1 and 12, returns the corresponding name
F, I, L, N, P, T, U, V, W, X, Y, or Z.
-
pentomino_pack.m
packs the pentominoes into an MxNx12 array.
-
pentomino_print.m,
prints a pentomino.
-
plot_mono.m,
after (step 1) a monohedral tiling problem has been set up,
and then (step 2) solved by one of the optimizers CPLEX,
GUROBI, or SCIP, this function (step 3) can create plots of
the corresponding tilings.
-
plot_multi.m,
after (step 1) a multihedral tiling problem has been set up,
and then (step 2) solved by one of the optimizers CPLEX,
GUROBI, or SCIP, this function (step 3) can create plots of
the corresponding tilings.
-
polyomino_area.m,
returns the area of a polyomino, simply the number of 1's
in the representation.
-
polyomino_condense.m,
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_display.m
displays a polyomino on a grid of squares.
-
polyomino_embed_list.m,
for each possible embedding, lists the translation necessary to
to apply to the polyomino.
-
polyomino_embed_number.m,
reports the number of ways a polyomino can be embedded in a region.
-
polyomino_embed_periodic_number.m,
counts polyomino embeddings in a periodic region.
-
polyomino_enumerate_chiral.m,
enumerates chiral or one-sided polyominoes.
-
polyomino_enumerate_fixed.m,
enumerates fixed polyominoes.
-
polyomino_enumerate_free.m,
enumerates free polyominoes.
-
polyomino_equal.m,
is true if two polyominoes are equal.
-
polyomino_index.m,
computes an index for each nonzero polyomino entry.
-
polyomino_lp_write.m,
writes an LP file describing a particular problem.
-
polyomino_lpa_write.m,
a variant of polyomino_lp_write().
-
polyomino_monohedral.m,
sets up and solves a polyomino monohedral tiling problem.
-
polyomino_monohedral_example_reid_system.m,
returns the linear system associated with a polyomino tiling problem.
-
polyomino_monohedral_matrix.m,
determines the matrix and right hand side for a polyomino monohedral
problem.
-
polyomino_monohedral_matrix2.m,
a variant of polyomino_monohedral_matrix().
-
polyomino_monohedral_tiling_plot.m,
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 displays a graphic representation of that tiling.
-
polyomino_monohedral_tiling_print.m,
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.m,
carries out reflections and rotations of a polyomino to
determine which transformations yield distinct variants.
-
polyomino_multihedral.m,
sets up and solves a polyomino multihedral tiling problem.
-
polyomino_multihedral_example_octomino_matrix.m,
computes the linear system for the octomino example.
-
polyomino_multihedral_example_octomino_tiling_plot.m,
plots the solutions of the octomino example.
-
polyomino_multihedral_example_octomino_tiling_print.m,
prints the solutions of the octomino example.
-
polyomino_multihedral_example_pent18x30_define.m,
defines the problem.
-
polyomino_multihedral_example_pent18x30_tiling_plot.m,
plots the solution.
-
polyomino_multihedral_matrix.m,
determines the matrix and right hand side for a polyomino multihedral
problem.
-
polyomino_multihedral_matrix2.m,
a variant of polyomino_multihedral_matrix().
-
polyomino_multihedral_tiling_plot.m,
is given matrices defining a region R and a set of polyominoes P,
and a vector X, computed by polyomino_multihedral(), which represents
a tiling of R by the polyominoes in P, and plots a representation
of that tiling.
-
polyomino_multihedral_tiling_print.m,
is given matrices defining a region R and a set of polyominoes P,
and a vector X, computed by polyomino_multihedral(), which represents
a tiling of R by the polyominoes in P, and prints out a representation
of that tiling.
-
polyomino_multihedral_variants.m,
carries out reflections and rotations of a set of polyominoes to
determine which transformations yield distinct variants.
-
polyomino_parity.m,
returns the parity of a polyomino.
-
polyomino_periodicity_apply.m,
applies periodicity to a polyomino.
-
polyomino_periodic_matrix.m,
handles polyomino tiling of a periodic rectangle.
-
polyomino_periodic_variants.m,
finds periodic variants of polyominoes.
-
polyomino_print.m,
prints a polyomino.
-
polyomino_random.m,
creates a random polyomino of n squares.
-
polyomino_reflect.m,
reflects a polyomino about the vertical axis.
-
polyomino_sparse_to_full.m,
converts a polyomino from sparse to full form.
-
polyomino_transform.m,
carries out reflections and rotations of a polyomino.
-
polyominoes_print.m,
prints polyominoes packed in an array.
-
r8mat_rref.m,
returns the reduced row echelon form of an R8MAT.
-
r8mat_rref_solve_binary.m,
seeks binary solutions of an RREF system.
-
r8mat_rref_solve_binary_nz.m,
seeks binary solutions (if any) of a row reduced echelon form
linear system in which exactly NZ entries are nonzero.
-
r8mat_u_solve.m,
solves an upper triangular linear system.
-
r8vec_binary_next.m,
generates the next binary vector.
-
r8vec_identity_row.m,
returns a row of the identity matrix as an R8VEC.
-
r8vec_is_binary.m,
is true if all entries of an R8VEC are 0 or 1.
-
s_len_trim.m
returns the length of a string to the last nonblank;
-
s_word_count.m
counts the number of "words" in a string;
-
s_word_extract_first.m
extracts the first word from a string;
-
xml2struct.m,
reads an XML file and converts the data to a structure.
Last revised on 06 June 2022.