Computational complexity of NURIKABE

DOI10.3233/FI-2011-534MaRDI QIDQ3100933zbMATH OpenOpenAlexFDO

Authors Markus Holzer, Martin Kutrib, Oliver Ruepp, Andreas Klein

Publication date 22 November 2011

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2011-534

zbMATH Keywords

computational complexityNP-completepencil puzzle Nurikabe

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

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

Cited in

(15)

• The fewest clues problem
• Interactive physical ZKP for connectivity: applications to Nurikabe and Hitori
• Rikudo is NP-complete
• Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
• Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle
• The complexity of regex crosswords
• Herugolf and Makaro are NP-complete
• Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
• scientific article; zbMATH DE number 5527901 (Why is no real title available?)
• NP-completeness of two pencil puzzles: Yajilin and Country Road
• The fewest clues problem
• Shikaku and Ripple Effect are NP-complete
• The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake
• Counting Islands in Nurikabe
• Computational complexity of puzzles and related topics

This page was built for publication: Computational complexity of NURIKABE

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