# A New Algorithm Based on Colouring Arguments for Identifying Impossible Polyomino Tiling Problems
## 5 Numerical Results  
In this section, we illustrate the theoretical approach for finding large impossible tiling problems with an efficient algorithm implemented in MATLAB.  
The open-source MATLAB (R2021b) programs used in this section are freely available in a repository, POLYOMINO_PARITY (v2.0.0) [22], and run on a Mac Pro (OS X 12.0.1) with 32 GB of memory and a 3.5 GHz 6-core Intel Xeon E5. We describe an algorithm based on Theorem 2 guaranteed to find all possible parity violations of a given tiling problem. To this end we must solve linear Diophantine equations in \(n\) variables \(\sum_{i=1}^{n}a_{i}x_{i}=b\), where the coefficients \(a_{i}\) and the right hand side value \(b\) are strictly positive integers. We wish to find all solutions \(x_{i}\) which are either nonnegative or strictly positive integers. Under the assumptions on \(a\) and \(b\), there are only a finite number of nonnegative or strictly positive integer solutions. We constructed the MATLAB functions DIOPHANTINE_ND_NONNEGATIVE and DIOPHANTINE_ND_POSITIVE with the syntax  
```
x = Diophantine_nd_nonnegative(a,b) x = Diophantine_nd_positive(a,b)
```  
which accept the coefficient \(n\)-vector a and right hand side b of a Diophantine equation, and return the set of solutions in an \(n\times k\) array x. Further details are given in Appendix B.  
Our starting point is a given set of \(F\) free polyominoes \(\{P_{i}\}_{i=1}^{F}\) with areas \(\{c_{i}\}_{i=1}^{F}\). The numbers of copies of the free polyominoes \(\{n_{i}\}_{i=1}^{F}\) is initially left unspecified. Once we have chosen a target region (e.g., from the families of polyominoes in Appendix A) we use Algorithm 1 implemented in MATLAB using the function PV_SEARCH with the syntax [ S1, S2 ] = pv_search ( par, ord, p, c ), which accepts the positive (or zero) parities of the polyominoes par, the areas of the polyominoes ord, and the parity p and area c of the target region. PV_SEARCH returns S1, the solutions to the area equation yielding trivial parity violations and S2, the solutions to the area equation yielding non-trivial parity violation.  
We illustrate this algorithm with several examples. In each problem we use PV_SEARCH to find all possible parity violations. In the first three examples we also use the open-source MATLAB programs, POLYOMINOES (v2.0.0) [23] (described in [24]), to yield successful tiling of the target regions concerned, However, there were many possible solutions and we made no attempt to enumerate them all, even for a particular choice of \(\{n_{i}\}_{i=1}^{F}\).  
We consider the problem of tiling the checkerboard coloured region shown in Figure 9(a) with copies of  
\[\left\{\begin{array}{c}\includegraphics[width=142.375 pt]{figs/2011-  
_With the particular choice of \((n_{1},n_{2},n_{3},n_{4})=(32,22,8,6)\) the polyominoes tile the target region (see Figure 10d)._  
**Example 9**.: _We consider the problem of tiling the checkerboard coloured region shown in Figure 10e with copies of_  
\[\left\{\begin{array}{c}\includegraphics[]{c}\includegraphics[]{c} \includegraphics[]{c},\includegraphics[]{c},\includegraphics[]{c}, \includegraphics[]{c},\includegraphics[]{c},\includegraphics[]{c}, \includegraphics[]{c},\includegraphics[]{c},\includegraphics[]{c},\includegraphics[]{c} \\ \includegraphics[]{c}.\end{array}\right.\]  
_We note that these tiles have parities \(\{0,0,\pm 2,\pm 1,\pm 8\}\) and areas \(\{2,4,4,5,18\}\), respectively. The target region (see Appendix A) has an area of \(264\) and a parity value of zero. Solving the linear Diophantine equation \(2n_{1}+4n_{2}+4n_{3}+5n_{4}+18n_{5}=264\) yields \(51,923\) solutions. PV_SEARCH found in \(12.91\)\(s\) that \(609\) of these solutions yielded parity violations (see Table 3 for the ten solutions with \(n_{1}=36\)):_  
_With the particular choice of \((n_{1},n_{2},n_{3},n_{4},n_{5})=(36,2,3,2,9)\) the polyominoes tile the target region (see Figure 10f)._