A polyomino tiling is a tiling of a region of the plane, possibly the whole plane, by specified types of polyominoes.
Tiling by polyominoes has
been investigated since at least the late 1950s, particularly by S. Golomb (Wolfram
2002, p. 943).
Recently, sets of polyominoes that force non-periodic patterns have been found. The set illustrated at left above was announced by Roger
Penrose in 1994, and the slightly smaller set illustrated at right below was found
by Matthew Cook (Wolfram 2002, p. 943).
Both of these sets yield nested patterns, as illustrated above for Cook's tiles (Wolfram
2002, p. 943).
Consider now those collections of all-ominoes which form a rectangle.
The polyominoes of orders and form only a square and rectangle,
respectively. The two polyominoes of order cannot form a rectangle, nor
can the five polyominoes of order or the 35 polyominoes of order
(Beeler 1972). There are several rectangles formed by the 12 polyominoes
of order , as summarized in the following table (Fletcher 1965,
Beeler 1972).
size
solutions
2
368
1010
2339
two
2
with hole
65
Chen and Xie (2026) construct a fixed finite family of connected polyominoes for which counting translation-only tilings of an
square
is -complete
under polynomial-time metric reductions. The counting complexity statement uses a binary encoding of , so the board can have area exponential
in the input length. The counting function also belongs
to . This counts tilings rather than merely testing whether
a tiling exists.
A finite set of allowed oriented polyominoes can be reduced to Wang tiles (Liang 2026). In each oriented
polyomino, give each interior unit side a fresh color
shared by the two squares meeting there, and use one common
color for all exterior sides. Then split each polyomino
into its unit squares. The fresh colors force the pieces
to reassemble, while the common color permits adjacent polyominoes
to meet. With that common color fixed on the boundary of the region, the construction
preserves the number of tilings.