Introduction

Nurikabe is one of the most interesting games we have worked on. Please see the first two example figures. It is played on a rectangular grid of cells, most of which are initially blank (grey in our version) but with a scattering of clue cells (white with numbers).

Cells "touch" orthogonally and the cells from one clue must not touch those of another.

Contents

When the puzzle is complete each clue cell of value N must be part of a cluster of touching white cells of size N and all other cells on the board must be black.

The black cells must touch to form a continuous path. This means that from every black cell we can find a route to any other, using only touching black cells.

The final rule is that no 2x2 blocks of black cells (squares) are allowed.

Nurikabe Example 1

Nurikabe Example 1

A typical Nurikable starting grid.

Others have assigned various descriptive names to the white and black cells. White cells are termed "islands" and the black cells form the surrounding "water" or "walls". We stick with "black" and "white".

The game contains 500 puzzles, each with grids of 10x10 cells.

The best way to see how the game is played is to read the caption and then watch the worked example.

The program starts with a randomly selected puzzle displayed. It shows a grid of cells, some white and containing numbers, but most are grey which indicates they are unsolved. Players can set cells white with a left mouse click, black with right mouse, and can undo with middle mouse.

Nurikabe Example 2

Nurikabe Example 2

The solution to the grid shown in Example 1.

Nurikabe Example 3

Nurikabe Example 3

A Nurikable puzzle containing errors. Incorrect cells are indicated by a red X. If the player clicks on the thumb all cells set since the first error will be reset to grey and the red X's removed.

At the top of the display is a Toolbar. The jigsaw piece button at the left is a menu which has options for configuring the program and saving the current settings. The next button to the right is used for selecting puzzles: left mouse will select a random puzzle and right mouse the next one in sequence. Next is a wand for selecting and executing hints; a thumb for checking and correcting errors, and a sad smiley for showing the solution. To the right of this are 2 numbers. The first is the puzzle number, the next a clock which ticks every 5 seconds. The puzzle number display is also an input box: players can position the cursor over this area and type in a number between 0 and 499 followed by 'Enter' to load the corresponding puzzle.

When a hint is requested using the wand a cell in the grid will be marked with a "?". If the player can work out its correct colour they can set it in the usual way. If not a further click on the wand will colour the cell. When a hint is requested the clock display is used to show the code for the algorithm used.

If the player clicks the thumb button the grid is checked for errors and they are reported as shown in Figure 3: the thumb turns down and the inccorrect cells are marked with a red X. A further click on the thumb will remove the Xs and undo all changes since the first mistake was made.

If the player requests a hint when errors are present no hint will be given and the thumb will turn down and the mistakes marked. The errors must be corrected using the thumb button before a hint can be given.

Nurikabe Worked Example

A video from nurikabe showing a puzzle being solved. Whites from different clues cannot touch which means that completed whites must be surrounded by blacks and that clues touching diagonally must have black cells on the opposing diagonal. The player quickly deals with the initial cases of these two simple consequences: left-click for white, right-click for black. Next, if a white can only extend one way that must be the way, so the 6 in the top left is extended. But then the adjacent black will be isolated if it is not extended too. Then the player sees the potential formation of a block of 4 black cells which can only be prevented by extending the nearby 3. Shortly after the player clicks the thumb to check that she has not made any mistakes. Potentially isolated blacks are extended, then whites. She then pauses and notices two easy blacks that could have been set at the start, and this opens up a new area. Another block of 4 blacks is prevented at the bottom of the grid. The thumb is clicked; the 5 extended. A bit later she cannot see how to proceed and so clicks on the wand which results in a hint 14 being displayed: another potential block of 4 blacks. A further click on the wand and the white cell is added. This has to form part of the white of size 6. Then she notices that however the 5 in the top row is completed it must use the cell in the next row so she sets it white. A few more moves and she is done.

Algorithms

Given the rules of the game some algorithms are fairly obvious. Cells which cannot be reached by any clue must be black. As whites from different clues cannot touch, when finished, all the white cells for a clue can be surrounded by black cells. So, for example, all clues of size 1 can be surrounded at the start of a game. If unfinished clues have only one way to extend, then that must be the way. Black cells cannot be isolated. Most of the algorithms are variations on these themes. Some of the program's algorithms may seem identical to one another - say finding cells which cannot be reached by any clue - but they are assigned separate numbers because they deal with different circumstances and the coding within the program is necessarily different.

The puzzles can be solved using a single "algorithm" for each step, ie when trying to solve an area of the grid there need be no necessity for considering multiple possible solutions and then working through them to find the one which satisfies all requirements.

Obviously the hint algorithms rely on recognising particular patterns of clues plus finished and unfinished cells. In very rare cases it may be possible that the algorithms can find no recognisable pattern and so cannot recommend a hint based on logic. If that arises the program cheats and gives any unfinished cell as a hint. This is displayed in the normal way and denoted as algorithm 20.

Nurikabe algorithm 0

Nurikabe algorithm 0

If a white can only extend via a single cell, that cell must be white.

Nurikabe algorithm 1

Nurikabe algorithm 1

The black cell to the left of the highlighted cell must be connected to the other black cells so the highlighted cell must be black.

Nurikabe algorithm 2

Nurikabe algorithm 2

The white to the right of the highlighted cell is complete so must be surrounded by black cells.

Nurikabe algorithm 3

Nurikabe algorithm 3

The highlighted cell cannot be reached by any clue cell, so it must be black.

Nurikabe algorithm 4

Nurikabe algorithm 4

The clue of size 5 next to the highlighted cell must expand through the highlighted cell in order to reach the required size, so the highlighted cell must be white.

Nurikabe algorithm 5

Nurikabe algorithm 5

All black cells must be connected to each other. The highlighted cell is the only possible connecting point for the string of black cells to its left. Therefore it too must be black.

Nurikabe algorithm 6

Nurikabe algorithm 6

The clue of size 2 has just been completed so now the highlighted cell cannot be reached by any clue and must be black.

Nurikabe algorithm 7

Nurikabe algorithm 7

The clue of size 5 above the highlighted cell can reach it, but not if it includes the nearby white cells. So the highlighted cell must be black.

Nurikabe algorithm 8

Nurikabe algorithm 8

The clue of size 6 requires one more cell for completion. The only way to add one more cell without making it too large is to set the highlighted cell white.

Nurikabe algorithm 9

Nurikabe algorithm 9

The unfinished clue of size 5 in the bottom row must include the white cell it currently touches diagonally. Once that cell is connected via either of the two touching grey cells the clue will be complete. Therefore the highlighted cell must be black.

Nurikabe algorithm 10

Nurikabe algorithm 10

White cells from different clues cannot touch so the highlighted cell cannot be white.

Nurikabe algorithm 11

Nurikabe algorithm 11

The two clues of size 3 near the bottom of the grid cannot touch so the highlighted cell must be black.

Nurikabe algorithm 12

Nurikabe algorithm 12

The clue of size 3 at the bottom of the grid has two choices for the cell it requires for completion. Which ever one it chooses the highlighted cell must be black.

Nurikabe algorithm 13

Nurikabe algorithm 13

A non-clue cell surrounded by blacks must be black.

                                               

Nurikabe algorithm 14

Nurikabe algorithm 14

Squares of four black cells are forbidden so the highlighted cell must be white.

Nurikabe algorithm 15

Nurikabe algorithm 15

The clue of size 2 at the left of the grid has two choices for the one cell it requires for completion. Which ever one it chooses the highlighted cell must be black.

Nurikabe algorithm 16

Nurikabe algorithm 16

Squares of four black cells are forbidden. The three cells immediately to the left and below the highlighted cell could form a black square. The highlighted cell is the only access from a clue cell to this potential square, so it must be white.

Nurikabe algorithm 17

Nurikabe algorithm 17

Squares of four black cells are forbidden so either the highlighted cell or the one above it or both of them must be white. The only access to them from a clue is through the highlighted cell, so it must be white.

Nurikabe algorithm 18

Nurikabe algorithm 18

The highlighted cell touches white cells from two different clues (5 and 2). White cells from different clues cannot touch so this cell must be black.

Nurikabe algorithm 19

Nurikabe algorithm 19

No clue can reach the highlighted cell so it must be black.