## 6 Numerical Examples
### Tiling Examples Where All Solutions Are Sought
#### 6.2.3 Case 3  
We give two examples of the monohedral polyomino type, where the application of colouring techniques does not split the full (uncoloured) polyomino tiling problem into multiple pariomino tiling subproblems and reduces the complexity. **Example 4** (*). : _Find all ways of tiling the diamond shaped region with 'holes'_  
_all orientations permitted. The area of \(R\) is 168, so we need 56 copies of the L-shaped trinino. The associated ILP file, constructed with the program LPMAKE_POLYONINOES_FIGUREE5, has \(n=336\) unknowns, \(m=168\) constraints, and \(f=168\) free variables. CPLEX found 16 solutions in 0.05 s._  
_Using colouring techniques we wish to tile the checkerboard coloured region \(\widehat{R}\) shown in Figure 15(a) using 56 pariominoes from the set_  
\[\{P_{1}^{+},P_{1}^{-}\}=\bigg{\{}\]  
Figure 15: Target region and a tiling solution for Example 3: (a) The target region \(\widehat{R}\), a checkerboard coloured irregularly shaped region; (b) successful tiling of the target region \(\widehat{R}\) using 72 copies of an L-shaped tetromino. The \(P_{1}^{+}\) variants are coloured light-blue, and the \(P_{1}^{-}\) variants coloured dark-blue corresponding to the single feasible solution of the subproblems when \((a_{1}^{+},a_{1}^{-})=(72,72)\). with parities \(\pm p_{1}=\pm 1\), all orientations permitted. The parity of \(\widehat{R}\) is \(p=+56\), thus the only way to satisfy the parity equation (see Theorem 1) is to choose \(a_{1}^{+}=56\) and \(a_{1}^{-}=0\). That is, the only way to tile \(\widehat{R}\) is to use the parioninoes \(P_{1}^{+}\) and we have a single parionino tiling subproblem. We constructed the ILP file using the program LPMAKE_PARIONIONES_FIGUREE5. CPLEI found 16 solutions with \((m,n,f)=(168,224,60)\) in 0.02 s, thus the potential speedup when using the colouring technique is about 2.5\(\times\). However, as the runtimes are very small, this is not a particularly meaningful measure. The optimal solution of the parionino tiling subproblem is shown in Figure 16b. Observe that for the polyomino tiling problem, we have \(n=336\) and for the parionino tiling subproblem we have \(n=224\), which represent the number of ways \(P_{1}\) fits in \(R\) and \(P_{1}^{+}\) fits in \(\widehat{R}\), respectively. Thus, the number of ways \(P_{1}^{-}\) fits in \(\widehat{R}\) is \(336-224=112\), even though the single tiling solution uses only parioninoes of type \(P_{1}^{+}\). **Example 5**. : _Find all ways of tiling the diamond shaped region with a single 'hole' in the middle_  
\[R=\]  
_all orientations permitted. The area of \(R\) is 84, so we need 28 copies of the \(L\)-shaped trinitino. The associated ILP file, constructed with the program LPMAKE_POLYONINOES_FIQUE6, has \(n=252\) unknowns, \(m=84\) constraints, and \(f=168\) free variables. CPLEI found 731,092 solutions in 165.78 s._  
_Using colouring techniques we wish to tile the checkerboard coloured region \(\widehat{R}\) shown in Figure 17a using 28 parioninoes from the set_  
\[\{P_{1}^{+},P_{1}^{-}\}=\bigg{\{}\]  
Figure 16: Target region and a tiling solution for Example 4: (**a**) the target region \(\widehat{R}\), a checkerboard coloured irregularly shaped region with ’holes’; (**b**) successful tiling of the target region \(\widehat{R}\) using 56 copies of an L-shaped trimino. The \(P_{1}^{+}\) variants are coloured light-blue corresponding to an optimal solution of the single parionino tiling subproblem. with parities \(\pm p_{1}=\pm 1\), all orientations permitted. The parity of \(\widehat{R}\) is \(p=+12\), thus, the only way to satisfy the parity equation (see Theorem 1) is to choose \(a_{1}^{+}=20\) and \(a_{1}^{-}=8\), i.e., we have a single pariamino tiling subproblem using 20 copies of \(P_{1}^{+}\) and 8 copies of \(P_{1}^{-}\). The ILP file was constructed using the program LPMAKE_PARIOMINOS_FIGUREE6. Solving this subproblem in CPLEY yielded 731,092 solutions with \((m,n,f)=(86,252,168)\) in 156.20 s, thus the potential speedup when using the colouring technique is about 1.1\(\times\).