# A New Algorithm Based on Colouring Arguments for Identifying Impossible Polyomino Tiling Problems
## 3 Parity Violations
### Combinatorial Considerations  
In the practical application of Proposition 2 to large tiling problems we must compute all possible parity sums for a given set of polyominoes, i.e.,:  
* find all possible sums \(\{s_{j}\}_{j=1}^{M}\) given by: \[\left\{ \begin{array}{c}n_{1}\text{ elements drawn from }\{-p_{1},+p_{1}\},\text{ with}\\ n_{2}\text{ elements drawn from }\{-p_{2},+p_{2}\},\text{ with}\\ \vdots\vdots\\ n_{F}\text{ elements drawn from }\{-p_{F},+p_{F}\},\end{array} \right.\] where \(n_{i}\in\mathbb{N}\) and \(p_{i},p\in\mathbb{N}\cup\{0\}\), for \(i=1,2,\ldots,F\). Figure 8: Tiling a square shaped region using \(15\) T-shaped tetrominoes: (**a**) \(p=+12\), (**b**) \(p_{5}=\pm 2\). With \(N\) polyominoes we have \(2^{N}\) different ways to sum the parity values, assuming the parities are distinct and non-zero. However, it is often the case that many of the polyominoes have the same parity value, or are zero, which reduces the number of possible sums of parities. We define the _parity problem_ as the decision problem of whether any of the parity sums equals \(p\). This problem is similar to the general subset sum problem, which is \(\mathcal{NP}\)-complete [19]. The tree diagram in Figure 9 illustrates the possible ways of adding five elements from \(\{-p,+p\}\) (here, the arrow \(\searrow\) denotes adding \(+p\) while the arrow \(\swarrow\) denotes adding \(-p\)). The following are some related results:  
**Proposition 3**. :
1. _All possible sums of_ \(n_{k}\) _elements drawn from_ \(\{-p_{k},+p_{k}\}\) _are given by_ \[s_{j}=p_{k}(n_{k}-2j),\quad n_{k}\geq 0,\quad j=0,1,\ldots,n_{k}.\]
2. _The number of sums we can form in the combinatorial problem_ \((P_{1})\) _is given by_ \[M=\prod_{k=1}^{F}(1+n_{k}).\]
3. _Consider a tiling problem using_ \(n_{k}\) _copies of each free polyomino_ \(P_{k}\) _for_ \(k=1,2,\ldots,F\)_, where each polyomino has_ \(z_{k}\) _parity equivalent polyominoes. If the tiling problem yields a parity violation then the number of equivalent parity violation problems is given by:_ \[\prod_{k=1}^{F}\binom{z_{k}+n_{k}-1}{n_{k}}.\]  
Proof. :
1. If the number of occurrences of \(-p_{k}\) in the sum is \(j,j\in\{0,1,\ldots,n_{k}\}\), then the number of occurrences of \(+p_{k}\) in the sum is \(n_{k}-j\), yielding the sums \[s_{j}=j(-p_{k})+(n_{k}-j)(+p_{k})=p_{k}(n_{k}-2j),\quad\text{for }j=0,1,\ldots,n_{k}.\]
2. From (i) we see that the total number of sums of \(n_{k}\) elements drawn from the set \(\{-p_{k},+p_{k}\}\) is given by \(1+n_{k}\). The result then follows if we apply the Fundamental Counting Principle over all sets for \(k=1,\ldots,F\). Figure 9: Possible ways of summing five elements from \(\{-p,+p\}\). 3. The number of combinations of \(z_{k}\) parity equivalent polyominoes taken \(n_{k}\) at a time with repetition is given by \( \begin{pmatrix}z_{k}+n_{k}-1\\ n_{k}\end{pmatrix} \) ([20], p. 36). Thus, applying the Fundamental Counting Principle again over all \(F\) equivalence classes yields the result. Proposition 3 (iii) is illustrated in the following example:  
**Example 5**. : _Consider the problem of tiling the \(8\times 8\) square with the following polyominoes_  
\[\left\{ \begin{array}{c}\includegraphics[width=142.26378 pt]{images/g1}, \includegraphics[width=142.26378 pt]{images/g2}, \includegraphics[width=142.26378 pt]{images/g3},\includegraphics[width=142.26378 pt]{images/g4} \end{array} \right\},\]  
_all orientations permitted, using \(n_{1}=3\), \(n_{2}=2\), and \(n_{3}=3\) copies, respectively. The target region has a parity of zero, and the total area of the tiles is \(3(4)+2(8)+3(12)=64\) as required. The polyominoes have parity values of \(0,\pm 4,\pm 6\), respectively, and it is easily verified that this problem yields a parity violation. We note that \(z_{1}=4\), \(z_{2}=3\), and \(z_{3}=5\) (see Figures 5 and 7).