User: Guest  Login
Author(s):
Holzer, Markus; Klein, Andreas; Kutrib, Martin; Ruepp, Oliver 
Title:
Computational Complexity of NURIKABE 
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:
Pages contribution:
159--174