Nurikabe

• Main Author: Johan Groenen
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Published: 2008
• Subjects: White Islands
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.2451; http://www.liacs.nl/assets/Bachelorscripties/18-JohanGroenen.pdf

Nurikabe, a pencil-and-paper, binary determination puzzle from the creators of Sudoku, is on the verge of breakthrough in Europe as the successor of the Sudoku puzzle. Played on an m × n grid, the goal is to determine for every cell whether it should be colored white or black, much like Sudoku and Minesweeper. A number in a cell on the puzzle grid indicates the size of the island the cell containing the number belongs to. These white islands are separated by a black wall, which is called Nurikabe. Since it is NP-complete, it can be difficult to solve a given puzzle. Compared to Sudoku, relatively little effort has been made in finding algorithms for solving these puzzles. In this paper we will describe methods for automated solving and generation of Nurikabe Puzzles. 1