## 1 Introduction
### Background and Motivation
 \tag{1}\]  
Observe that if we sum these equations, we obtain \(4\sum_{i=1}^{8}y_{i}=8\implies\sum_{i=1}^{8}y_{i}=2\), which implies that we must use exactly two polyominoes to tile the region. Thus, this constraint is automatically incorporated into the system. A tiling of the region \(R\) corresponds to a binary solution of this system. However, solutions of the extended system where \(y_{i}\in\mathbb{R}\) do not necessarily correspond to a tiling as solutions may also be rational. The reduced row echelon form of this system has seven non-zero rows and eight variables, thus one free variable. Solving this system, using a high-performance optimization package, such as CPLEX, Gurobi, or SCIP, yields two binary solutions: \(y_{1}=y_{4}=1\) with all other variables equal to zero; and \(y_{7}=y_{6}=1\) with all other variables equal to zero, illustrated in Figure 2. These tilings are trivial variations of each other, obtained by reflecting the entire board horizontally. We now solve this tiling problem by including checkerboard colouring techniques. The starting point of the approach is to give the target region \(R\) a fixed checkerboard colouring, illustrated in Figure 3. There is another checkerboard colouring for this region obtained by swapping the black and white squares, but the particular choice of colouring does not matter to the solution procedure. We also assume that the tetrominoes used to tile \(R\) have a checkerboard colouring, and the two distinct variants are  
\[ \begin{array}{c}\Big{\{}\includegraphics[width=142.26378 pt]{.eps}, \includegraphics[width=142.26378 pt]{.eps}\end{array} \end{array},\]  
where all orientations are permitted. Not only must the coloured polyominoes fit in the target region, but the colouring of the cells covered must correspond to the colouring of the cells in the tiles. Using two coloured tetrominoes from this set yields three subcases: tiling with two of the first coloured tetromino; tiling with one coloured tetromino of each variant; or tiling with two of the second coloured tetromino. We focus on the first subcase. We introduce a variable \(x_{i}\in\{0,1\}\) for whether a particular placement of a coloured tetromino of the first kind in this set is used to tile the region, illustrated in Figure 4.  
Figure 3: Checkerboard coloured region to be tiled with coloured tetrominoes. Figure 2: The two possible ways to tile \(R\): (**a**) first tiling solution; (**b**) second tiling solution. In any tiling of the checkerboard coloured region in Figure 3, each of the eight cells must be covered exactly once, yielding the following system of eight linear equations in four unknowns:  
\[ \begin{split} x_{1}&=1\\ x_{2}&+x_{4}=1\\ x_{2}+x_{3}+x_{4}&=1\\ x_{2}&+x_{4}=1\\ x_{1}&+x_{3}&=1\\ x_{1}&+x_{3}+x_{4}=1\\ x_{1}&+x_{3}&=1\\ x_{2}&=1\end{split}  \tag{2}\]  
If we sum these equations, we obtain \(4\sum_{i=1}^{4}x_{i}=8\implies\sum_{i=1}^{4}x_{i}=2\), which again reflects the fact that we must use exactly two coloured polyominoes of the first variant to tile the region. Thus, this constraint is also automatically incorporated into the system. However, unlike in the previous example, this system has full rank and is thus trivially solved to yield \(x_{1}=x_{2}=1\) with all other variables equal to zero, i.e., we have the first tiling solution illustrated in Figure 2. The third subcase is similar, yielding the second tiling solution illustrated in Figure 2.  
In the second subcase, unlike the first and third subcases, we are tiling with two different coloured polyominoes. So each coloured polyomino has an associated constraint equation that must be incorporated into the linear system (i.e., unlike the case with a single polyomino or coloured polyomino, they are not both automatically incorporated into the linear system). This is like the multihedral case for tiling with polyominoes [46], which we review in the next section.