POLYOMINO_MULTIHEDRAL_EXAMPLE_PENTOMINO
12 Pentominoes Tile an 8x8 Square with Hole

POLYOMINO_MULTIHEDRAL_EXAMPLE_PENTOMINO, a MATLAB program which sets up a problem in which an 8x8 square with 2x2 central hole is to be tiled by the 12 distinct pentominoes.

Because this problem results in a large linear system to be solved, we simply set up the linear system, write it to an LP file, and have CPLEX compute solutions. The resulting solutions are then read by CPLEX_SOLUTION_READ, and can be printed or plotted.

Licensing:

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

Source Code:

• pentomino_matrix.m, is given the one-letter code for a pentomino, and returns a corresponding shape matrix.
• 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_example_pentomino_matrix.m, computes the linear system for the pentomino example.
• polyomino_multihedral_example_pentomino_tiling_plot.m, plots the solutions of the pentomino example.
• polyomino_multihedral_example_pentomino_tiling_print.m, prints the solutions of the pentomino example.
• 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.
• polyominoes_print.m, prints a set of polyominoes.
• timestamp.m, prints the current YMDHMS date as a timestamp.

Examples and Tests:

• polyomino_multihedral_example_pentomino_matrix.txt, output file.
• polyomino_multihedral_example_pentomino_tiling_plot.txt, output file.
• polyomino_multihedral_example_pentomino_tiling_plot.txt, output file.
• pentomino.lp, an LP file which records the linear system to be solved by CPLEX.
• pentomino_solution.xml, solutions computed by CPLEX.
• pentomino_solution.txt, a simple text version of the CPLEX solutions, readable by load().
• pentomino01.png