A little puzzle experiment

Here’s a thing I’m working on:

Screenshot of WIP islands game

The aim is simply to classify each square on the grid as either land or water. Your clues consist of the following:

  • A list of all islands in the grid. Islands are four-connected: two squares that touch only on their corners do not connect.
  • A set of indicators in the playing field. Currently a bit cryptic: # means this square is land, ~ means it’s water. The number underneath indicates how many neighbours (again four-connected) are land.

With that knowledge, can you solve the puzzle in the screenshot above? Spoiler: here’s the solution.

Solution

I could describe it as a mix between Minesweeper and nonograms two because it has both the “global” clues from the nonogram, and the “local” clues from Minesweeper.

Minesweeper
Nonogram

Today I wrote the above glorious GUI, as well as a generator and solver for these kinds of puzzles. I had to have a generator to test whether it’s fun, because I can’t properly test a puzzle whose solution I just created five seconds ago.

The generator is fairly straightforward:

  1. Generate some random island sizes.
  2. While the solution is not unique, add a random clue to a random square. If this results in an unsolvable puzzle, retry with another random clue.
  3. Remove as many clues from squares as possible without the solution becoming ambiguous.

It has to work this way (rather than starting with a solution) because if we generate some clues to point towards an existing solution, we have no way to know whether that solution will be unique.

The solver is mostly brute-force. Making it more intelligent would mean encoding more knowledge about types of clues, but I wasn’t sure which ones I wanted, so keeping it generic paid off. It precomputes a set of polyominos for each island size, which is smaller than you might think, for example for size 7 (note that mirrored and rotated versions are not in the figure below):

All heptominos
(source: Wolfram MathWorld)

Then it just tries placing all of these in all possible positions without overlapping or touching, and finally checks whether all the clues are satisfied. It seems to be fast enough for 3 medium-sized islands on a 5x5 grid, or 2 small islands on an 8x8 grid.

More importantly, these sizes already make for interesting puzzles. I think I’ll develop this further into a mobile game, with maybe 30 or 50 levels for free, and additional packs available via in-app purchase. If I tweak the generator a bit more, creating extra content will be a breeze.