# A New Algorithm Based on Colouring Arguments for Identifying Impossible Polyomino Tiling Problems
## 3 Parity Violations  
### A Sufficient Condition for a Non-Tileable Region  
We describe a simple sufficient condition for a tiling problem to have no solution based on the parity of the target region and the parities of the tiles.  
We attempt to tile a region \(R\) with parity \(p\) using \(F\) free polyominoes \(\{P_{i}\}_{i=1}^{F}\) with copies \(\{n_{i}\}_{i=1}^{F}\), \(n_{i}\geq 1\). Assume the polyominoes have parity values \(\{\pm p_{i}\}_{i=1}^{F}\) (if the parity value is zero then for ease of notation the parity is still represented as \(\pm p_{i}\)). Denote the multiset of all possible sums of \(N=\sum_{i=1}^{F}n_{i}\) parity values by \(\{s_{j}\}_{j=1}^{M}\), \(M\geq 1\). The following elementary result is key to the arguments that follow:  
Proposition 2: _A necessary (but not sufficient) condition for the polyominoes to tile a region \(R\) is that \(s_{j}=p\) for at least one \(j\in\{1,2,\ldots,M\}\)._  
Proof: Assume the polyominoes \(\{P_{i}\}_{i=1}^{N}\) tile the target region \(R\). For each polyomino \(P_{k}\) with \(b_{k}\) black cells and \(w_{k}\) white cells the parity is given by \(\pm p_{k}=b_{k}-w_{k}\) and thus there exists a \(j\in\{1,2,\ldots,M\}\) such that  
\[s_{j}=\sum_{k=1}^{N}(\pm p_{k})=\sum_{k=1}^{N}(b_{k}-w_{k})=\sum_{k=1}^{N}b_{k }-\sum_{k=1}^{N}w_{k}=b-w=p.\]  
When none of the possible parity sums equals the parity of the target region we call this a _parity violation_ which implies it is impossible for the given polyominoes to tile the target region.  
Example 1: _Consider the problem of tiling the target regions \(R\) in Figure 6 with three dominoes, both orientations \(\left\langle\raisebox{-0.0 pt}{\includegraphics[height=14.226378 pt]{fig:p_2\(1\)1_2\(2\)3_4\(1\)2_4\(2\)5_5\(6\)6\(7\)7  
Any rectangle tiled by the five free tetrominoes must have an area of \(20\) cells, and as the area is even the parity of the target region must be zero; see Proposition 1 (iii). From Figure 7 we see that the sum of parities of the five tetrominoes is given by \(s_{1}=+2\) or \(s_{2}=-2\), thus from Proposition 2 we conclude that the tetrominoes do not tile any rectangle. This result is proved in ([2], p. 17) using a similar checkerboard colouring argument to the one presented here, but without parity considerations.  
**Example 3**.: _Consider the problem of tiling any rectangle with the \(35\) free hexominoes [2]. Any rectangle tiled by these polyominoes must have an area of \(35\times 6=210\) cells, thus the parity of the target region is zero. Of the \(35\) hexominoes, \(11\) polyominoes have a parity of \(\pm 2\), while the remaining \(24\) polyominoes have a parity of zero. Observe that the sum of \(11\) numbers from the set \(\{-2,+2\}\) can never equal zero, thus application of Proposition 2 yields that the \(35\) free hexominoes can never tile a rectangle. This result is proved in ([2], p. 10) using a similar checkerboard colouring argument to the one presented here, but without parity considerations._  
**Example 4**.: _Is it possible for \(15\) T-shaped tetrominoes (see Figure 8b) to tile the checkerboard coloured region shown in Figure 8a? The target region is the \(5\)th polyomino in the 'diamond-shapes' family (see Appendix A), but with a square removed from the middle. Thus, the target region has area \(c_{5}-1=36+25-1=60\) and parity \(p_{5}+1=11+1=+12\). The parity values of the tetrominoes are \(\pm 2\). However, it is not possible for a one-dimensional walk along the integers with \(15\) steps from \(\{-2,+2\}\) to arrive at \(+12\). Thus, the answer is 'no'._  
These simple examples illustrate that when using a parity violation to prove a tiling problem has no solution we must solve a combinatorial problem. We need to consider all possible sums of the parities of the polyominoes and verify that none of them equals the parity of the region we wish to tile.