## 6 Numerical Examples
### Tiling Examples Where All Solutions Are Sought
#### 6.2.5 Case 5  
We give four examples of the multihedral type, where the application of colouring techniques splits the full (uncoloured) polyomino tiling problem into multiple parionino tiling subproblems, with a reduction in complexity. **Example 7**. : _Find all ways of tiling the jagged-square shaped region with a single 'hole' in the middle_  
_all orientations permitted. The area of \(R\) is 144, which we aim to tile using \(n_{1}=33\) copies of an \(L\)-shaped trimino and \(n_{2}=9\) copies of the cross-shaped pentomino. The associated ILP file, constructed  
Figure 18: Target region and a tiling solution for Example 6: (**a**) the target region \(\widehat{R}\), a \(16\times 18\) rectangle; (**b**) successful tiling of the target region \(\widehat{R}\) using 48 parioninoes \(P_{1}^{+}\) (\(=P_{1}^{-}\)), coloured light-blue, corresponding to an optimal solution of the single parionino tiling subproblem. with the program LPMAKE_POLYOMINOES_FIGUREE8, has \(n=528\) unknowns, \(m=146\) constraints, and \(f=383\) free variables. _CPLEX[found 731,092 solutions in 165.78 s._  
_Using colouring techniques, we wish to tile the checkerboard coloured region \(\widehat{R}\) shown in Figure 19a using 33 parioninoes from the set_  
\[\{P_{1}^{+},P_{1}^{-}\}=\Bigg{\{}\]  
_with parities \(\pm p_{1}=\pm 1\), and 9 parioninoes from the set_  
\[\{P_{2}^{+},P_{2}^{-}\}=\Bigg{\{}\]  
_with parities \(\pm p_{2}=\pm 3\), all orientations permitted. The parity equation (see Theorem 1) is given by_  
\[p_{1}a_{1}^{+}+p_{2}a_{2}^{+}=(p+p_{1}n_{1}+p_{2}n_{2})/2,\quad 0\leq a_{i}^{+} \leq n_{i},\quad i=1,2.\]  
_After noting that \(p=+24\) we obtain the linear Diophantine equation_  
\[a_{1}^{+}+3a_{2}^{+}=42,\quad 0\leq a_{1}^{+}\leq 33,\quad 0\leq a_{2}^{+}\leq 9.\]  
_The MATLAB program DIOPANTINE_ND_NONEGATIVE_BOUNDED was used to solve this equation yielding seven parionino tiling subproblems, solved in _CPLEX to give the data in Table 3 for the number of parionino tiling solutions (# solns.) and _CPLEX tuttimes (sec)_. _The fifth subproblem took the longest to solve (106.42 s), thus the potential speedup when using the colouring technique is about \(1.6\times\). We found an optimal solution using _CPLEX for the fourth subproblem, i.e., using 24 copies of \(P_{1}^{+}\), 9 copies of \(P_{1}^{-}\), 6 copies of \(P_{2}^{+}\), and 3 copies of \(P_{2}^{-}\) (see Figure 19b). We constructed the ILP file in this case, using the program LPMAKE_PARIOMINOES_FIGUREE8 (similar programs were used to construct the ILP files for the other cases). \begin{table}
\begin{tabular}{c c c c c c c} \hline \(\mathbf{a_{1}^{+}}\) & \(\mathbf{a_{2}^{+}}\) & \(\mathbf{n}\) & \(\mathbf{m}\) & \(\mathbf{f}\) & \# Solns. & Runtime (s) \\ \hline
15 & 9 & 492 & 147 & 347 & - & 0.00 \\ \hline
18 & 8 & 528 & 148 & 382 & - & 0.04 \\ \hline
21 & 7 & 528 & 148 & 382 & - & 0.04 \\ \hline
24 & 6 & 528 & 148 & 382 & 62,960 & 15.21 \\ \hline
27 & 5 & 528 & 148 & 382 & 339,224 & 106.42 \\ \hline
30 & 4 & 528 & 148 & 382 & 16,256 & 2.84 \\ \hline
33 & 3 & 336 & 147 & 191 & - & 0.10 \\ \hline \end{tabular}
\end{table} 
Table 3: Number of tiling solutions (# solns.) and runtimes in seconds for _CPLEX_ to solve the seven parionino tiling subproblems in Example 7. **Example 8**. : _Find all ways of tiling the diamond-shaped region_  
\[R=\]  
_with_  
\[\{P_{1},P_{2},P_{3}\}=\Bigg{\{}\]  
_all orientations permitted. The area of \(R\) is 181, which we aim to tile using \(n_{1}=34\) copies of the T-shaped tritinino, \(n_{2}=5\) copies of Y-shaped hexomino, and \(n_{3}=3\) copies of the cross-shaped pentomino. The ILP file, constructed with the program LPMAKE_POLYONINOES_FIGURE9, has \(n=1685\) unknowns, \(m=184\) constraints, and \(f=1502\) free variables.