Covering a Polyomino-Shaped Stain with Non-Overlapping Stickers of the Same Shape

You find a stain on the wall and decide to cover it with non-overlapping stickers of a
single identical shape (rotation and reflection are allowed). Is it possible to find a sticker
shape that fails to cover the stain? In this paper, we consider this problem under polyomino
constraints and complete the classification of always-coverable stain shapes (polyominoes).
We provide proofs for the maximal always-coverable polyominoes and construct concrete
counterexamples for the minimal not always-coverable ones, demonstrating that such cases
exist even among hole-free polyominoes. This classification consequently yields an algorithm
to determine the always-coverability of any given stain. We also show that the problem of
determining whether a given sticker can cover a given stain is NP-complete, even though
exact cover is not demanded. This result extends to the 1D case where the connectivity
requirement is removed. As an illustration of the problem complexity, for a specific hexomino
(6-cell) stain, the smallest sticker found in our search that avoids covering it has, although
not proven minimum, a bounding box of 325 × 325.