Rikudo is NP-complete

DOI10.1016/J.TCS.2022.01.034MaRDI QIDQ2118858OpenAlexFDO

Authors Viet-Ha Nguyen, Kévin Perrot

Publication date 23 March 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2022.01.034

zbMATH Keywords

NP-completeone-player number-placement gameRikudo

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Shikaku and Ripple Effect are NP-complete
• Hashiwokakero is NP-complete
• HIROIMONO Is NP-Complete
• scientific article; zbMATH DE number 1342225
• Tatamibari is NP-complete
• Knuth--bendix constraint solving is NP-complete
• scientific article; zbMATH DE number 1754649
• On strong NP-completeness of rational problems
• Computational complexity of NURIKABE
• The STO problem is NP-complete

Cites work

• scientific article; zbMATH DE number 512936 (Why is no real title available?)
• Efficient Planarity Testing
• GO Is Polynomial-Space Hard
• Gobang is PSPACE-complete
• Hamiltonian cycles in T-graphs
• Hanabi is NP-complete, even for cheaters who look at their cards
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• Minesweeper is NP-complete.
• Minesweeper may not be NP-complete but is hard nonetheless
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Planar 3DM is NP-complete
• The computational complexity of the game of Set and its theoretical applications
• \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\)

Cited in

(1)

• Tatamibari is NP-complete

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

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