Hard Tiling Problems with Simple Tiles

Cristopher Moore and John Michael Robson

Discrete and Computational Geometry 26(4) (2001) 573--590.

It is well-known that the question of whether a given finite region can be tiled with a given set of tiles is NP-complete. We show that the same is true for the right tromino and square tetromino on the square lattice, or for the right tromino alone. In the process, we show that Monotone 1-in-3 Satisfiability is NP-complete for planar cubic graphs. In higher dimensions, we show NP-completeness for the domino and straight tromino for general regions on the cubic lattice, and for simply-connected regions on the four-dimensional hypercubic lattice.

Click here to download Postscript

Click here to download PDF

Cris Moore <moore@santafe.edu>