Herugolf and Makaro are NP-complete

DOI10.4230/LIPICS.FUN.2018.24zbMATH Open1489.68109MaRDI QIDQ3301014FDOQ3301014

Authors: C. Iwamoto, Masato Haruishi, Tatsuaki Ibusuki 

Publication date: 11 August 2020

Recommendations

• Computational complexity of NURIKABE
• NP-completeness of two pencil puzzles: Yajilin and Country Road
• Shikaku and Ripple Effect are NP-complete
• Tatamibari is NP-complete
• The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake

zbMATH Keywords

NP-completenesspencil puzzleHerugolfMakaro

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Game theory (91A99)

Cited In (8)

• Computational complexity of NURIKABE
• Shikaku and Ripple Effect are NP-complete
• The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake
• Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle
• NP-completeness of two pencil puzzles: Yajilin and Country Road
• Physical ZKP for Makaro using a standard deck of cards
• Computational complexity of two pencil puzzles: Kurotto and Juosan
• Computational complexity of puzzles and related topics

This page was built for publication: Herugolf and Makaro are NP-complete

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