# A New Algorithm Based on Colouring Arguments for Identifying Impossible Polyomino Tiling Problems  
[PERSON]  
1 Department of Mathematics & Statistics, University of Guelph, Guelph, ON 1 NG 2W1, Canada 1+  
Footnote †: This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ([[https://creativecommons.org/licenses/py/4.0/](https://creativecommons.org/licenses/py/4.0/)]([https://creativecommons.org/licenses/py/4.0/](https://creativecommons.org/licenses/py/4.0/))). Footnote †: This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ([[https://creativecommons.org/licenses/py/4.0/0/](https://creativecommons.org/licenses/py/4.0/0/)]([https://creativecommons.org/licenses/py/4.0/0/](https://creativecommons.org/licenses/py/4.0/0/))). Footnote †: This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ([[https://creativecommons.org/licenses/py/4.0/](https://creativecommons.org/licenses/py/4.0/)]([https://creativecommons.org/licenses/py/4.0/](https://creativecommons.org/licenses/py/4.0/))). Footnote †: This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ([[https://creativecommons.org/licenses/py/4](https://creativecommons.org/licenses/py/4)]([https://creativecommons.org/licenses/py/4](https://creativecommons.org/licenses/py/4)). The focus of this article is the decision problem of whether or not a given set of polyominoes tiles a finite region of the plane called the 'target region'. The general decision problem is \(\mathcal{NP}\)-complete [12] and so large problems rapidly become intractable. To help tackle this problem we apply 'checkerboard' colouring arguments to the polyominoes and target region, which in certain cases prove the polyominoes do not tile the region. To this end we consider the 'parity' of the checkerboard coloured polyominoes or target region, which for a given region is the difference between the number of black squares and the number of white squares. Although checkerboard colouring arguments are common in the literature, a systematic mathematical treatment _without_ using a more theoretical algebraic approach is lacking. The colouring arguments we use yield sufficient, but not necessary conditions for a tiling problem to have no solution, and are generally weaker than the more theoretical tools of Combinatorial Group theory [10; 11; 13; 14; 15]. Our main contribution is to tackle this problem algorithmically using colouring arguments, which leads to an efficient numerical method implemented in MATLAB. In addition to developing a systematic method for finding impossible tiling problems we also prove some interesting associated results about polyominoes and their parity values. Our checkerboard colouring technique identifies impossible tiling problems using polyominoes of arbitrary shape. In graph theory, there is a well-known related approach, which is limited to tiling with dominoes. In that case, black and white squares of the checkerboard coloured region to be tiled are represented by black and white vertices of a graph. A link is made between any two adjacent squares of the region. Then [PERSON]'s marriage theorem gives necessary and sufficient conditions for the existence of a tiling of the region using dominoes, requiring the construction and examination of every possible subset of the white vertices [16]. A checkerboard colouring is not the only way two colours can help prove a tiling problem has no solution. Other colouring schemes have been successfully used in specific cases (see Figure 2 for colouring schemes applied to an \(8\times 8\) square [2; 8]). However, using two colours, it is only a checkerboard colouring that seems to have wide applicability and hence is amenable to a systematic mathematical description. The rest of this article has the following structure.