# 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.)

### 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_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:

1. 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.
2. 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.
• 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, SCIP, or GUROBI, this function (step 3) can create plots of the corresponding tilings.

Some master functions for a multihedral polyomino tiling problem:

• LPmake_Figure9b.m, performs step 1 of a multihedral tiling problem, in which a copy of each of the 12 pentominoes are to be used to tile the 6x10 rectangle. This example is depicted in figure 9b of the "Contributions to Discrete Mathematics" reference paper.
• LPmake_Figure10a.m, performs step 1 of a multihedral tiling problem, in which 4 copies of each of 8 octominoes are to be used to tile an L-shaped region. This example is depicted in figure 10a of the "Contributions to Discrete Mathematics" reference paper.
• LPmake_Figure10b.m, performs step 1 of a multihedral tiling problem, in which 1 or 2 copies of each of the 12 pentominoes are to be used to tile an 11x11 region with 4 2x2 holes. This example is depicted in figure 10b of the "Contributions to Discrete Mathematics" reference paper.
• LPmake_Figure12.m, performs step 1 of a multihedral tiling problem, in which 20 copies of each of the 12 pentominoes are to be used to tile a 30x40 region. This example is depicted in figure 12 of the "Contributions to Discrete Mathematics" reference paper.
• 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, SCIP, or GUROBI, this function (step 3) can create plots of the corresponding tilings.

The general library of polyomino functions:

Last revised on 20 June 2021.