## 1 Introduction
### Goals and Related Work  
The traditional approach to tiling finite regions of the plane with polyominoes employs backtracking, which is the default way in computer science for exploring the search tree of a combinatorial problem [48; 49; 50; 51; 52]. Although backtracking is quick for some problems, it only refines a 'brute-force' solution procedure for exhaustively finding all solutions to a combinatorial search problem. Another less commonly used 'brute-force' approach to tiling with polyominoes employs either evolutionary computation [26] or genetic algorithms [53]; however, such approaches are likely considerably less efficient than backtracking. The only other general-purpose algorithmic procedure to tiling finite regions of the plane with polyominoes that we are aware of uses ILP, first introduced in [46]. There are several potential advantages of an algebraic approach to tiling over the backtracking methods. In [46], the authors note that with ILP the \"the structure, combinatorial nature, and solvability of the model can be analyzed\". Finally, we mention there are many pure mathematical results for proving that a set of polyominoes tiles a region, for example, using the combinatorial group theory approach of [PERSON] [54; 55; 56]. However, these methods typically apply only to special cases and thus, we cannot make them algorithmic. It is interesting to note that the tiling problem, which is here regarded as an ILP instance, can also be considered a satisfiability problem (SAT) [57; 58; 59], for which there are a number of powerful solvers. Examples of suitable open-source SAT solvers include Lingeling; see [[http://fmvjku.at/lingeling/](http://fmvjku.at/lingeling/)]([http://fmvjku.at/lingeling/](http://fmvjku.at/lingeling/)) (accessed on 6 May 2022) and MapleSAT, see [[https://sites.google.com/a/gsd.uwaterloo.ca/maplesat/maplesat](https://sites.google.com/a/gsd.uwaterloo.ca/maplesat/maplesat)]([https://sites.google.com/a/gsd.uwaterloo.ca/maplesat/maplesat](https://sites.google.com/a/gsd.uwaterloo.ca/maplesat/maplesat)) (accessed on 6 May 2022). Unfortunately, however, the overhead of enforcing the conditions that we use each tile a fixed number of times is prohibitive. Further details are provided in Appendix A. The focus of the current article is to combine checkerboard colouring techniques adapted from [47] with a recently introduced ILP method [46] for tiling with polyominoes. The checkerboard colouring method [47] was originally used to identify large impossible tiling problems, i.e., the opposite of what we aim to do here. Our checkerboard colouring techniques often splits large tiling problems into smaller tiling subproblems, where each subproblem is represented as a separate ILP problem. Problems that are amenable to this approach are embarrassingly parallel. This article provides proof of concept of a parallelizable ILP approach for tiling finite regions of the plane with polyominoes. We construct the ILP formulations of the tiling problems in MATLAB and compute the numerical solutions using CPLEX, a high-performance optimization package. The primary goal is to analyze when this approach yields a potential parallel speedup. For tiling problems solved via a parallelizable ILP optimization technique, there are two basic aims: (i) find _a single_ tiling solution (i.e., an optimal solution), and (ii) find _all_ tiling solutions. In the former case, when we apply our checkerboard colouring techniques, we seek the subcase yielding an optimal solution computed in the least amount of time. In the latter case, it is the subcase that takes the longest time to compute all solutions that is of interest; if this takes less time to compute than for the full (uncoloured) problem, then we have a potential parallel speedup. The simple tiling examples discussed above raise many questions, namely the following:  
1. When do the checkerboard colouring techniques split the problem into multiple (\(\geq\)2) independently solvable subproblems? 2.