Affiliations: Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. {holzer,kutrib}@informatik.uni-giessen.de | Institut für Informatik, Technische Universität München, Boltzmannstr. 3, 85748 Garching bei München, Germany. [email protected]
Note: [] Address for correspondence: Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany
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.
