On the Complexity of Packing Trominoes

摘要

We study the computational complexity of packing puzzles of identical polyominoes. Packing dominoes (i.e.,1 × 2 rectangles) into grid polygons can be solved in polynomial time by reducing to a bipartite matching problem. On the other hand, packing 2×2 squares is known to be NP-complete. In this paper, we fill the gap between dominoes and 2×2 squares, that is, we consider the packing puzzles of trominoes. Note that there exist only two shapes of trominoes: L-shape and Ⅰ-shape. We show that their packing problems are both NP-complete. Our reductions are carefully designed so that we can also prove #P-completeness and ASP-completeness of the counting and the another-solution-problem variants, respectively. (This article is a technical report without peer review.)%与えられた盤面に1種類のポリオミノを詰め込む問題に対し，その計算複雑さを研究する.ドミノ （すなわち，1×2の矩形）を詰め込む問題は，二部グラフのマッチング問題に帰着することで，多項式時間で解けることが知られている.一方で，2×2の正方形を詰め込む問題は，NP完全であることが知られている.本論文では，トロミノ（すなわち，サイズ3のポリオミノ）を詰め込む問題を扱うことで，これら既存研究のギャップを埋める.ここで，トロミノはL型とⅠ型の2種類が存在することに注意が必要である.本論文では，どちらのトロミノを詰め込む問題もNP完全であることを示す.また，これらの帰着を注意深く設計することで，トロミノ詰込問題の数え上げ版が#P完全であり，別解問題版がASP完全であることを示す.