Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912919976935424 |
|---|---|
| author | Oka, Keigo Inaba, Naoki Iino, Akira |
| author_facet | Oka, Keigo Inaba, Naoki Iino, Akira |
| contents | 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 \times 325$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_19525 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers Oka, Keigo Inaba, Naoki Iino, Akira Data Structures and Algorithms Computational Complexity 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 \times 325$. |
| title | Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2602.19525 |