## 6 Numerical Examples
### Tiling Examples Where All Solutions Are Sought
#### 6.2.5 Case 5
CPLEX found 337,680 solutions in 225.06 s._  
_Using colouring techniques we wish to tile the checkerboard coloured region \(\widehat{R}\) shown in Figure 19(a) using 34 parjointnoes from the set_  
\[\{P_{1}^{+},P_{1}^{-}\}=\Bigg{\{}\]  
_,_  
Figure 19: Target region and a tiling solution for Example 7: (**a**) The target region \(\widehat{R}\), a checkerboard coloured jagged-square shaped region with a single ‘hole’ in the middle. (**b**) Successful tiling of the target region \(\widehat{R}\) using 33 copies of an L-shaped tritino and 9 copies of the cross-shaped pentomino. The optimal solution corresponds to the fourth pariolomino tiling subproblem in Table 3 where we use 24 copies of \(P_{1}^{+}\), 9 copies of \(P_{1}^{-}\), 6 copies of \(P_{2}^{+}\), and 3 copies of \(P_{2}^{-}\). The pariolominoes \(P_{1}^{+},P_{1}^{-},P_{2}^{+}\) and \(P_{2}^{-}\) are coloured dark blue, light blue, dark red, and light red, respectively. _with parities \(\pm p_{1}=\pm 2\), and 5 parioninoes from the set_  
\[\{P_{2}^{+},P_{2}^{-}\}=\left\{ \begin{array}{c}\includegraphics[width=142.26378 pt]{ 142.eps},\includegraphics[width=142.26378 pt]{ 214.eps},\includegraphics[width=142.26378 pt]{ 221.eps}\end{array} \right\},\]  
_with parities \(\pm p_{2}=\pm 2\), and 3 parioninoes from the set_  
\[\{P_{3}^{+},P_{3}^{-}\}=\left\{ \begin{array}{c}\includegraphics[width=142.26378 pt]{ 142.eps},\includegraphics[width=142.26378 pt]{ 214.eps},\includegraphics[width=142.26378 pt]{ 214.eps}\end{array} \right\},\]  
_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_{3}a_{3}^{+}=(p+p_{1}n_{1}+p_{2}n_{2}+p_{3}n_{ 3})/2,\quad 0\leq a_{i}^{+}\leq n_{i},\quad i=1,2,3.\]  
_After noting that \(p=+19\) we obtain the linear Diophantine equation_  
\[2a_{1}^{+}+2a_{2}^{+}+3a_{3}^{+}=53,\quad 0\leq a_{1}^{+}\leq 34,\quad 0\leq a_{2 }^{+}\leq 5,\quad 0\leq a_{3}^{+}\leq 3.\]  
_The MATLAB program DIOPANTINE_ND_NONNEGATIVE_BOUNDED was used to solve this equation yielding 12 parionino tiling subproblems, solved in CPLEI to give the data in Table 4 for the number of parionino tiling solutions and CPLEI runtimes._  
_The sixth subproblem took the longest to solve (72.09 s), and thus the potential speedup when using the colouring technique is about \(3.1\times\). We found an optimal solution using CPLEI for the first subproblem, i.e., using \(17\) copies of \(P_{1}^{+}\), \(17\) copies of \(P_{1}^{-}\), \(5\) copies of \(P_{2}^{+}\), and \(3\) copies of \(P_{3}^{+}\) (see Figure 1(b)). We constructed the ILP file in this case using the program LPMAKE_PARIOMINOES_FIGURE9 (similar programs were used to construct the ILP files for the other cases)._  
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \(a_{1}^{+}\) & \(a_{2}^{+}\) & \(a_{3}^{+}\) & \(n\) & \(m\) & \(f\) & \# Solns. & Runtime (s) \\ \hline \(17\) & \(5\) & \(3\)  
**Example 9**. : _Find all ways of tiling the region_  
_with_  
_all orientations permitted. The area of \(R\) is 80, which we aim to tile with \(n_{1}=26\) copies of the domino, \(n_{2}=3\) copies of the P-shaped pentomino, \(n_{3}=1\) copies of the cross-shaped pentomino, and \(n_{4}=1\) copies of the octonino. The associated ILP file, constructed with the program LPMAKE_POLYIONIONIES_FIGURE10, has \(n=444\) unknowns, \(m=84\) constraints, and \(f=361\) free variables. CPLEX found 105,344 solutions in 16.83 s._  
_Using colouring techniques, we wish to tile the checkerboard coloured region \(\widehat{R}\) shown in Figure 11(a) using 26 parioninoes from the set_  
\[\{P_{1}^{+}\}=\bigg{\{}\ \raisebox{-1.29 pt}{\includegraphics[]{figures/11.eps}},\]  
Figure 20: Target region and a tiling solution for Example 8: (**a**) the target region \(\widehat{R}\), a checkerboard coloured diamond-shaped region; (**b**) successful tiling of the target region \(\widehat{R}\) using 34 copies of a T-shaped trimino, 5 copies of the Y-shaped hexomino, and 3 copies of the cross-shaped pentomino.