POLYOMINO_MULTIHEDRAL
Seek Solutions of Polyomino Multihedral Tiling

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

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

The k-th polyomino P(k) is a subset of an MRxNR grid of squares.

Both objects are represented by an MRxNR binary matrices.

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_index.m, computes an index for each nonzero polyomino entry.
• polyomino_lp_write.m, writes an LP file describing a particular problem.
• polyomino_multihedral.m, sets up and solves a polyomino multihedral tiling problem.
• polyomino_multihedral_matrix.m, determines the matrix and right hand side for a polyomino multihedral problem.
• polyomino_multihedral_tiling_print.m, prints a tiling of a region R by a set of polyominoes P, based on a solution computed by polyomino_multihedral.
• polyomino_multihedral_variants.m, carries out reflections and rotations of a set of polyominoes 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_multihedral_test.m
• polyomino_multihedral_test.txt
• 2x4.lp, an LP file created by the test program for the 2x4 rectangle example.