POLYOMINO_MONOHEDRAL_EXAMPLE_REID
Polyomino Tiling Example REID

POLYOMINO_MONOHEDRAL_EXAMPLE_REID, a MATLAB program which sets up and solves the Reid example of a polyomino tiling problem, using copies of a single polyomino P to tile a region R.

A region R consists of the following arrangement of square cells, (numbered row first):

        1 2
        3 4 5
        6 7 8

We are given a polyomino P, also composed of square cells, and also numbered row first (although in this case it doesn't matter):

        1 2

It is desired to use a set of 4 copies of P to cover the region R, so that each cell is covered exactly once by a tile cell, and every tile cell covers some cell of R.

There are two versions of the polyomino:

• P1: no reflection, no rotation:

            1 2
  

• P2: no reflection, rotation of 90 degrees:

            1
            2
  

There are 5 distinct ways to place a single copy of P1 onto R, and 5 ways to use P2 in this way. We will index each way as a separate "variable" called X, and we can describe each X by the squares of R that it covers. Again, we traverse R rowwise as we search:

        x1: P1 on 1 2
        x2: P1 on 3 4
        x3: P1 on 4 5
        x4: P1 on 6 7
        x5: P1 on 7 8

        x6: P2 on 1 3
        x7: P2 on 2 4
        x8: P2 on 3 6
        x9: P2 on 4 7
       x10: P2 on 5 8

We also require that the areas of the cells used equal the area of R:

        2x1 + 2x2 + 2x3 + 2x4 + 2x5 + 2x6 + 2x7 + 2x8 + 2x9 + 2x10 = 8

The requirement that each of the cells of R be covered exactly once, and that just the total area of the tiles used is equal to the area of the region results in a linear system:

         <--------- P1 -------->   <-------- P2 --------->
          x1   x2   x3   x4   x5   x6   x7   x8   x9   x10   b
        +-----------------------------------------------------
      R1: x1                     + x6                      = 1
      R2: x1                          + x7                 = 1
      R3:      x2                + x6      + x8            = 1
      R4:      x2 + x3                + x7      + x9       = 1
      R5:           x3                               + x10 = 1
      R6:                x4                + x8            = 1
      R7:                x4 + x5                + x9       = 1
      R8:                     x5                     + x10 = 1

      A: 2x1 +2x2 +2x3 +2x4 +2x5 +2x6 +2x7 +2x8 +2x9 +2x10 = 8

The system A*x=b is underdetermined, and hence infinite families of solutions may exist. However, we are only interested in solutions in which every entry of x is an integer and in fact, every entry of x is 0 or 1. Given, in this case, 10 variables, there can be of course no more than 2^10 possible such vectors x, and we could simply try them all by brute force.

We can significantly reduce the work involved by computing the row reduced echelon form of the system. This allows us to determine the number of degrees of freedom in the solution. Our search for acceptable binary solutions can then be carried out by considering every possible binary assignment of the degrees of freedom in which no more than 4 degrees of freedom are set to 1.

Note that the formation of the RREF matrix is highly subject to roundoff error. In particular, if an entry which should mathematically be zero is instead nonzero, it may be taken for a pivot, and renormalized to 1, completely changing the structure of the solution. For this reason, the RREF should be computed cautiously, and with a tolerance.

Licensing:

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

Languages:

polyomino_monohedral_example_reid is available in a MATLAB version.

Related Data and Programs:

polyomino_monohedral_example_reid_test

Source Code:

• polyomino_lp_write.m, writes an LP file describing a particular problem.
• polyomino_monohedral_example_reid_system.m, sets up the Reid linear system.
• polyomino_print.m, prints a polyomino.
• r8mat_rref.m, computes the reduced row echelon form of a matrix.
• r8mat_rref_solve_binary.m, seeks binary solutions of an RREF system.
• r8mat_u_solve.m, solves an upper triangular linear system.
• r8vec_binary_next.m, generates the next binary vector.
• r8vec_identity_row.m, returns a row of the identity matrix.
• r8vec_is_binary.m, is true if an R8VEC only contains 0 and 1 entries.
• timestamp.m, prints the current YMDHMS date as a timestamp.