Hashiwokakero is NP-complete

DOI10.1016/j.ipl.2009.07.017zbMath1206.68128OpenAlexW2023593885WikidataQ63549437 ScholiaQ63549437MaRDI QIDQ990945

Daniel Andersson

Publication date: 1 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.07.017

zbMATH Keywords

computational complexitycombinatorial problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems ⋮ On a generalization of ``eight blocks to madness puzzle ⋮ Computational complexity of two pencil puzzles: Kurotto and Juosan ⋮ \textsc{Hanano} puzzle is \textsf{NP}-hard ⋮ Matchstick puzzles on a grid ⋮ A case study on the graph-transformational modeling and analysis of puzzles

Cites Work

• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
• Hamilton Paths in Grid Graphs

This page was built for publication: Hashiwokakero is NP-complete