## 1 Introduction  
### Background and Motivation  
A polyomino \(P_{i}\) is a set of edge-connected unit squares in the plane, which we assume is simply connected. We refer to the polyominoes of area \(n\) as \(n\)-ominoes and for \(n=1,2,\ldots,8\) are called monominoes, dominoes, triminoes, termininoes, pentominoes, hexominoes, heptominoes, and octoninoes, respectively. In this work, we focus on tiling finite regions of the plane \(R\) with copies of \(F\)_free_ polyominoes \(\{P_{i}\}_{i=1}^{F}\). Free polyominoes are the same if reflected ('flipped') or rotated, and thus correspond to a physical puzzle piece or tile. For example, there are exactly 12 free pentominoes, illustrated below:  
(1,0)(0  
We can rotate _one-sided_ polyominoes, but not reflect them, while _fixed_ polyominoes cannot be rotated or reflected. There is no known closed-form formula for enumerating the number of distinct polyominoes (free, one-sided, or fixed) as a function of area or perimeter [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12]. For tiling reasons, we can translate free, one-sided, and fixed polyominoes in a _target region_\(R\). We assume the target region is connected, but not necessarily simply connected, i.e., we let \(R\) have 'holes'. There are two basic tiling situations: tiling with copies of a single free polyomino, or tiling with two or more distinct free polyominoes (with or without copies). We refer to these cases as _monohedral_ and _multihedral_, respectively. For more background theory on polyominoes and tiling with polyominoes, we refer the reader to standard references (see e.g., [5; 7; 13; 14; 15; 16] and the citations there). There is also a large specialized literature on the many computational and theoretical aspects of tiling the plane with polyominoes [17; 18; 19; 20; 21; 22; 23], or tiling finite regions of the plane with polyominoes (e.g., [24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40]). Unless stated otherwise, in the rest of this article, we assume polyominoes are free. Tiling with polyominoes is an example of combinatorial optimization [41; 42]. The key challenge is to develop algorithms that solve large tiling problems in a reasonable amount of time [43]. The general problem of tiling finite regions of the plane with polyominoes is \(\mathcal{NP}\)-complete [42; 44; 45], and so the associated computational geometry problem rapidly becomes intractable for large instances. Thus, it is important to reduce algorithm complexity for tiling, and this area continues as a fruitful area of research. The method in this article for tiling relies on combining two different techniques, namely, integer linear programming (ILP) [46] and checkerboard colouring techniques [47]. We give a very simple tiling example to motivate our tiling strategy and leave the formal development of the method and definitions to Section 3. Although the two solutions are obvious, for the sake of introducing the colouring approach, we proceed as though the solution is unknown, to highlight the issues involved. Consider the problem of tiling the \(2\times 4\) rectangle, denoted \(R\), with two L-shaped tetrominoes \(\left\{\raisebox{-1.0 pt}{\includegraphics[]{figures/1.eps}}\right\}\), all orientations permitted. Initially, we review the basic ILP approach that was developed in [46] and then solve the same problem with the addition of colouring techniques. We introduce a variable \(y_{i}\in\{0,1\}\) for whether we use a particular placement of a tetromino ( coloured red) to tile the region, illustrated in Figure 1.  
In any tiling of \(R\), we must cover each of the eight cells exactly once, yielding the following system of eight linear equations in eight unknowns:  
Figure 1: Possible placements of a tetromino in \(R\) and the associated variables. \[ \begin{array}{ccccc}y_{1}&+y_{3}&+y_{7}&=1\\ &y_{2}+y_{3}+y_{4}&+y_{7}+y_{8}&=1\\ &&y_{3}+y_{4}+y_{5}&+y_{7}+y_{8}&=1\\ &&y_{4}&+y_{6}&+y_{8}&=1\\ y_{1}&+y_{5}&+y_{7}&=1\\ y_{1}+y_{2}&+y_{5}+y_{6}&+y_{8}&=1\\ y_{1}+y_{2}+y_{3}&+y_{5}+y_{6}&=1\\ y_{2}&+y_{4}&+y_{6}&=1\end{array}