This is the archive of the old posts from Djape .Net, more or less as they used to be. Please go to djape.net to see the new website.

My first Nurikabe puzzle (a difficult one)

Another addition to my portfolio of various number/logic puzzles are 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!)

Difficult Nurikabe book


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!
This entry was posted in Free sample puzzles, General, Puzzle variants and tagged , , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

12 Comments

  1. wellbeback
    Posted July 22, 2009 at 5:53 am | Permalink

    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.

  2. Para
    Posted July 22, 2009 at 6:18 pm | Permalink

    It’s an okay puzzle. Definitely not a “difficult one”.
    Your rules description is really awkward though.

  3. Posted July 22, 2009 at 8:19 pm | Permalink

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

  4. nlgold
    Posted July 22, 2009 at 11:21 pm | Permalink

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

  5. Posted July 23, 2009 at 12:40 am | Permalink

    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.

  6. rgeorge
    Posted August 9, 2009 at 6:38 am | Permalink

    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?

  7. Posted August 22, 2009 at 11:57 am | Permalink

    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!

  8. Posted August 24, 2009 at 10:49 pm | Permalink

    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” 😉

  9. rgeorge
    Posted August 26, 2009 at 5:43 pm | Permalink

    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

  10. udosuk
    Posted August 28, 2009 at 9:10 am | Permalink

    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. 💡

  11. ghalf
    Posted November 4, 2009 at 1:55 pm | Permalink

    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)

  12. ghalf
    Posted November 4, 2009 at 1:59 pm | Permalink

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

    .. and some others that are connected diagonally?

    thank you

2 Trackbacks

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*

This site uses Akismet to reduce spam. Learn how your comment data is processed.

eXTReMe Tracker