## 4 A Splitting Method Using Parity Constraints  
In [47], the authors used constraints on the parity values of the tiles to identify impossible tiling problems. We adapt these techniques here to split large tiling problems into many subproblems that admit a parallel solution strategy. We attempt to tile a region \(R\) with parity \(p\) using \(F\) free polyominoes \(\{P_{i}\}_{i=1}^{F}\) with copies \(\{n_{i}\}_{i=1}^{F}\), \(n_{i}\geq 1\). Assume the polyominoes have parity values \(\{\pm p_{i}\}_{i=1}^{F}\) (if the parity value is zero then for ease of notation, we still represent the parity as \(\mp p_{i}\)). Denote the multiset of all possible sums of \(N=\sum_{i=1}^{F}n_{i}\) parity values by \(\{S_{j}\}_{j=1}^{\mathcal{T}}\), \(\mathcal{T}\geq 1\), namely, all possible sums of  
\[\left\{ \begin{array}{rl}&n_{1}\text{ elements drawn from }\{-p_{1},+p_{1}\}, \text{ with}\\ &n_{2}\text{ elements drawn from }\{-p_{2},+p_{2}\},\text{ with}\\ &\vdots\\ &n_{F}\text{ elements drawn from }\{-p_{F},+p_{F}\},\end{array} \right. \tag{6}\]  
where \(n_{i}\in\mathbb{N}\) and \(p_{i},p\in\mathbb{N}\cup\{0\}\), for \(i=1\ldots F\). It is easy to prove the combinatorial result that [47]:  
Proposition 1: _The number of sums of parity values that we can form from (6) is_  
\[\mathcal{T}=\prod_{k=1}^{F}(1+n_{k}).\]  
The following simple result is key to the arguments that follow [47]:  
Proposition 2: _A necessary (but not sufficient) condition for the polyominoes to tile a region \(R\) is that \(S_{j}=p\) for at least one \(j\in\{1,2,\ldots,\mathcal{T}\}\)._  
When none of the possible parity sums equals the parity of the target region, we call this a _parity violation_, which implies that it is impossible for the given polyominoes to tile the target region. In this work, we are more interested when we know ahead of time that the polyominoes _do_ tile the target region \(R\), in which case many combinations of parity values may satisfy Proposition 2. Each solution satisfying Proposition 2 corresponds to a separate tiling subproblem with pariominoes that may or may not tile \(\tilde{R}\). The total number of possible tiling solutions is partitioned among all the pariomino tiling subproblems. It is possible to compute all solutions satisfying Proposition 2 using brute-force techniques. However, this rapidly becomes intractable for large problems. The decision problem of whether there is a solution that satisfies Proposition 2 is related to the general subset sum problem, which is \(\mathcal{NP}\)-complete [61]. For this reason, we apply a systematic mathematical procedure for solving this problem using linear Diophantine equations. We adapt the arguments given below from [47]. If all \(F\) polyominoes have zero parity, then we must have \(p=0\) so Proposition 2 is trivially satisfied. Now consider the case that at least one polyomino has non-zero parity. Assume, without loss of generality, the first \(r\) polyominoes, \(0\leq r\leq F-1\) have zero parity. Let the variable \(a_{i}^{+}\in\mathbb{N}\cup\{0\}\) denote how many of the \(n_{i}\)_non-negative_ elements drawn from \(\{-p_{i},+p_{i}\}\) are \(+p_{i}\), \(0\leq a_{i}^{+}\leq n_{i}\), \(i=r+1,r+2,\ldots,F\). We derive an equation in the variables \(a_{i}^{+}\) that matches the sum of the parities of the tiles to the parity of the target region. As we have \(a_{i}^{+}\) choices for how many of the \(n_{i}\) elements drawn from \(\{-p_{i},+p_{i}\}\)are \(+p_{i}\), we must have \(n_{i}-a_{i}^{+}\) choices of \(-p_{i}\), \(0\leq a_{i}^{+}\leq n_{i}\), \(i=r+1,r+2,\ldots F\). Then the equation \(s_{j}=p\) takes the form  
\[(+p_{r+1})a_{r+1}^{+}+(-p_{r+1})(n_{r+1}-a_{r+1}^{+})+(+p_{r+2})a_{r +2}^{+}+(-p_{r+2})(n_{r+2}-a_{r+2}^{+})+\ldots\] \[+(+p_{F})a_{F}^{+}+(-p_{F})(n_{F}-a_{F}^{+})=p,\]  
or after some simplification  
\[2p_{r+1}a_{r+1}^{+}+2p_{r+2}a_{r+2}^{+}+\cdots+2p_{F}a_{F}^{+}=p+p_{r+1}n_{r+1} +p_{r+2}n_{r+2}+\cdots+p_{F}n_{F},\]  
for \(r\in\{0,1,\ldots,F-1\}\), which is a linear Diophantine equation in \(F-r\) unknowns \(\{a_{i}^{+}\}_{i=r+1}^{F}\).