POLYOMINO_MULTIHEDRAL_EXAMPLE_2X4
Solution of a Sample Tiling Problem

POLYOMINO_MULTIHEDRAL_EXAMPLE_2X4, a MATLAB program which sets up and solves the 2x4 example of a polyomino tiling problem, using several polyominos for the tiling.

A region R consists of the following arrangement of square cells:

        1 1 1 1
        1 1 1 1

We can assign an index to each cell, as follows:

        1 2 3 4
        5 6 7 8

We are given a set of 3 polyomino tiles, N, O, and P, and it is desired to arrange these tiles in such a way that they exactly cover R, that is, each cell of R is covered exactly once by a tile cell, and every tile cell is covering a cell of R.

The shapes of the 3 tiles are

Allowing reflections and rotations, there are:

        1 variant of N:

          N1 = 1
  
        2 variants of O:
  
          O1 = 1 1 1
  
          O2 = 1
               1
               1
  
        8 variants of P:
  
          P1 = 0 0 1
               1 1 1
  
          P2 = 1 1
               0 1
               0 1
  
          P3 = 1 1 1
               1 0 0
  
          P4 = 1 0
               1 0
               1 1
  
          P5 = 1 0 0
               1 1 1
  
          P6 = 0 1
               0 1
               1 1
  
          P7 = 1 1 1
               0 0 1
  
          P8 = 1 1
               1 0
               1 0

There are 8 ways to place N1 on R:

There are 4 ways to place O1 and no ways to place O2 on R:

There are 2 ways to place each of P1, P3, P5, or P7 on R, and no ways to place P2, P4, P6, or P8:.

        p11: 3 5 6 7
        p12: 4 6 7 8
        p31: 1 2 3 5
        p32: 2 3 4 6
        p51: 1 5 6 7
        p52: 2 6 7 8
        p71: 1 2 3 7
        p72: 2 3 4 8

We can only use N once:

        n11 + n12 + n13 + n14 + n15 + n16 + n17 + n18 = 1

We can only use O once:

        o11 + o12 + o13 + o14 = 1

We can only use P once:

        p11 + p12 + p31 + p32 + p51 + p52 + p71 + p72 = 1

The area covered by copies of N, O, and P must have the same area as R:

        1 * n11 + 1 * n12 + 1 * n13 + 1 * n14 
      + 1 * n15 + 1 * n16 + 1 * n17 + 1 * n18
      + 3 * o11 + 3 * o12 + 3 * o13 + 3 * o14
      + 4 * p11 + 4 * p12 + 4 * p31 + 4 * p32 
      + 4 * p51 + 4 * p52 + 4 * p71 + 4 * p72 = 8

The requirement that each of the 8 cells of R be covered exactly once using some choice of placement for P1, P2 and P3 can be expressed as the linear system for which only binary solutions (0 or 1 valued) are sought:

The linear system is a bit large to print out. We present it in three strips of columns: A = [ N | O | P ]:

          <---------- N ---------------------->
          x1   x2   x3   x4   x5   x6   x7   x8 
        +--------------------------------------
      R1: n11                            
      R2:      n12                        
      R3:           n13                    
      R4:                n14                
      R5:                     n15            
      R6:                          n16        
      R7:                               n17    
      R8:                                    n18

      N:  n11  n12  n13  n14  n15  n16  n17  n18
      O:                                 
      P:                                 

      R: 1n11 1n12 1n13 1n14 1n15 1n16 1n17 1n18


          <------ O -------> 
          x9   x10  x11  x12 
        +-------------------
      R1: o11            
      R2: o11  o12        
      R3: o11  o12        
      R4:      o12        
      R5:           o13    
      R6:           o13  o14
      R7:           o13  o14
      R8:                o14

      N:
      O:  o11  o12  o13  o14
      P:                  

      R: 3o11 3o12 3o13 3o14


          <----------- P ----------------------> <-B-> 
          x13  x14  x15  x16  x17  x18  x19  x20   b
        +-------------------------------------------
      R1:           p31       p51       p71      = 1
      R2:           p31  p32       p52  p71  p72 = 1
      R3: p11       p31  p32            p71  p72 = 1
      R4:      p12       p32                 p72 = 1
      R5: p11       p31       p51                = 1
      R6: p11  p12       p32  p51  p52           = 1
      R7: p11  p12            p51  p52  p71      = 1
      R8:      p12                 p52       p72 = 1

      N:                                         = 1
      O:                                         = 1
      P:  p11  p12  p31  p32  p51  p52  p71  p72 = 1

      R: 4p11 4p12 4p31 4p32 4p51 4p52 4p71 4p72 = 8

We regard this as a linear system of equations A*x=b, where

        x = [n11 n12 n13 n14 n15 n16 n17 n18 
             o11 o12 o13 o14 
             p11 p12 p31 p32 p51 p52 p71 p72 ].

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

Instead, we consider the row reduced echelon form of the system, identify the degrees of freedom, and consider just the solution vectors x corresponding to setting those degrees of freedom to 0 or 1.

(At this point, we do not take one further efficiency step, and only consider binary solutions x with exactly 3 nonzero entries.)

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.

Source Code:

polyomino_lp_write.m, writes an LP file describing a particular problem.
polyomino_multihedral_example_2x4.m, sets up and solves the two by four polyomino example.
polyomino_multihedral_example_2x4_system.m, sets up the two by four 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.

Examples and Tests:

polyomino_multihedral_example_2x4.txt, the output file.
2x4.lp, an LP file which formulates the problem.

Last revised on 17 May 2018.

POLYOMINO_MULTIHEDRAL_EXAMPLE_2X4 Solution of a Sample Tiling Problem

Licensing:

Source Code:

Examples and Tests:

POLYOMINO_MULTIHEDRAL_EXAMPLE_2X4
Solution of a Sample Tiling Problem