## 6 Numerical Examples
### Tiling Examples Where All Solutions Are Sought
#### 6.2.2 Case 2  
We give two examples of the monohedral polyomino type, where the application of colouring techniques splits the full (uncoloured) polyomino tiling problem into multiple pariomino tiling subproblems, with no reduction in complexity. **Example 2** (*). : _Find all ways of tiling the 18 \(\times\) 24 rectangle with_  
_all orientations permitted. The area of \(R\) is 432, so we need 72 copies of the hexomino. The associated ILP file, constructed with the program LPMAKE_POLYORINUOES_FIGURE3, has \(n=2816\) unknowns, \(m=432\) constraints, and \(f=2385\) free variables. CPLEX found 414 solutions in \(14.22\) s._  
_Using colouring techniques, we wish to tile the checkerboard coloured region \(\tilde{R}\) shown in Figure 14 using 72 pariominoes from the set_  
_all orientations permitted._  
_As the hexomino and \(R\) have zero parity and \(P_{1}^{+}\
eq P_{1}^{-}\) we automatically obtain 73 tiling subproblems to consider with \(a_{1}^{+}\) and \(a_{1}^{-}=72-n_{1}\) copies of \(P_{1}^{+}\) and \(P_{1}^{-}\) respectively, given by  
Figure 13: Target region and a tiling solution for Example 1: (**a**) The target region \(\tilde{R}\), a checkerboard coloured 9-by-9 single-notched square; (**b**) Successful tiling of the target region \(\tilde{R}\) using 20 copies of an L-shaped tetromino. The \(P_{1}^{+}\) variants are coloured light-blue and the \(P_{1}^{-}\) variants coloured dark-blue corresponding to an optimal solution of the subproblem with \((a_{1}^{+},a_{1}^{-})=(4,16)\) (see Table 1). \((a_{1}^{+},a_{1}^{-})\) for \(a_{1}^{+}=0,1,\ldots,72\). Solving the subproblems in CPLEX yielded the data for the 23 feasible solutions shown in Table 2.  
A single (optimal) tiling solution corresponding to the subproblem with \((a_{1}^{+},a_{1}^{-})=(16,56)\) is shown in Figure 14b. The program LPMAKE_PARIIONIOES_FIGURE3 was used to construct the ILP file in this case. (Similar programs were used to construct the ILP files for the other cases.) The subproblems with either \(a_{1}^{+}=0\) and \(a_{1}^{-}=72\), or \(a_{1}^{+}=72\) and \(a_{1}^{-}=0\), yielded \((m,n,f)=(432,1408,978)\). All other subproblems yielded \((m,n,f)=(434,2816,2384)\). The maximum runtime for the infeasible solutions was 6.3 s. The subproblem with the maximum runtime of 15.30 s yielded 94 solutions, which is an increase in the runtime of approximately 7.60% compared to the full (uncoloured) tiling problem, i.e., no potential speedup was observed. \begin{table}
\begin{tabular}{c c c c c c c c c c c c} \hline \hline \(a_{1}^{+}\) & 16 & 26 & 27 & 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 \\ \hline \(a_{1}^{-}\) & 56 & 46 & 45 & 44 & 43 & 42 & 41 & 40 & 39 & 38 & 37 & 36 \\ \hline \# solns. & 1 & 4 & 2 & 4 & 6 & 9 & 12 & 31 & 26 & 51 & 14 & 94 \\ \hline \
\begin{tabular}{c} runtime \\ (s) \\ \end{tabular} & 2.2 & 8.7 & 8.5 & 10.2 & 8.8 & 10.1 & 9.8 & 13.3 & 9.6 & 11.0 & 9.9 & 15.3 \\ \hline \(a_{1}^{+}\) & 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 & 46 & 56 & - \\ \hline \(a_{1}^{-}\) & 35 & 34 & 33 & 32 & 31 & 30 & 29 & 28 & 27 & 26 & 16 & - \\ \hline \# solns. & 14 & 51 & 26 & 31 & 12 & 9 & 6 & 4 & 2 & 4 & 1 & - \\ \hline
\begin{tabular}{c} runtime \\ (s) \\ \end{tabular} & 12.8 & 12.6 & 10.6 & 12.6 & 12 & 10.7 & 8 & 8.8 & 7.6 & 8.1 & 3.7 & - \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Number of tiling solutions (# solns.) and runtimes in seconds for CPLEX to find the feasible solutions of the parionimo tiling problem in Example 2. Figure 14: Target region and a tiling solution for Example 2: (**a**) the target region \(\widehat{R}\), a checkerboard coloured \(18\times 24\) rectangle; (**b**) successful tiling of the target region \(\widehat{R}\) using 72 copies of a hexomino. The \(P_{1}^{+}\) variants are coloured light-blue and the \(P_{1}^{-}\) variants coloured dark-blue corresponding to the optimal solution of the subproblem with \((a_{1}^{+},a_{1}^{-})=(16,56)\) (see Table 2). **Example 3** (\"). : _Find all ways of tiling the irregularly shaped region_  
_all orientations permitted.