Herugolf and Makaro are NP-complete

DOI10.4230/LIPICS.FUN.2018.24MaRDI QIDQ3301014zbMATH OpenFDO

Authors C. Iwamoto, Masato Haruishi, Tatsuaki Ibusuki

Publication date 11 August 2020

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)

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

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
• Computational complexity of two pencil puzzles: Kurotto and Juosan
• Physical ZKP for Makaro using a standard deck of cards
• 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)