Document Open Access Logo

Solving and Generating Nagareru Puzzles

Authors Masakazu Ishihata, Fumiya Tokumasu

PDF
Thumbnail PDF

File

LIPIcs.SEA.2022.2.pdf
  • Filesize: 1.12 MB
  • 17 pages

Document Identifiers

Author Details

Masakazu Ishihata
  • NTT Communication Science Laboratories, Kyoto, Japan
Fumiya Tokumasu
  • National Institute of Technology, Nara College, Nara, Japan

Cite AsGet BibTex

Masakazu Ishihata and Fumiya Tokumasu. Solving and Generating Nagareru Puzzles. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SEA.2022.2

Abstract

Solving paper-and-pencil puzzles is fun for people, and their analysis is also an essential issue in computational complexity theory. There are some practically efficient solvers for some NP-complete puzzles; however, the automatic generation of interesting puzzle instances still stands out as a complex problem because it requires checking whether the generated instance has a unique solution. In this paper, we focus on a puzzle called Nagareru and propose two methods: one is for implicitly enumerating all the solutions of its instance, and the other is for efficiently generating an instance with a unique solution. The former constructs a ZDD that implicitly represents all the solutions. The latter employs the ZDD-based solver as a building block to check the uniqueness of the solution of generated instances. We experimentally showed that the ZDD-based solver was drastically faster than a CSP-based solver, and our generation method created an interesting instance in a reasonable time.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Combinatorial algorithms
  • Theory of computation → Generating random combinatorial structures
  • Mathematics of computing → Graph algorithms
Keywords
  • Paper-and-pencil puzzle
  • SAT
  • CSP
  • ZDD

Metrics

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

Supplementary Materials

References

  1. Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, and Jayson Lynch. Tatamibari is np-complete. In Martin Farach-Colton, Giuseppe Prencipe, and Ryuhei Uehara, editors, 10th International Conference on Fun with Algorithms, FUN 2021, May 30 to June 1, 2021, Favignana Island, Sicily, Italy, volume 157 of LIPIcs, pages 1:1-1:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.FUN.2021.1.
  2. Daniel Andersson. HIROIMONO is np-complete. In Pierluigi Crescenzi, Giuseppe Prencipe, and Geppino Pucci, editors, Fun with Algorithms, 4th International Conference, FUN 2007, Castiglioncello, Italy, June 3-5, 2007, Proceedings, volume 4475 of Lecture Notes in Computer Science, pages 30-39. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-72914-3_5.
  3. Erich Friedman. Corral puzzles are np-complete. Technical Report, 2002. URL: https://erich-friedman.github.io/papers/corral.pdf.
  4. Markus Holzer, Andreas Klein, Martin Kutrib, and Oliver Ruepp. Computational complexity of NURIKABE. Fundam. Informaticae, 110(1-4):159-174, 2011. URL: https://doi.org/10.3233/FI-2011-534.
  5. Ayaka Ishibashi, Yuichi Sato, and Shigeki Iwata. Np-completeness of two pencil puzzles: Yajilin and country road. UTILITAS MATHEMATICA, 88:237-246, July 2012. Google Scholar
  6. Chuzo Iwamoto. Yosenabe is np-complete. J. Inf. Process., 22(1):40-43, 2014. URL: https://doi.org/10.2197/ipsjjip.22.40.
  7. Chuzo Iwamoto, Masato Haruishi, and Tatsuaki Ibusuki. Herugolf and makaro are np-complete. In Hiro Ito, Stefano Leonardi, Linda Pagli, and Giuseppe Prencipe, editors, 9th International Conference on Fun with Algorithms, FUN 2018, June 13-15, 2018, La Maddalena, Italy, volume 100 of LIPIcs, pages 24:1-24:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.FUN.2018.24.
  8. Chuzo Iwamoto and Tatsuaki Ibusuki. Dosun-fuwari is np-complete. J. Inf. Process., 26:358-361, 2018. URL: https://doi.org/10.2197/ipsjjip.26.358.
  9. Chuzo Iwamoto and Tatsuya Ide. Moon-or-sun, nagareru, and nurimeizu are np-complete (in japanese). In Winter LA Symposium 2019, 2019. Google Scholar
  10. Chuzo Iwamoto and Tatsuya Ide. Nurimisaki and sashigane are np-complete. In Zachary Friggstad and Jean-Lou De Carufel, editors, Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019, August 8-10, 2019, University of Alberta, Edmonton, Alberta, Canada, pages 184-194, 2019. Google Scholar
  11. Jun Kawahara, Takeru Inoue, Hiroaki Iwashita, and Shin-ichi Minato. Frontier-based search for enumerating all constrained subgraphs with compressed representation. IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 100-A(9):1773-1784, 2017. URL: https://doi.org/10.1587/transfun.E100.A.1773.
  12. Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki, and Ryo Yoshinaka. Colorful frontier-based search: Implicit enumeration of chordal and interval subgraphs. In Ilias S. Kotsireas, Panos M. Pardalos, Konstantinos E. Parsopoulos, Dimitris Souravlias, and Arsenis Tsokas, editors, Analysis of Experimental Algorithms - Special Event, SEA² 2019, Kalamata, Greece, June 24-29, 2019, Revised Selected Papers, volume 11544 of Lecture Notes in Computer Science, pages 125-141. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-34029-2_9.
  13. Graham Kendall, Andrew J. Parkes, and Kristian Spoerer. A survey of np-complete puzzles. J. Int. Comput. Games Assoc., 31(1):13-34, 2008. Google Scholar
  14. Shin-ichi Minato. Zero-suppressed bdds for set manipulation in combinatorial problems. In Alfred E. Dunlop, editor, Proceedings of the 30th Design Automation Conference. Dallas, Texas, USA, June 14-18, 1993, pages 272-277. ACM Press, 1993. URL: https://doi.org/10.1145/157485.164890.
  15. Yu Nakahata, Jun Kawahara, Takashi Horiyama, and Shin-ichi Minato. Implicit enumeration of topological-minor-embeddings and its application to planar subgraph enumeration. In M. Sohel Rahman, Kunihiko Sadakane, and Wing-Kin Sung, editors, WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Singapore, March 31 - April 2, 2020, Proceedings, volume 12049 of Lecture Notes in Computer Science, pages 211-222. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-39881-1_18.
  16. Nikoli Co., Ltd. Puzzles: Nagareru [Nikoli]. Available online, 2021. https://www.nikoli.co.jp/en/puzzles/nagareru.html, (accessed on 20th April 2021).
  17. Hirofumi Suzuki, Sun Hao, and Shin-ichi Minato. Generating all solutions of minesweeper problem using degree constrained subgraph model. In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), page 356. The Steering Committee of The World Congress in Computer Science, Computer …, 2016. Google Scholar
  18. Naoyuki Tamura. Solving Puzzles with Sugar Constraint Solver (in Japanese). Available online, 2013. https://cspsat.gitlab.io/sugar-puzzles/, (accessed on 20th April 2021).
  19. Naoyuki Tamura. Solving Slither Link Puzzles with Sugar Constraint Solver (in Japanese). Available online, 2013. https://cspsat.gitlab.io/sugar-puzzles/slitherlink.html, (accessed on 20th April 2021).
  20. Naoyuki Tamura, Akiko Taga, Satoshi Kitagawa, and Mutsunori Banbara. Compiling finite linear CSP into SAT. Constraints An Int. J., 14(2):254-272, 2009. URL: https://doi.org/10.1007/s10601-008-9061-0.
  21. Nobuhisa Ueda and Tadaaki Nagao. Np-completeness results for nonogram via parsimonious reductions. Technical report, Technical Report, TR96-0008, 1996. Google Scholar
  22. Gerhard van der Knijff, H Zantema, and JH Geuvers. Solving and generating puzzles with a connectivity constraint. Bachelor thesis of Radboud University, 2021. Google Scholar
  23. Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 86-A(5):1052-1060, 2003. URL: http://search.ieice.org/bin/summary.php?id=e86-a_5_1052.
  24. Ryo Yoshinaka, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki Iwashita, and Shin-ichi Minato. Finding all solutions and instances of numberlink and slitherlink by zdds. Algorithms, 5(2):176-213, 2012. URL: https://doi.org/10.3390/a5020176.
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 Imprint Privacy Contact