Title:
Hard Tiling Problems with Simple Tiles
Author(s):
Cristopher Moore, John Robson
Paper #:
00-03-019
Date:
March 1, 2000
Abstract:
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.
Facebook
Twitter
Email Newsletter
SFI News Feed
Google+
YouTube
iTunes U