**Nurikabe**puzzles. I think these puzzles are being undeservedly somewhat neglected in the puzzle world and I intend to change that. The number of solving techniques and approaches that can be found in Nurikabe puzzles far exceeds any other puzzle type. For me it was a challenge programming a solver and a generator of Nurikabe puzzles, much more than programming all other puzzles so far.

**Goal:**For each cell, determine if it must be white (draw a circle in it) or black (paint it). There are two types of Nurikabe

**jargon**: 1) White cells are

**walls**, black cells are a

**maze**. 2) White cells are

**islands**, black cells are a

**stream**.

## The Rules of Nurikabe

1. Cells with numbers (initial clues) are always white. 2. 2×2 (or bigger) blocks of black cells are not allowed. 3. All black cells must be connected orthogonally (horizontally or vertically). In other words: there is a maze between the walls. Or: A stream runs between the islands. 4. The initial numbers (clues) indicate how many white cells are orthogonally connected with the cell that contains the number (including that cell). In other words: the numbers indicate how big each island is; or again, how big each wall is. 5. White cells that “belong” to two different clues must be separated by black cells. In other words: two islands cannot touch each other, there must be some water between them. Or, two walls must be separated by the maze. 6. Nurikabe puzzles can be of any size. And finally, here is the puzzle. I’m still working on automagically determining the difficulty of these puzzles, but I think this one is quite tough.**Nurikabe 12×12**for July 20, 2009.

(click to download or right-click to save the image!) | |

**To see the solution to this puzzle**click here

Folks, I’d really like to hear what you think of Nurikabe puzzles in general and about this particular puzzle (the difficulty in first place). So, please do post your comments!

## 12 Comments

I looked Nurikabe up in Wikipedia since it wasn’t clear to me whether the white cell islands also had to be connected orthogonally within themselves. (They are). Thanks for introducing it to me. It wasn’t too difficult – took me about 15 minutes. It reminds me of Hidoku.

It’s an okay puzzle. Definitely not a “difficult one”.

Your rules description is really awkward though.

Thanks for your responses. I’ve updated the rules to include the jargon. Hopefully it is more clear now.

I completed this with a slightly different solution. I might have a rule violation. Can you have a 2X2 block of White cells?

Yes, nlgold, you CAN have a 2×2 block of white cells. If you think you have a different solution, please e-mail it to me and I’ll tell you if you’re right or not.

Pay attention to rule number 3 – it is often the one easiest to forget.

I’d be interested to know more about your solving and generating methods.

I have a solver that works by recursive descent, applying a set of static rules at each step. It took about 15 minutes to solve this making this by far the deepest puzzle of its size I’ve tried it on. (I solved it by hand in about 10.)

As for generation, I haven’t been able to do better than: generate a candidate maze by the usual methods; place numbers randomly; try to solve. Is there a more straightforward way?

rgeorge,

for the solver: yes, recursive descent is the way to go, however, this particular puzzle that I posted doesn’t require any recursive (backtracking) calls, it can be solved by iterative methods (repeatedly applying a set of solving methods). In fact, all my puzzles can be solved iteratively, otherwise, if you use backtracking, that is considered guessing. Therefore, you need to work on your solving strategies and implement and apply more of them.

For generation of Nurikabe puzzles, first of all you need a (very) fast iterative solver. Then, generate a random but valid maximum Nurikabe “maze”. By “maximum” I mean that you can’t add any more black cells. Mark the existing white cells with numbers randomly (there will almost always be only 1s and 2s for a “maximum” maze). Check if those numbers constitute a valid puzzle (they will almost always do). And finally, repeatedly remove one random black cell at a time, thus increasing one of the white “islands” (or joining two of them). Randomly place the number for this white island until you get a valid puzzle. If you can’t get a valid puzzle, replace the black cell and keep going.

I think this is the first time I ever explained any of my algorithms. ðŸ™‚ I don’t intend to further engage into discussion about this.

Good luck!

Thanks for sharing your algorithm for generating a puzzle… being a puzzle solver the world of puzzle creation was a complete mistery for me, you offered a quick glance “behind the curtains” ðŸ˜‰

Thanks! That just about describes my semi-manual method: sprinkle enough ‘1’s or ‘2’s around to make the board legal, then merge islands that look promising, and see if the solution stays unique and within reasonable reach, until the puzzle looks interesting.

I’ve improved my solver to where it will solve this puzzle in about 10 seconds, but still needs to do a little recursive descent to do so. Obviously my ruleset isn’t as good, but recursion is (so far) an OK stand-in for the harder-to-express rules.

One of the better ones I’ve come up with so far is this 9×9:

-, 4, -, -, -, 1, -, -, –

-, -, -, -, -, -, -, -, –

-, -, -, -, -, 1, -, -, 3

-, -, -, -, -, -, -, -, –

-, -, -, 4, -, -, -, -, –

-, -, -, -, -, -, -, -, –

-, -, -, -, -, -, -, 4, –

-, -, -, -, -, -, -, -, –

-, 1, -, 9, -, -, -, -, 10

Thanks rgeorge, the 9×9 puzzles you showed is very enjoyable, and I had to use all kind of tricks to solve it without T&E.

If anyone wants to discuss about it, feel free to post in the “Others” section of the forum. ðŸ’¡

There is something I donÃ‚Â´t understand about this kindo of puzzle, probably due to my difficulties with English.

If rule number three says that all black cells must be connected orthogonally

What about boxes (2nd row, 2nd column and 1 column third row)

Sorry pressed the wrong button (this follows the las comment)

.. and some others that are connected diagonally?

thank you

## 2 Trackbacks

[…] If you are uncertain about the rules of Nurikabe, read my Nurikabe introductory article. […]

[…] If you are uncertain about the rules of Nurikabe, read my Nurikabe introductory article. […]