Portal de Periódicos da CAPES

Computational Complexity of NURIKABE

2011; IOS Press; Volume: 110; Issue: 1-4 Linguagem: Inglês

10.3233/fi-2011-534

1875-8681

Markus Holzer, Andreas Klein, Martin Kutrib, Oliver Ruepp,

Coding theory and cryptography

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 puz