Hashiwokakero is NP-complete

DOI10.1016/J.IPL.2009.07.017MaRDI QIDQ990945zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Cites work

• Hamilton Paths in Grid Graphs
• Playing games with algorithms: algorithmic combinatorial game theory

Cited in

(10)

• Tatamibari is NP-complete
• Matchstick puzzles on a grid
• A case study on the graph-transformational modeling and analysis of puzzles
• Rikudo is NP-complete
• \textsc{Hanano} puzzle is \textsf{NP}-hard
• LaserTank is NP-Complete
• 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
• Computational complexity of puzzles and related topics

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990945)