POLYOMINO_MONOHEDRAL
Seek Solutions of Polyomino Monohedral Tiling

POLYOMINO_MONOHEDRAL, a MATLAB library which is given matrices defining a region R and a polyomino P; it sets up the corresponding linear system, and solves for binary solutions x that represent possible tilings of the region R by the polyomino P.

A region R is a subset of an MRxNR grid of squares.

A polyomino P is a subset of an MPxNP grid of squares.

Both objects are represented by binary matrices, with the property that there are no initial or final zero rows or columns.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Source Code:

• i4mat_is_binary.m, is TRUE if an I4MAT contains only 0 and 1 entries.
• ksub_next4.m, returns, one at a time, all the K-subsets of a set.
• 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_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_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_monohedral.m, sets up and solves a polyomino monohedral tiling problem.
• polyomino_monohedral_matrix.m, determines the matrix and right hand side for a polyomino monohedral problem.
• polyomino_monohedral_tiling_print.m, prints a tiling of a region R by a polyomino P, based on a solution computed by polyomino_monohedral.
• polyomino_monohedral_variants.m, carries out reflections and rotations of a polyomino to determine which transformations yield distinct variants.
• polyomino_print.m, prints a polyomino.
• polyomino_transform.m, carries out reflections and rotations of a polyomino.
• r8mat_rref.m, returns the reduced row echelon form of an R8MAT.
• 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_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.
• timestamp.m, prints the YMDHMS date as a timestamp.

Examples and Tests:

• polyomino_monohedral_test.m
• polyomino_monohedral_test.txt
• reid.lp, an LP file created by the test program for the Reid example.
• 4x5.lp, an LP file created by the test program for the 4x5 rectangle example.