# A New Algorithm Based on Colouring Arguments for Identifying Impossible Polyomino Tiling Problems
## 2 Preliminaries
_Consider a polyomino_ \(P_{i}\) _with area_ \(c_{i}\) _and parity_ \(\pm p_{i}\)_. Then_ \(c_{i}\) _is odd (resp. even) if and only if_ \(\pm p_{i}\) _is odd (resp. even) (we avoid using the term 'parity' here in the usual sense to avoid confusion with its alternate definition in this article)._
5. _Let the number of black cells and white cells of a checkerboard coloured polyomino_ \(P_{i}\) _with area_ \(c_{i}\) _be_ \(b_{i}\) _and_ \(w_{i}\)_, respectively. If the parity of_ \(P_{i}\) _is_ \(\pm p_{i}\)_, then_ \(b_{i}=(c_{i}\pm p_{i})/2\)_, and_ \(w_{i}=(c_{i}\mp p_{i})/2\)_._  
As we shall see in later sections, (iii) is useful when we consider the problem of fitting a given set of polyominoes into a rectangle. Additional results for more general polyomino constructions are given in Appendix A, where we give the explicit relationships between area and parity. The results follow from elementary results for sequences and series and mathematical induction. Consider the sequence of free polyomino constructions shown in Figure 5. Starting with a black square, at each stage we add the minimum number of black and white squares to increase the parity by exactly one unit. (If necessary, we allow a re-arrangement of the squares to create all possible parity equivalent \(n\)-ominoes at each level, as is the case with the 2 nd construction for \(p=+6\)). From the figure we see that we must initially add a straight trimino \(\blacksquare\) or an L-shaped trimino \(\blacksquare\) (all orientations permitted) and then in the next step a black square, and repeat, yielding the parity sequence \(\{+1,+2,+3,\ldots\}\). At each level in the construction the shapes are parity equivalent \(n\)-ominoes. The following result clarifies the relationship between the areas and the parities of the polyominoes constructed in Figure 5.  
**Theorem 1**. : _Consider the sequence of polyominoes constructed in Figure 5 together with a domino. If the areas of the polyominoes are denoted by \(c_{p}\) with parities \(p\in\mathbb{Z}\), then_  
\[c_{p}= \begin{cases}2|p|-\operatorname{mod}(p,2)&\text{if }|p|\in\mathbb{N},\\ 2&\text{if }p=0.\end{cases}  \tag{1}\]  
_Furthermore, every polyomino in the sequence has minimal area with respect to its parity, or equivalently, maximal parity with respect to its area._  
Figure 4: Parity equivalent 8-ominoes: (**a**) \(P_{1}\), (**b**) \(P_{2}\). Figure 5: Illustration of Proposition 1 (ii) and Theorem 1. Starting with the top black square with parity \(p=+1\), as we descend each level of the tree the parity increases by \(+1\). At each level the shapes are parity equivalent \(n\)-ominoes, and have minimal area with respect to their parity. Cells with a red border indicate which cells were added to the polyomino in the previous level to construct the corresponding polyomino at the current level. Proof. : We assume throughout the proof that \(p>0\). Similar arguments apply for the case \(p<0\) and the result is clearly true for \(p=0\) (the case with \(p=0\) corresponds to a domino with parity zero). We use induction on \(p\). The result is clearly true for \(p=1\). Assume the result is true for \(p\), then we have two cases to consider. If \(p\) is even, then \(c_{p}=2p-\mathrm{mod}(p,2)=2p\). By construction, we get the next polyomino in the sequence with a parity of \(p+1\) by adding a single black square, yielding an area of \(2p+1=2(p+1)-1=2(p+1)-\mathrm{mod}(p+1,2)\) as \(p+1\) is odd. If \(p\) is odd, then \(c_{p}=2p-\mathrm{mod}(p,2)=2p-1\). By construction we get the next polyomino in the sequence with a parity of \(p+1\) by adding two black squares and one white square. So the area becomes \(c_{p}=2p-1+3=2(p+1)=2(p+1)-\mathrm{mod}(p+1,2)\) as \(p+1\) is even. At each stage of the construction procedure in Figure 5 we add the least number of black and white squares to increase the parity by one unit. If the parity is odd, no white squares are accessible, so we must add either an L-shaped trimino or a straight trimino.