# A New Algorithm Based on Colouring Arguments for Identifying Impossible Polyomino Tiling Problems
## 4 Linear Diophantine Equation Approach  
In this section, we convert the combinatorial problem of finding parity violations into the problem of solving linear Diophantine equations. The theoretical results form the basis for a practical algorithm implemented in MATLAB for identifying all possible parity violations of a given tiling problem, presented in Section 5. Consider the problem of whether \(F\) free polyominoes \(\{P_{i}\}_{i=1}^{F}\) with areas \(c_{i}\) and \(n_{i}\) (\(n_{i}\geq 1\)) copies of each polyomino \(P_{i}\) are able to tile a target region \(R\) with area \(c\). The total number of polyominoes used is \(N:=\sum_{i=1}^{F}n_{i}\). If the number of copies of each polyomino is not specified then we have the following linear Diophantine equation in \(F\) unknowns \(\{n_{i}\}_{i=1}^{F}\) to solve for:\[c_{1}n_{1}+c_{2}n_{2}+\cdots+c_{F}n_{F}=c,\quad\text{for}\quad n_{i}\in\mathbb{N}, \quad i=1,\ldots,F. \tag{3}\]  
A well-known classical result (e.g., see (([21], p. 30)) is that a necessary condition for the existence of integer solutions (and hence also positive integer solutions) of (3) is  
\[\gcd(c_{1},c_{2},\ldots,c_{F})\ \mid\ c, \tag{4}\]  
where \(\gcd(c_{1},c_{2},\ldots,c_{F})\) denotes the greatest common divisor of the numbers \(c_{1},c_{2},\ldots,c_{F}\). Now denote the solutions of (3) by the set of \(F\)-tuples  
\[S_{c}:=\{(n_{1},n_{2},\ldots,n_{F})\ :\ n_{i}\in\mathbb{N}\}, \tag{5}\]  
which may be empty. The subscript \(c\) of \(S_{c}\) indicates that the solution set depends on \(c\) in (3). Assume the target region \(R\) has a fixed parity \(p\in\mathbb{N}\cup\{0\}\) and the polyominoes \(P_{i}\) have parities \(\pm p_{i}\), \(p_{i}\in\mathbb{N}\cup\{0\}\) and W.L.O.G. the first \(r\) polyominoes, \(0\leq r\leq F-1\) have zero parity. In the arguments below we will need the following simple lemma:  
Lemma 1: _Let \(\mathcal{O}\) and \(\mathcal{E}\) denote the set of odd and even integers, respectively. Then for all \(a_{i},b_{i},c_{i}\in\mathbb{Z}\)_  
\[\sum_{i=1}^{M}(a_{i}+b_{i})c_{i}\in\mathcal{O}\ \text{(resp. $\mathcal{E}$)} \iff\sum_{i=1}^{M}(a_{i}-b_{i})c_{i}\in\mathcal{O}\ \text{(resp. $\mathcal{E}$)}.\]  
Proof: Recall from the elementary properties of odd and even numbers that the sum of two numbers \(a+b\) is odd (resp. even) if and only if the difference \(a-b\) is odd (resp. even). After setting \(a:=\sum_{i=1}^{M}a_{i}c_{i}\) and \(b:=\sum_{i=1}^{M}b_{i}c_{i}\) the result follows. The following theorem is the theoretical basis of Algorithm 1 presented in Section 4:  
Theorem 2: _Let the variable \(a_{i}\in\mathbb{N}\cup\{0\}\) denote how many of the \(n_{i}\) elements drawn from \(\{-p_{i},+p_{i}\}\) are \(+p_{i}\), \(0\leq a_{i}\leq n_{i}\), \(i=r+1,r+2,\ldots,F\). A solution \((n_{1},n_{2},\ldots,n_{F})\) of the linear Diophantine Equation (3) (if it exists) yields a parity violation if and only if one of the following mutually exclusive conditions holds:_  
1. \(\gcd(p_{r+1},p_{r+2},\ldots,p_{F})\ \
ot|\ k\)_, where_ \[k:=(p+p_{r+1}n_{r+1}+p_{r+2}n_{r+2}+\cdots+p_{F}n_{F})/2\in\mathbb{Z}.\]
2. \(\gcd(p_{r+1},p_{r+2},\ldots,p_{F})\ |\ k\) _but there is no solution to the following linear Diophantine equation in_ \(F-r\) _unknowns_ \(\{a_{i}\}_{i=r+1}^{F}\)_:_ \[p_{r+1}a_{r+1}+p_{r+2}a_{r+2}+\cdots+p_{F}a_{F}=k.\]
3. _There exists one or more solutions to the linear Diophantine equation in (ii), but none of the solutions satisfy the bounds_ \[0\leq a_{i}\leq n_{i},\quad a_{i}\in\mathbb{N}\cup 0,\quad i=r+1,r+2,\ldots,F.\]  
Proof: To find possible parity violations we need an equation that matches the sum of the parities of the tiles to the parity of the target region. Our starting point is the parity problem of Section 3.2. As we have \(a_{i}\) choices for how many of the \(n_{i}\) elements drawn from \(\{-p_{i},+p_{i}\}\) are \(+p_{i}\), we must have \(n_{i}-a_{i}\) choices of \(-p_{i}\), \(0\leq a_{i}\leq n_{i}\), \(i=r+1,r+2,\ldots,F\) (recall, the parities of the first \(r\) polyominoes are zero).