Hashiwokakero is NP-complete

DOI10.1016/J.IPL.2009.07.017zbMATH Open1206.68128OpenAlexW2023593885WikidataQ63549437 ScholiaQ63549437MaRDI QIDQ990945FDOQ990945

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)

• 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
• Tatamibari is NP-complete

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)