Sample nurikabe puzzle (solved)

Nurikabe

Generating and Auto-solving

Nurikabe is a logic puzzle I came across in a puzzle magazine I got for Christmas (thanks Mom P!). They're a lot of fun. See here for a description/tutorial, and here for an explanation of this interesting Japanese word.

Since there were only five puzzles in the magazine, I started thinking about how a computer program could generate nurikabe puzzles. It shouldn't be hard to generate nurikabe "mazes" that satisfy the game constraints. However, like most logic puzzles, it seems like the hard part of generating nurikabe is guaranteeing that the ones you produce are solvable. For that, the only way I know is to try to solve them, whether manually or by writing an auto-solver. So below is a draft of some rules for an automatic nurikabe solver to follow. This would be a fun program to write!

According to Brandon McPhail's thesis, nurikabe is NP-complete. What does this imply for writing an auto-solver? That for sufficiently large puzzles, if we wanted to do an exhaustive search for solutions, it would take much longer than we can afford to wait.1 (Or else we make computer science history by solving an NP-hard problem in polynomial time.) Does this mean that writing a nurikabe solver, and possibly generator, is a lost cause? Theoretically, perhaps, but practically, I don't think so. When I solve a nurikabe puzzle by hand, it doesn't take me exponential time. I don't go six levels deep into hypotheses in order to find out what square to color black or white next. Usually there are deterministic ways to move forward, i.e. you can eliminate possibilities without much searching through potential moves. (Of course, this may be because the puzzles I try to solve are those invented and tested by humans to be not-too-hard for humans.) My hope is that using mostly deterministic methods, an auto-solver can either solve the puzzle in a reasonable amount of time, or give up. A non-exhaustive solver won't be able to prove in every case whether there is exactly one solution to a puzzle, but maybe in most cases, or many cases, it can do a good enough job by doing this reduced task: showing that there is exactly one solution reachable by a fairly thorough application of a set of mostly-deterministic methods typical of what a human is likely to be able to use. I.e. showing that the puzzle is not too hard, which is really in some ways better for what I want (making puzzles for humans) than showing that the puzzle is has exactly one solution.

One question that arises about the generate-and-auto-solve approach is, how efficient will this be? What proportion of well-formed nurikabe puzzles are solvable? Will I have to generate 100,000 puzzles to find one good one? I have no idea what the answer is. If the proportion of good ones is small, would generation heuristics help much? E.g. if the islands are kept fairly narrow, will that help? One could look at a collection of human-designed nurikabe puzzles and try to come up with heuristics.

Maybe an approach from a different direction would yield better results. Instead of (1) generate a random, well-formed nurikabe puzzle and then (2) check how solvable it is, maybe it would be possible to generate a solvable puzzle from the beginning, something like this: start with a blank puzzle, and keep adding clues until it becomes solvable by deterministic methods. I'm not sure of the details of how this would work.

Nurikabe software

There is a free nurikabe-player program for download here (slow connection). It has some predefined puzzles and lets you solve them (assisted by some convenient "smarts"), save progress, and create your own puzzles manually. There is another freeware nurikabe program for Palm here. I haven't played it, but it seems to do the same thing. Neither offers an auto-solver or a puzzle generator. Online nurikabe puzzles can be found here.

Nurikabe constraints

A nurikabe puzzle must conform to these laws:

Corollaries:

Nurikabe-solving rules

OK, now some rules for solving nurikabe:

These rules are roughly in order of increasing difficulty to apply.

Please let me know of any corrections, improvements, or additions you can think of for the above rules.

Method of applying rules:

(Much of this method is probably applicable to solving many logic games.)

Implementation

Objects:

Operations (methods):

Solver implemented!

Hooray! I finally got a nurikabe puzzle solver implemented. It really wasn't that tough, but took a while. My thanks to Dr. Drake at Lewis & Clark College for his Final Project: Nurikabe. The skeleton Java code there gave me the impetus to go ahead and do it.

The solver uses about seven production rules, i.e. rules that can potentially deduce the color of certain cells without doing any trial-and-error. It applies those rules repeatedly until they no longer yield any results. Then it makes a hypothesis about a given cell being a given color. If that hypothesis leads to a contradiction, it concludes the cell must be the opposite color.

The solver is successful to a degree: it solves small-to-medium puzzles very quickly. The one at the top of the page took it about half a second. But there are puzzles it has not yet solved, such as this 24x14. However, I'm getting some optimization done, and I'm hopeful that the envelope can be pushed back a ways. I think the biggest way to improve solving time is to pick your hypotheses more intelligently: If you pick one that quickly leads to a contradiction, you've made solid progress.

Creating Puzzles

My original intent for a Nurikabe solver was not to solve puzzles per se, but to assist in creating them. The last few days, I've made my first attempts at creating my own puzzles. Here they are (via Otto Janko's Java applet):

Help for the Java applet can be found here. Note, the save/load state feature does not work. I'm not sure why.

I used the Nurikabe player program by Oleg Andrushko to create and test the puzzles. Each puzzle is also wife-tested for quality assurance. Kathy's getting pretty good at Nurikabe!

As you might expect, the process is trial-and-error: scatter some numbers around, and try to solve the puzzle; if you find that there can't be a solution or there's not enough information, make adjustments. You usually have to try to solve it from scratch on each iteration, lest your changes have made some of the inferences you made last time invalid. So, I'd like to have the nurikabe auto-solver help with that repetitive solving part.

Recently I created a couple of Nurikabe puzzles on hex grids. Here they are. I don't know of an applet or any other player for such puzzles, so you'll probably have to do them on paper. Keep in mind that while a square-grid Nurikabe disallows a 2x2 block of black cells, a hex-grid Nurikabe prohibits a cluster of 3 black cells (which all share a common vertex).

Feedback

In response to my statement

What does this imply for writing an auto-solver? That if we wanted to do an exhaustive search for solutions, it would take much longer than we can afford to wait.

Adrian writes,

I'm not begging for a "who asked you?" response, but . . .

that's not really true for puzzles that are significantly small enough. For example, the three puzzles I've found on google [and the one on your web page] were solvable in a second [by the] program I wrote...

I responded,

OK, I stand corrected. I can't remember now what mental-back-of-the-envelope calculations I did, but it seemed like 2^100 was an awful lot, even with pruning.

and Adrian answered,

Well pruning is pretty serious. For a 10 by 10, you can jump down from 2^100 to 2^20 (about).

... I've looked around on the web some more (which is pretty slow because I'm stuck on dialup this week) and I've found a bunch of larger puzzles that (with my mental-back-of-the-envelope calculations) are way too big to do an exhaustive search on. Still, it works pretty fast on the small and medium sized puzzles.

(OK, I'm amending my original statement to say "for sufficiently large puzzles". --Lars)

I wrote the program in c and I really just wrote it as fast as I could type it in, so no design or OO or readability was considered.

Again, I take no credit for the readability of this program, but here it is:

http://aporter.org/nurikabe/

adrian


Jonathan wrote:

Hi Lars,

I learned of your interest in Nurikabe construction/solving after coming across your web page in a Google search. I've got a few ideas to share with you (but not a lot of time at the moment), but I did want to quickly point you to a link you might find interesting.

I think you may be reading too much into the McPhail proof of Nurikabe's NP-completeness. The fact is, NP-completeness doesn't say a whole lot about how efficiently you'll be able to autosolve in the average case, or even in the 99th percentile case. All it says is that as you scale up Nurikabe, there will exist some problems that are polynomial-intractable. These *could* be common, but they could be extraordinarily rare, too. Check out http://citeseer.ist.psu.edu/cheeseman91where.html for an excellent exposition of the relation between NP-completeness and "hardness".

I responded:

Thanks for the pointer. I'm reading the Cheeseman article with interest. I wonder if we can identify "order parameters" for Nurikabe that indicate how hard it will be to solve a particular problem?

Looking forward to hearing any ideas you have to share.


Again, please contact me if you have ideas or comments about the above, or just find it interesting.

Nurikabe Links


Written Mar. 9-10, 2005; updated May 12, 2007