DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2022.2

Solving and Generating Nagareru Puzzles

Authors: Masakazu Ishihata and Fumiya Tokumasu

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{ishihata_et_al:LIPIcs.SEA.2022.2,
  author =	{Ishihata, Masakazu and Tokumasu, Fumiya},
  title =	{{Solving and Generating Nagareru Puzzles}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.2},
  URN =		{urn:nbn:de:0030-drops-165366},
  doi =		{10.4230/LIPIcs.SEA.2022.2},
  annote =	{Keywords: Paper-and-pencil puzzle, SAT, CSP, ZDD}
}

Search Results

Documents authored by Tokumasu, Fumiya

Solving and Generating Nagareru Puzzles

Abstract

Cite as

Thanks for your feedback!

Could not send message