polyomino_parity

polyomino_parity, a MATLAB code which uses parity considerations to determine whether a given set of polyominoes can tile a specified region.

Licensing:

The computer code and data files made available on this web page are distributed under the MIT license

Languages:

polyomino_parity is available in a MATLAB version and an Octave versionand a Python version.

Related Data and Programs:

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

diophantine_nd, a MATLAB code which is given a Diophantine equation in N variables, and returns all strictly positive solutions, or all nonnegative solutions.

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.

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.

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:

• addmultisteps.m, seeks combinations of N1 elements of (-Q1,+Q1), N2 elements of (-Q2,Q2), ..., and NK elements of (-QK,+QK), that match a given sum.
• diophantine_equation_print.m, prints the data associated with a Diophantine equation.
• diophantine_nd_check.m, checks that a given Diophantine problem is well posed.
• diophantine_nd_nonnegative.m, returns all nonnegative solutions of a Diophantine equation in N variables.
• diophantine_nd_positive.m, returns all strictly positive solutions of a Diophantine equation in N variables.
• diophantine_solution_print.m, prints the solutions associated with a Diophantine equation.
• pv_search.m, finds trivial and serious parity violations in proposed tilings of a region by a set of polyominoes.
• pv_search_post.m, prints the results from a call to pv_search().
• sumallsteps.m, finds all possible sums of A plus N signed copies of Q.