Hard Tiling Problems with Simple Tiles |
| |
Authors: | C. Moore J.M. Robson |
| |
Affiliation: | (1) Computer Science Department, University of New Mexico, Albuquerque, NM 87131, USA, US |
| |
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. Received March 8, 2000, and in revised form May 14, 2001, and June 18, 2001. Online publication October 12, 2001. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|