Login
- Title:
Computational Complexity of NURIKABE
- Author(s):
- 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.
- Journal title:
- Fundamenta Informaticae
- Year:
- 2011
- Journal volume:
- 110
- Month:
- Jan
- Journal issue:
- 1
- Pages contribution:
- 159--174
- Fulltext / DOI:
- doi:10.3233/FI-2011-534
BibTeX