Login
- Titel:
Computational Complexity of NURIKABE
- Autor(en):
- Holzer, Markus; Klein, Andreas; Kutrib, Martin; Ruepp, Oliver
- Abstract:
- We show that the popular pencil puzzle NURIKABE is intractable from the computational complexity point of view, that is, it is NP-complete, even when the involved numbers are 1 and 2 only. To this end, we show how to simulate Boolean gates by the puzzle under consideration. Moreover, we also study some NURIKABE variants, which remain NP-complete, too.
- Zeitschriftentitel:
- Fundamenta Informaticae
- Jahr:
- 2011
- Band / Volume:
- 110
- Monat:
- Jan
- Heft / Issue:
- 1
- Seitenangaben Beitrag:
- 159--174
- Volltext / DOI:
- doi:10.3233/FI-2011-534
BibTeX