Benutzer: Gast  Login
Autor(en):
Holzer, Markus; Klein, Andreas; Kutrib, Martin; Ruepp, Oliver 
Titel:
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. 
Zeitschriftentitel:
Fundamenta Informaticae 
Jahr:
2011 
Band / Volume:
110 
Monat:
Jan 
Heft / Issue:
Seitenangaben Beitrag:
159--174