pariomino
pariomino,
a MATLAB code which
considers pariominoes, which are polyominoes with a checkerboard parity,
and the determination of tilings of a region using a specific set of
pariominoes.
Licensing:
The computer code and data files described and made available on this web page
are distributed under
the GNU LGPL license.
Languages:
pariomino is available in
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.
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 306090 triangles, known as polydrafters.
pariomino_test
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.
polyominoes,
a MATLAB code which
defines, solves, and plots a variety of polyomino tiling problems,
which are solved by a direct algebraic approach involving the
reduced row echelon form (RREF) of a specific matrix, instead of the
more typical bruteforce or backtracking methods.
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 pariomino tiling problem.

LPmake_2by4_alt.m,
performs step 1 of a polyomino tiling problem, in which
a 2x4 rectangle is to be tiled with one Tshaped tetromino,
one monomino, and one Lshaped triomino. In this computation,
parity arguments are not used.

LPmake_2by4_alt_case1.m,
performs step 1 of a pariomino tiling problem, in which
a 2x4 rectangle is to be tiled with one Tshaped tetromino,
one monomino, and one Lshaped triomino. Parity arguments are used.

LPmake_2by4_alt_case2.m,
performs step 1 of a pariomino tiling problem, in which
a 2x4 rectangle is to be tiled with one Tshaped tetromino,
one monomino, and one Lshaped triomino. Parity arguments are used.

plot_pariomino.m,
after (step 1) a pariomino 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 functions for reading the
optimizer solution are accessible in the polyominoes directory.
The general library of pariomino functions:

colour_poly.m,
creates a matrix for a pariomino using 1, 0, and +1 values.

cplex_solution_single_read.m,
extracts solution data from a structure obtained from a
CPLEX data that contained a single solution.

cplex_solution_multiple_read.m,
extracts solution data from a structure obtained from a
CPLEX data that contained multiple solutions.

cplex_solution_read.m,
reads an XML file, converts the data to a structure,
and extracts the data representing solutions.

file_line_count.m,
returns the number of lines in a file.

filename_inc.m
numerically "increments" a file name.

gurobi_solution_read.m,
reads a file created by GUROBI, representing a solution of a
polyomino tiling problem, and extracts the solutions as a
simple vector.

i4mat_is_ternary.m,
is TRUE if an I4MAT contains only 1, 0 and 1 entries.

i4mat_print.m,
prints an I4MAT;

i4mat_print_some.m,
prints some of an I4MAT;

i4vec2_print.m,
prints a pair of integer vectors.

ksub_next4.m,
returns, one at a time, all the Ksubsets of a set.

pariomino_area.m,
returns the area of a pariomino, simply the number of 1's
in the representation.

pariomino_condense.m,
cleans up a matrix that represents a pariomino by setting all nonzero
entries to 1, and removing initial and final rows and columns of zeros.

pariomino_embed_list.m,
for each possible embedding, lists the translation necessary to
to apply to the pariomino.

pariomino_embed_number.m,
reports the number of ways a pariomino can be embedded in a region.

pariomino_equal.m,
is true if two pariominoes are equal.

pariomino_index.m,
computes an index for each nonzero pariomino entry.

pariomino_lp_write.m,
writes an LP file describing a particular problem.

pariomino_matrix.m,
determines the matrix and right hand side for a pariomino problem.

pariomino_matrix_reid.m,
returns the matrix associated with the Reid tiling problem.

pariomino_parity.m,
computes the parity of a pariomino.

pariomino_print.m,
prints a pariomino.

pariomino_reverse.m,
reverses the parity of the cells of a pariomino.

pariomino_tiling_plot.m,
is given matrices defining a region R and a set of pariominoes P,
and a solution vector X, which represents
a tiling of R by the pariominoes in P, and plots a representation
of that tiling.

pariomino_tiling_print.m,
is given matrices defining a region R and a set of pariominoes P,
and a solution vector X, which represents
a tiling of R by the pariominoes in P, and prints out a representation
of that tiling.

pariomino_tiling_solver.m,
sets up and solves a pariomino tiling problem.

pariomino_transform.m,
carries out reflections and rotations of a pariomino.

pariomino_variants.m,
carries out reflections and rotations of a set of pariominoes to
determine which transformations yield distinct variants.

pariominoes_print.m,
prints pariominoes packed in an array.

plot_checker_tile.m,
plots a pariomino in gray and black.

polyomino_charge.m,
creates a pariomino from a polyomino, by assigning a parity
to each cell.

polyomino_print.m,
prints a polyomino.

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.

r8vec_print.m,
prints an R8VEC.

s_len_trim.m
returns the length of a string to the last nonblank;

s_word_extract_first.m
extracts the first word from a string;

scip_index_read.m,
reads a file created by SCIP, representing solutions to a
polyomino tiling problem, and extracts information about the
permutation of the variables.

scip_solution_read.m,
reads a file created by SCIP, representing solutions to a
polyomino tiling problem, and extracts the solutions as a
simple vector.

xml2struct.m,
reads an XML file and converts the data to a structure.
Last revised on 04 August 2020.