POLYOMINO_MULTIHEDRAL_EXAMPLE_OCTOMINO
8 Octominoes Tile an 8x8 Square

POLYOMINO_MULTIHEDRAL_EXAMPLE_OCTOMINO, a MATLAB program which sets up a problem in which an 8x8 square is to be tiled by 8 distinct octominoes.

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 all solutions. The resulting solutions are then read by CPLEX_SOLUTION_READ, and can be printed or plotted.

Because of the symmetry of the problem, the 8 solutions that are computed actually represent a single solution, which may be rotated and reflected to generate 8 variations.

Licensing:

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

Source Code:

• 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_octomino_matrix.m, computes the linear system for the octomino example.
• polyomino_multihedral_example_octomino_tiling_plot.m, plots the solutions of the octomino example.
• polyomino_multihedral_example_octomino_tiling_print.m, prints the solutions of the octomino 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_octomino_matrix.txt, output file.
• polyomino_multihedral_example_octomino_tiling_plot.txt, output file.
• polyomino_multihedral_example_octomino_tiling_plot.txt, output file.
• octomino.lp, an LP file which records the linear system to be solved by CPLEX.
• octomino_solution.xml, solutions computed by CPLEX.
• octomino_solution.txt, a simple text version of the CPLEX solutions, readable by load().
• octomino01.png
• octomino02.png
• octomino03.png
• octomino04.png
• octomino05.png
• octomino06.png
• octomino07.png
• octomino08.png