License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2022.2
URN: urn:nbn:de:0030-drops-165366
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16536/
Ishihata, Masakazu ;
Tokumasu, Fumiya
Solving and Generating Nagareru Puzzles
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.
BibTeX - Entry
@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/opus/volltexte/2022/16536},
URN = {urn:nbn:de:0030-drops-165366},
doi = {10.4230/LIPIcs.SEA.2022.2},
annote = {Keywords: Paper-and-pencil puzzle, SAT, CSP, ZDD}
}
