chrominoes

chrominoes, a MATLAB code which searches for tilings of a polygonal region using polyominoes, in which a coloring scheme is used to reduce the problem size and quickly eliminate certain arrangements.

Licensing:

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

Languages:

chrominoes is available in a MATLAB version.

Related Programs and Data:

chrominoes_test

cplex_solution_read, a MATLAB code which extracts solution data from a CPLEX solution file; CPLEX reads an LP problem definition file, which might have been created by polyomino_monohedral_matrix() or polyomino_multihedral_matrix(), and returns a solution file. This function opens the solution file and extracts the solution information in a standard vector format.

pariomino, a MATLAB code which considers pariominoes, which are polyominoes with a checkerboard parity.

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

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. Marcus Garvie, John Burkardt,
   A new algorithm based on colouring arguments for identifying impossible polyomino tiling problems,
   Algorithms,
   Volume 15, Number 2, 65, February 2022.
3. Solomon Golomb,
   Polyominoes: Puzzles, Patterns, Problems, and Packings,
   Revised and expanded second edition,
   Princeton University Press, 1996,
   ISBN: 9780691024448

Source Code:

• colour_C_variants.m, creates and plots matrices for a coloured region.
• count_colours.m, counts the squares of each color in a C-coloured rectangle.
• cplex_solution_read.m, reads an XML file, converts the data to a MATLAB structure, and extracts the data representing solutions.
• cplex_solution_single_read.m, extracts solution data from a structure obtained from a CPLEX data that contained a single solution.
• cplex_solution_multiple_read.m, extracts solution data from a structure obtained from a CPLEX data that contained multiple solutions.
• LPmake_Problem71_Golo.m, sets up an LP version of Golomb's problem 71.
• splitting_monohedral_matrix.m, constructs a monohedral tiling linear system.
• splitting_multihedral_matrix.m, constructs a multihedral tiling linear system.
• variants_lp_write.m, writes an LP file for a chromino splitting problem.
• xml2struct.m, reads an XML file and converts the data to a MATLAB structure.