April 2026 - Polyomino Tiling Problem Colouring Algorithm

On a slightly work-related note, I think I might benefit from looking into solutions to polyomino tiling problems, so opening up this research hole, I found a journal paper, and some lecture notes, the latter of which I'll stretch the reading of over the usual handful of months. Instead, I'll start with A New Algorithm Based on Colouring Arguments for Identifying Impossible Polyomino Tiling Problems (https://doi.org/10.3390/a15020065) to get a sense of the ideas that exist in this space. A polyomino is constructed from a finite number of edge-connected cells in a plane. n-ominoes are defined as polyominoes with n cells. Polyominoes can be considered free, when allowed to undergo the reflection, rotation and translation. one-sided polyominoes lose the reflection, and fixed ones can only be translated. Tiling problems are primarily concerned with filling a target area with tiles of a specific shape. Polyomino tiling problems impose the rectangular cell constraint on its tiles and hence the target area are visually very "regular". The paper describes an algorithm for colored polyominoes to fill the target area, while also applying an additional color-pattern constraint (Section 1).

The (finite) set F of free polyominoes in the ℤ² lattice, written as {P₁}^F_i=1; F ≥ 1,. Assuming that they're simply connected (no 'holes'), the area of each polyomino P_i is written as ci, and given that R is a connected (not necessarily simply) union of a finite number of edge-connected cells, R is to be tiled with members of F. Each cell of a polyomino is colored black or white in checkerboard pattern, which can be defined through cell coordinates (i, j), by which i + j mod 2 is either 0 or 1. Define the parity of a checkerboard coloured region as the number of black cells minus the number of white cells. Assign first the target region R with a fixed checkerboard colouring with parity p, and a polyomino placed onto R applies the colouring, so transformation may change a polyomino's parity p_i. Two distinct polyominoes with the same area and parity are considered parity equivalent. As the name suggests, this is an equivalence relation. From it emerge some propositions:

• Parity equivalent n-ominoes have the same number of black and white squares
• The parities of all members of the set of all free polyominoes take on all possible values in ℤ
• Rectangles in ℤ², if their side-length m×n is even, the parity is 0. If it's odd, the parity is ±1
• A polyomino P with area c and parity ±p, then c is odd/even iff ±p is odd/even
• The parity is ±p relates to the number of black cells b, and white cells w as: b = (c ± p)/2; w = (c ∓ p)/2

(Prop. 1). The sequence of free polyomino follows the schema of checking first with a black square, and then adding the minimum number of black and white squares to increase parity by exactly 1, and allowing all rearrangement of squares to create all possible parity equivalent n-ominoes. This can be mapped onto an increasing parity sequence. For |p| ∈ ℕ, c = 2|p| - mod(p, 2); and for p = 2, then c = 2. Every polyomino in the sequence has minimal area with respect to its parity, or equivalently maximal parity wrt. its area (Theorem 1). Given a tile with some parity p, then p ≤ c/2 if p is even, and (c+1)/2 if p is odd (Corollary 1). A simple sufficient condition for a tiling problem without a solution based on parity is based on the proposition that a necessary (not sufficient) condition for the polyominoes tiling a region R is that the parity values s_j = p for at least one j ∈ {1, 2, ... M} (Prop. 2). By application to large tiling problems, all possible parity sums would have to be computed for any set of polyominoes. This introduces the parity problem, in which N polyominoes have 2^N^ different ways to sum the parity values, given that they're distinct and nonzero. Often, the resulting parity value overlaps with another sum, collapsing the possibilities. From it emerges that all possible sums of elements with parity -p_k, +p_k: s_j = p_k(n_k - 2j), n_k ≥ 1, j = 0, 1, ..., n_k (Prop. 3.i). The number of sums is given by M = Π^F_k=1(1 + n_k) (Prop. 3.ii). Given a tiling problem with nk copies of free polyomino P_k, the polyomino has z_k parity equivalent polyominoes. The parity violations are enumerated of

In section 4 of the paper, the enumeration of parity violations is translated into a system of linear Diophantine equations, which were then put into practice in the algorithm. The results are presented as MATLAB code in section 5 and 6.