The Complexity of Generalized Domino Tilings
Igor Pak, Jed Yang · The Electronic Journal of Combinatorics · 2013
Tiling planar regions with dominoes is a classical problem, where the decision and counting problems are polynomial. We prove a variety of hardness results (both NP- and #P-completeness) for different generalizations of dominoes in three and higher dimensions.