|
Abstract: Nurikabe is one of many paper-and-pencil puzzles recently
popular in Japan (and now elsewhere). The question, "Is this Nurikabe
puzzle solvable?" turns out to be very "hard" to answer quickly. We
construct a polynomial-time reduction from Circuit-SAT to Nurikabe to
show that Nurikabe belongs to the hardest of its class. The
construction, built of grid-based puzzle boards, is largely visual and
should be fun.
|