# A New Algorithm Based on Colouring Arguments for Identifying Impossible Polyomino Tiling Problems
## 2 Preliminaries  
Consider a finite set of \(F\) free polyominoes ('tiles') in the lattice \(\mathbb{Z}^{2}\), denoted \(\{P_{i}\}_{i=1}^{F}\), \(F\geq 1\). We assume the polyominoes are simply-connected, i.e., have no 'holes'. The area of each polyomino \(P_{i}\) is denoted \(c_{i}\). Consider another arbitrary union of a finite number of edge-connected cells in the lattice \(\mathbb{Z}^{2}\) denoted \(R\) with area \(c\). We assume \(R\) is connected, but not necessarily simply-connected, thus the region \(R\) can have 'holes'. We attempt to tile the _target region_\(R\) with \(n_{i}\) (\(n_{i}\geq 1\)) copies of each free polyomino \(P_{i}\), \(i=1,\ldots,F\), without 'gaps' or tiles overlapping, i.e., we have an exact cover problem. Obviously a necessary condition for a solution to a tiling problem is that the sum of the areas of the tiles must equal the area of the target region, i.e., \(\sum_{i=1}^{F}c_{i}n_{i}=c\). Suppose we colour the cells of a polyomino, or the region we wish to tile, either black or white in such a way that each black cell is edge connected only to white cells and each white cell is edge connected only to black cells. We call this a _checkerboard colouring_. A checkerboard colouring is rigorously defined using modular arithmetic by identifying each black cell with the number \(1\) and each white cell with the number \(0\). If the centre of each cell of a region has coordinates \((i,j)\in\mathbb{Z}^{2}\) then a map \(f:\mathbb{Z}^{2}\mapsto\mathbb{Z}\) given by \(f(i,j)=i+j\) (mod \(2\)) defines a checkerboard colouring [17]. If we have \(f(i,j)=i+j+1\) (mod \(2\)) then we reverse the colouring of cells. See Figure 3 for an example (we colour the 'white' cells of a checkerboard coloured region light grey, to distinguish them from any holes in the region, which we colour white). We define the _parity_ (pl. _parities_) of a checkerboard coloured region as the number of black cells minus the number of white cells. We start each tiling problem by assigning the target region \(R\) a fixed checkerboard colouring with parity \(p\), \(p\in\mathbb{N}\cup\{0\}\). A polyomino placed in a checkerboard coloured region \(R\) acquires the colouring of the cells it covers. If the parity of a polyomino is non-zero, then it has two parity values \(\pm p_{i}\), \(p_{i}\in\mathbb{N}\), depending on its placement in \(R\). Rotating, reflecting or translating the polyomino in the region may reverse its parity. If a polyomino has zero parity then \(p_{i}=0\). If a polyomino \(P_{i}\) has parity \(+p_{i}\), then its parity becomes \(-p_{i}\) by reversing the colouring of cells (and vice versa). Consider two distinct polyominoes \(P_{1}\) and \(P_{2}\), with the same area \(n\) and parities \(\pm p_{1}\) and \(\pm p_{2}\), respectively. Then \(P_{1}\) and \(P_{2}\) are _parity equivalent \(n\)-ominoes_ if \(p_{1}=p_{2}\). Clearly, if \(P_{1}\) and \(P_{2}\) are parity equivalent \(n\)-ominoes then \(P_{1}\) can be transformed into \(P_{2}\) (and vice versa) by rearranging the black and white cells. Parity equivalence of \(n\)-ominoes is an equivalence relation. An example of parity equivalent 8-ominoes is illustrated in Figure 4.  
Consider a polyomino \(P_{i}\) with \(b_{i}\) black cells and \(w_{i}\) white cells. We state the following simple results without proof, as they are immediate consequences of the equations for area (\(c_{i}=b_{i}+w_{i}\)) and parity (\(p_{i}=b_{i}-w_{i}\)) of a polyomino (or region) and elementary mathematical induction. Figure 3: Defining a checkerboard colouring. **Proposition 1**. :
1. _Parity equivalent_ \(n\)_-oninoes have the same number of black squares and the same number of white squares._
2. _Consider the set of all free polyominoes. The parities of polyominoes in this set take on all possible values in_ \(\mathbb{Z}\)_._
3. _Consider an_ \(m\times n\) _rectangle in_ \(\mathbb{Z}^{2}\)_. If_ \(mn\) _is even the parity of the rectangle is_ \(0\)_. If_ \(mn\) _is odd the parity is_ \(\pm 1\)_._
4.