Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Complexity of Tiling a Polygon with Trominoes or Bars

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

We study the computational hardness of the tiling puzzle with polyominoes, where a polyomino is a right-angled polygon (i.e., a polygon made by connecting unit squares along their edges). In the tiling problem, we are given a right-angled polygon P and a set S of polyominoes, and asked whether P can be covered without any overlap using translated copies of polyominoes in S. In this paper, we focus on trominoes and bars as polyominoes; a tromino is a polyomino consisting of three unit squares, and a bar is a rectangle of either height one or width one. Notice that there are essentially two shapes of trominoes, that is, I-shape (i.e., a bar) and L-shape. We consider the tiling problem when restricted to only L-shape trominoes, only I-shape trominoes, both L-shape and I-shape trominoes, or only two bars. In this paper, we prove that the tiling problem remains NP-complete even for such restricted sets of polyominoes. All reductions are carefully designed so that we can also prove the # P-completeness and ASP-completeness of the counting and the another-solution-problem variants, respectively. Our results answer two open questions proposed by Moore and Robson (Discrete Comput Geom 26:573–590, 2001) and Pak and Yang (J Comb Theory 120:1804–1816, 2013).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20

Similar content being viewed by others

References

  1. Beauquier, D., Nivat, M., Remila, E., Robson, M.: Tiling figures of the plane with two bars. Comput. Geom. 5(1), 1–25 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  2. Creignou, N., Hermann, M.: Complexity of generalized satisfiability counting problems. Inf. Comput. 125(1), 1–12 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  3. El-Khechen, D., Dulieu, M., Iacono, J., van Omme, N.: Packing \(2\times 2\) unit squares into grid polygons is NP-complete. In: Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG 2009), pp. 33–36 (2009). http://cccg.ca/proceedings/2009/cccg09_09.pdf

  4. Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12(3), 133–137 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  5. Golomb, S.: Polyominoes, 2nd edn. Princeton University Press, Princeton (1994)

    MATH  Google Scholar 

  6. Hearn, R.A., Demaine, E.D.: Games, Puzzles, and Computation. A K Peters, Wellesley (2009)

    MATH  Google Scholar 

  7. Horiyama, T., Ito, T., Nakatsuka, K., Suzuki, A., Uehara, R.: Packing trominoes is NP-complete, #P-complete and ASP-complete. In: Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), pp. 211–216 (2012). http://2012.cccg.ca/e-proceedings.pdf

  8. Kenyon, C., Kenyon, R.W.: Tiling a polygon with rectangles. In: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS 1992), pp. 610–619. IEEE, Piscataway (1992)

  9. Moore, C., Robson, J.M.: Hard tiling problems with simple tiles. Discrete Comput. Geom. 26(4), 573–590 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  10. Pak, I., Yang, J.: Tiling simply connected regions with rectangles. J. Comb. Theory Ser. A 120(7), 1804–1816 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  11. Rémila, E.: Tiling a simply connected figure with bars of length 2 or 3. Discrete Math. 160(1–3), 189–198 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  12. Rémila, E.: Tiling with bars and satisfaction of Boolean formulas. Eur. J. Comb. 17(5), 485–491 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  13. Rémila, E.: Tiling a polygon with two kinds of rectangles. Discrete Comput. Geom. 34(2), 313–330 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  14. Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC’78), pp. 216–226. ACM, New York (1978)

  15. Yato, T., Seta, T.: Complexity and completeness of finding another solution and its application to puzzles. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E86–A(5), 1052–1060 (2003)

    Google Scholar 

Download references

Acknowledgements

We are grateful to Yoshio Okamoto for his fruitful suggestions, and thank anonymous referees of the preliminary version and of this journal version for their helpful suggestions. This work is partially supported by MEXT/JSPS KAKENHI Grant Numbers JP15K00008 and JP24106007 (T. Horiyama), JP15H00849 and JP16K00004 (T. Ito), JP26730001 (A. Suzuki), and JP26330009 and JP24106004 (R. Uehara).

Author information

Authors and Affiliations

  1. Graduate School of Science and Engineering, Saitama University, 255 Shimo-Okubo, Sakura, Saitama, 338-8570, Japan

    Takashi Horiyama

  2. Graduate School of Information Sciences, Tohoku University, 6-6-05 Aramaki Aza Aoba, Aoba-ku, Sendai, Miyagi, 980-8579, Japan

    Takehiro Ito & Akira Suzuki

  3. CREST, JST, 4-1-8 Honcho, Kawaguchi, Saitama, 332-0012, Japan

    Takehiro Ito & Akira Suzuki

  4. Faculty of Engineering, Saitama University, 255 Shimo-Okubo, Sakura, Saitama, 338-8570, Japan

    Keita Nakatsuka

  5. School of Information Science, JAIST, 1-1 Asahidai, Nomi, Ishikawa, 923-1292, Japan

    Ryuhei Uehara

Authors
  1. Takashi Horiyama
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Takehiro Ito
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Keita Nakatsuka
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Akira Suzuki
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ryuhei Uehara
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Akira Suzuki.

Additional information

Editor in Charge: János Pach

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Horiyama, T., Ito, T., Nakatsuka, K. et al. Complexity of Tiling a Polygon with Trominoes or Bars. Discrete Comput Geom 58, 686–704 (2017). https://doi.org/10.1007/s00454-017-9884-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-017-9884-9

Keywords

Mathematics Subject Classification

Search

Navigation