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 information on this web page is distributed under the MIT license.

Languages:

pariomino is available in a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

pariomino_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.

chrominoes, a MATLAB code which searches for tilings of a polygonal region using polyominoes, in which a coloring scheme is used to reduce the problem size and quickly eliminate certain arrangements.

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.

eternity_hexity, a MATLAB code which evaluates and manipulates a six-fold parity quantity associated with grids and tiles used in the Eternity puzzle.

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 brute-force or backtracking methods.

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 tiling problems:

• LPmake_pariominoes_Figure2.m
• LPmake_pariominoes_Figure3.m
• LPmake_pariominoes_Figure4.m
• LPmake_pariominoes_Figure5.m
• LPmake_pariominoes_Figure6.m
• LPmake_pariominoes_Figure7.m
• LPmake_pariominoes_Figure8.m
• LPmake_pariominoes_Figure9.m
• LPmake_pariominoes_Figure10.m
• LPmake_pariominoes_Figure11.m
• LPmake_pariominoes_Figure12.m
• LPmake_pariominoes_Figure13.m
• LPmake_pariominoes_Figure14.m
• colour_poly.m
• diamondshapes.m
• fournotchedsquareshapes.m
• jaggedsquare.m

The general library of pariomino functions:

• colour_poly.m, creates a matrix for a pariomino using -1, 0, and +1 values.
• cplex_solution_read.m, reads a file created by cplex(), representing a solution of a polyomino tiling problem, and extracts the solutions as a simple vector.
• diophantine_nd_nonnegative_bounded.m, determines bounded nonnegative diophantine 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 K-subsets 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.
• plot_pariomino.m, plots pariomino tilings after optimization.
• 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_count.m counts the words in a string;
• s_word_extract_first.m extracts the first word from a string;
• 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.