Document Open Access Logo

Tatamibari Is NP-Complete

Authors Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, Jayson Lynch

PDF
Thumbnail PDF

File

LIPIcs.FUN.2021.1.pdf
  • Filesize: 1.2 MB
  • 24 pages

Document Identifiers

Author Details

Aviv Adler
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Jeffrey Bosboom
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Erik D. Demaine
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Martin L. Demaine
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Quanquan C. Liu
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Jayson Lynch
  • Massachusetts Institute of Technology, Cambridge, MA, USA

Acknowledgements

This work was initiated during open problem solving in the MIT class on Algorithmic Lower Bounds: Fun with Hardness Proofs (6.890) taught by Erik Demaine in Fall 2014. We thank the other participants of that class for related discussions and providing an inspiring atmosphere.

Cite As Get BibTex

Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, and Jayson Lynch. Tatamibari Is NP-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FUN.2021.1

Abstract

In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an m x n grid of cells, where each cell possibly contains a clue among ⊞, ⊟, ◫.  The goal is to partition the grid into disjoint rectangles, where every rectangle contains exactly one clue, rectangles containing ⊞ are square, rectangles containing ⊟ are strictly longer horizontally than vertically, rectangles containing ◫ are strictly longer vertically than horizontally, and no four rectangles share a corner. We prove this puzzle NP-complete, establishing a Nikoli gap of 16 years. Along the way, we introduce a gadget framework for proving hardness of similar puzzles involving area coverage, and show that it applies to an existing NP-hardness proof for Spiral Galaxies. We also present a mathematical puzzle font for Tatamibari.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Nikoli puzzles
  • NP-hardness
  • rectangle covering

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, and Mikhail Rudoy. Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible. In Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), pages 3:1-3:21, La Maddalena, Italy, June 2018. Google Scholar
  2. Aaron B. Adcock, Erik D. Demaine, Martin L. Demaine, Michael P. O'Brien, Felix Reidl, Fernando Sánchez Villaamil, and Blair D. Sullivan. Zig-zag numberlink is NP-complete. Journal of Information Processing, 23(3):239-245, 2015. URL: https://doi.org/10.2197/ipsjjip.23.239.
  3. Aviv Adler, Michael Biro, Erik Demaine, Mikhail Rudoy, and Christiane Schmidt. Computational complexity of numberless Shakashaka. In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015), Kingston, Canada, August 2015. Google Scholar
  4. Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, and Jayson Lynch. Z3-based Tatamibari solver, and figures from Tatamibari NP-hardness paper, 2020. Includes inputs for the gadgets in this paper. URL: https://github.com/jbosboom/tatamibari-solver.
  5. Addison Allen, Daniel Packer, Sophia White, and Aaron Williams. Pencils and Sto-Stone are NP-complete [paper in review], 13 March 2018. URL: https://www.researchgate.net/project/Computational-Complexity-of-Video-Games-and-Puzzles/update/5aa7c402b53d2f0bba57bfb8.
  6. Walker Anderson, Erik D. Demaine, and Martin L. Demaine. Spiral galaxies font. In Jennifer Beineke and Jason Rosenhouse, editors, The Mathematics of Various Entertaining Subjects (MOVES 2017), volume 3, pages 24-30. Princeton University Press, 2019. Google Scholar
  7. Daniel Andersson. HIROIMONO is NP-complete. In Proceedings of the 4th International Conference on FUN with Algorithms, volume 4475 of Lecture Notes in Computer Science, pages 30-39, 2007. URL: http://www.springerlink.com/content/h31jq82185n0618h/?p=408092624f724be298d11ec22a3da382&pi=4.
  8. Daniel Andersson. Hashiwokakero is NP-complete. Information Processing Letters, 109(19):1145-1146, 2009. Google Scholar
  9. Mark de Berg and Amirali Khosravi. Optimal binary space partitions in the plane. In My T. Thai and Sartaj Sahni, editors, Proceedings of the 16th Annual International Conference on Computing and Combinatorics, volume 6196 of Lecture Notes in Computer Science, pages 216-225, July 2010. Google Scholar
  10. Leonardo Mendonça de Moura and Nikolaj Bjørner. Z3: an efficient SMT solver. In C. R. Ramakrishnan and Jakob Rehof, editors, Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2008), volume 4963 of Lecture Notes in Computer Science, pages 337-340, Budapest, Hungary, 2008. URL: https://doi.org/10.1007/978-3-540-78800-3_24.
  11. Erik D. Demaine and Martin L. Demaine. Fun with fonts: Algorithmic typography. Theoretical Computer Science, 586:111-119, June 2015. Google Scholar
  12. Erik D. Demaine, Yoshio Okamoto, Ryuhei Uehara, and Yushi Uno. Computational complexity and an integer programming model of Shakashaka. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E97-A(6):1213-1219, 2014. URL: http://hdl.handle.net/10119/12147.
  13. Erich Friedman. Corral puzzles are NP-complete. http://www.stetson.edu/~efriedma/papers/corral/corral.html, August 2002.
  14. Erich Friedman. Pearl puzzles are NP-complete, August 2002. URL: http://www.stetson.edu/~efriedma/papers/pearl/pearl.html.
  15. Erich Friedman. Spiral Galaxies puzzles are NP-complete, March 2002. URL: https://www2.stetson.edu/~efriedma/papers/spiral/spiral.html.
  16. Leslie M. Goldschlager. The monotone and planar circuit value problems are log space complete for P. SIGACT News, 9(2):25-29, July 1977. URL: https://doi.org/10.1145/1008354.1008356.
  17. Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation. A K Peters, July 2009. Google Scholar
  18. Markus Holzer, Andreas Klein, and Martin Kutrib. On the NP-completeness of the nurikabe pencil puzzle and variants thereof. In Proceedings of the 3rd International Conference on FUN with Algorithms, pages 77-89, Isola d'Elba, Italy, May 2004. Google Scholar
  19. Markus Holzer and Oliver Ruepp. The troubles of interior design - a complexity analysis of the game Heyawake. In Proceedings of the 4th International Conference on FUN with Algorithms, volume 4475 of Lecture Notes in Computer Science, pages 198-212, 2007. URL: http://www.springerlink.com/content/77t44731124j6427/?p=421c0ae5f9364a0880436edd93980bd7&pi=17.
  20. Ayaka Ishibashi, Yuichi Sato, and Shigeki Iwata. NP-completeness of two pencil puzzles: Yajilin and Country Road. Utilitas Mathematica, 88:237-246, 2012. Google Scholar
  21. Chuzo Iwamoto. Yosenabe is NP-complete. Journal of Information Processing, 22(1):40-43, 2014. URL: https://doi.org/10.2197/ipsjjip.22.40.
  22. Jonas Kölker. Kurodoko is NP-complete. Journal of Information Processing, 20(3):694-706, 2012. URL: https://doi.org/10.2197/ipsjjip.20.694.
  23. Kouichi Kotsuma and Yasuhiko Takenaga. NP-completeness and enumeration of Number Link puzzle. IEICE Technical Report, 109(465):1-7, March 2010. URL: http://ci.nii.ac.jp/naid/110008000705/en/.
  24. Brandon McPhail. The complexity of puzzles. Undergraduate thesis, Reed College, Portland, Oregon, 2003. URL: http://www.cs.umass.edu/~mcphailb/papers/2003thesis.pdf.
  25. Brandon McPhail. Light Up is NP-complete. http://www.mountainvistasoft.com/docs/lightup-is-np-complete.pdf, 2005.
  26. Brandon McPhail. Metapuzzles: Reducing SAT to your favorite puzzle. CS Theory talk, December 2007. Google Scholar
  27. Nikoli Co., Ltd. タタミバリ（仮題）(Tatamibari (temporary title)). Puzzle Communication Nikoli, 107, 10 June 2004. See https://www.nikoli.co.jp/ja/publication/various/nikoli/back_number/nikoli107/ for a table of contents.
  28. Nikoli Co., Ltd. パズル通信ニコリ > オモパリスト (Puzzle Communication Nikoli > Omopa List), 2020. Google Scholar
  29. Nikoli Co., Ltd. Nikoli puzzles, 2020. URL: http://www.nikoli.co.jp/en/puzzles/.
  30. Nobuhisa Ueda and Tadaaki Nagao. NP-completeness results for NONOGRAM via parsimonious reductions. Technical Report TR96-0008, Department of Computer Science, Tokyo Institute of Technology, Tokyo, Japan, May 1996. URL: http://www.phil.uu.nl/~oostrom/oudonderwijs/cki20/02-03/japansepuzzles/complexity.ps.
  31. Takayuki Yato. Complexity and completeness of finding another solution and its application to puzzles. Master’s thesis, University of Tokyo, Tokyo, Japan, January 2003. URL: http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf.
  32. Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications, and Computer Sciences, E86-A(5):1052-1060, 2003. Also IPSJ SIG Notes 2002-AL-87-2, 2002. URL: http://ci.nii.ac.jp/naid/110003221178/en/.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact