In the fourth part of my video lecture series introducing the Standard Template Library, I walk through an extended example of using the STL to solve Nurikabe puzzles. It assumes that you've read Wikipedia's Nurikabe page, and that you've watched Part 1 (sequence containers), Part 2 (associative containers), and Part 3 (smart pointers), or that you're already familiar with those topics.
My original source code and output are available. I've been working on improving them, and I'm up to version 1.2.
In Part 5 (which was filmed back-to-back; it's in the editing pipeline), I'll explain how I implemented the advanced analysis in my Nurikabe solver, including the first breadth-first search that I ever wrote.
Stephan T. Lavavej
Visual C++ Libraries Developer
Thank you for this series of videos. I'm finding them very interesting even though I already have experience with the STL - I've picked up some useful techniques and it has been great to see some of the new C++0x features in action.
In the video you mention that your Nurikabe solver is occasionally forced to make a guess - the output above shows that this occurs in two situations when working on the Wikipedia puzzle. These are the methods I (as a human) would use in these situations - perhaps they could be added to the solver:
1. Consider the '3' at (zero-based) coordinates x=6, y=4. In order to form a white region of the correct size, this must expand either up then left or left (then left). Then, the cells bordering the resulting region must be marked as black. In both cases, the cell immediately below the '7' is part of this border: it must be black.
2. This situation is simpler: there is a single black cell still to be placed, and there are two disjoint black regions. The black cell must thus be placed where it joins the two regions: at x=3, y=3.
You're welcome! That's exactly what I was hoping for.
> These are the methods I (as a human) would use in these situations - perhaps they could be added to the solver:
One of the things that I learned while writing the solver is that it can be difficult to teach a computer how to perform analysis that's easy for a human (this is perhaps most obvious with confinement).
> 1. Consider the '3' at (zero-based) coordinates x=6, y=4.
Yep, that analysis is correct. However, it's not immediately clear to me whether it can be implemented efficiently, and if so, how. You're talking about imagining all of the ways that a partial island could be completed, and looking for any cells that are invariably known to be one color as a result. For an island of size 3, this is probably fast, but not for large islands. One of the interesting properties of my solver is that it can handle Nikoli's monster examples (with large islands); someone else at Microsoft wrote a solver that handles simpler examples faster than mine, but can't deal with the monsters, because it's sensitive to things like large islands.
> 2. This situation is simpler: there is a single black cell still to be placed, and there are two disjoint black regions.
Also correct, but I'm not sure how valuable special-casing that knowledge would be. (I did special-case "isolated unknown regions", because that came up early, and I could imagine it coming up elsewhere.)
If you have good ideas to make the solver smarter and faster, I encourage you to try implementing them!