# A New Algorithm Based on Colouring Arguments for Identifying Impossible Polyomino Tiling Problems
## 6 Conclusions and Future Work  
The main contribution of our article is to make some classical colouring techniques in tiling theory algorithmic. Previous work in colouring theory for tiling was typically applied on a case-by-case basis, or used theoretical algebraic techniques. Our article provides a systematic mathematical treatment of checkerboard colouring arguments and leads to a new algorithm, implemented via a suite of MATLAB codes called POLYOMINO_PARITY (v2.0.0) [22]. For a given choice of target region and a set of polyominoes, with an unspecified number of copies of each polyomino, the algorithm presented in this article finds all associated parity violations. Each parity violation corresponds to an impossible tiling problem. The ideas presented in this article show promise in opening up new techniques for the analysis of polyomino tiling problems that benefit from the power of modern scientific computing. There are several possible lines of inquiry we could pursue for future work. For tiling problems where solutions are not excluded by parity arguments, backtrack algorithms are often used to find solutions if they exist [25; 26; 27; 28]. Such algorithms work by exploring a tree of possible polyomino placements. For each polyomino placement, the remaining untiled region and the remaining polyominoes define a new tiling sub-problem. The same parity arguments can be applied to each sub-problem to decide if that branch of the search tree is necessarily unsolvable. It would be interesting to explore by adding monitoring for parity violations to backtrack algorithms if there is a reduction in solve times for some problems. [PERSON] [25] conducted preliminary investigations along these lines using a modern backtrack algorithm called 'POLYCUBE', optimized in C++ (personal communication, 8 June 2021). Another promising line of inquiry that we are currently investigating is to use the colouring techniques presented in this article to formulate an improved tiling procedure  
Figure 10: Target regions and tilings for Example 7 (**a,b**), Example 8 (**c,d**), and Example 9 (**e,f**). for polyominoes. By combining the checkerboard colouring techniques with the linear programming approach presented in [24] we are able to improve the computational efficiency of tiling in many problems. This technique relies on the fact that checkerboard colouring can split large tiling problems into many smaller tiling subproblems that are embarrassingly parallel, and hence solvable via a 'divide-and-conquer' strategy. A famous open problem in the theory of polyominoes is to enumerate polyominoes as a function of area, and sometimes as a function of perimeter [29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40]. In the context of checkerboard colouring we ask how many distinct polyominoes there are with a given (fixed) area \(c=b+w\), where \(b\) and \(w\) denote the number of black and white squares, respectively. We introduce a (new) related open problem:  
**Problem 1**. : _Consider the set of checkerboard coloured polyominoes with \(b\) black squares and \(w\) white squares. Enumerate the number of distinct (free, one-sided, or fixed) polyominoes as a function of the (fixed) parity \(p=b-w\)._  
Even with the simpler situation of a fixed area, i.e., we are enumerating parity equivalent \(n\)-ominoes (see Section 2), this is a complicated combinatorial problem. Hopefully this question stimulates further research. While this article focuses on two-dimensional tiling problems on a square lattice, the arguments and techniques presented here are easily extended to tiling problems in higher dimensions, and to other lattice structures (e.g., polyiamonds, polyhexes, etc.). Conceptualization, M.R.G. and J.B.; methodology, M.R.G. and J.B.; software, J.B.; validation, M.R.G. and J.B.; formal analysis, M.R.G. ; writing--original draft preparation, M.R.G. ; writing--review and editing, M.R.G. and J.B.; funding acquisition, M.R.G. All authors have read and agreed to the published version of the manuscript.