arXiv Analytics

Sign in

arXiv:1710.04640 [cs.CC]AbstractReferencesReviewsResources

Hard and Easy Instances of L-Tromino Tilings

Javier T. Akagi, Carlos F. Gaona, Fabricio Mendoza, Marcos Villagra

Published 2017-10-12Version 1

In this work we study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, nonetheless, we indentify restrictions to the problem where either it remains NP-complete or it has a polynomial time algorithm. First we show that an aztec diamond of order $n$ always has an L-tromino tiling if and only if $n(n+1)\equiv 0\mod 3$; if an aztec diamond has at least two defects or holes, however, the problem of deciding a tiling is NP-complete. Then we study tilings of arbitrary regions where only $180^\circ$ rotations of L-trominoes are available. For this particular case we show that deciding the existence of a tiling remains NP-complete, yet, if a region contains certain so-called "forbidden polyominoes" as subregions, then there exists a polynomial time algorithm for deciding a tiling.

Comments: 13 pages, 11 figures
Categories: cs.CC, cs.DS, math.CO
Subjects: 68R05, F.2.2, G.2.1
Related articles: Most relevant | Search more
arXiv:cs/0703098 [cs.CC] (Published 2007-03-21)
Polynomial time algorithm for 3-SAT. Examples of use
arXiv:cs/0703146 [cs.CC] (Published 2007-03-29, updated 2012-05-07)
A Polynomial Time Algorithm for SAT
arXiv:cs/0701023 [cs.CC] (Published 2007-01-04, updated 2008-07-15)
A Polynomial Time Algorithm for 3-SAT