2026-07-26T19:54:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19919 2024-05-29T09:43:29Z ddc:004 open_access

Hamiltonian Paths and Cycles in NP-Complete Puzzles Deurloo, Marnix Donkers, Mitchell Maarse, Mieke Rin, Benjamin G. Schutte, Karen Hamiltonicity NP-completeness complexity theory pen-and-paper puzzles We show that several pen-and-paper puzzles are NP-complete by giving polynomial-time reductions from the Hamiltonian path and Hamiltonian cycle problems on grid graphs with maximum degree 3. The puzzles include Dotchi Loop, Chains, Linesweeper, Arukone{}₃ (also called Numberlink₃), and Araf. In addition, we show that this type of proof can still be used to prove the NP-completeness of Dotchi Loop even when the available puzzle instances are heavily restricted. Together, these results suggest that this approach holds promise in general for finding NP-completeness proofs of many pen-and-paper puzzles. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marnix Deurloo and Mitchell Donkers and Mieke Maarse and Benjamin G. Rin and Karen Schutte 2024 Is Part Of LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2024.11 urn:nbn:de:0030-drops-199199 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.11 eng https://creativecommons.org/licenses/by/4.0/legalcode