OddThinking

Preface

Before reading this article, you should read about Nonograms and also my approach to using software to solve puzzles, once and for all. Once you have done that, it will be no surprise to you that, having tried a couple of Nonograms (or whatever you want to call them), I analysed the problem with a view to producing software that automatically solves it.

First, a definition. I called each “run” or sequence of a single colour (including white) a Segment. Segments can run horizontally along a row, or vertical down a column.

It is clear that there is a strong element of elimination and refinement in this puzzle. For example, if a particular pixel’s column has only white and black segments, and the same pixel’s row has only white and red segments, then that pixel must be white. That in turn means that the black vertical segment cannot run through it, and it might now be restricted to a smaller area – perhaps only one possible location, below. That in turn, means several other pixels that used to be either black or white, is now definitely black, which means they could further limit the horizontal segments, and so on.

Categorising the Puzzle

I hypothesized that there were several possible categories of nonogram.

1. Completely ambiguous nonograms, where the clues do not uniquely select a single bitmap. It might be possible to find several solutions.

2. Contextually solvable nonograms, where the human solver can see the big picture of the scene being represented and can accurate determine which solution is appropriate, or otherwise use heuristics to perform educated guesswork.

3. Simple nonograms that fall to simple rules of elimination, albeit applied repeatedly.

4. Dull nonograms, solvable only through brute-force and/or guesswork – e.g. that solving nonograms is NP-complete.

I still didn’t know which of these categories actually existed.

The risks were two-fold.

1. If typical nonograms where only contextually solvable, I would lose the fight to automate it.

2. If typical nonograms were dull (by my definition above), I was going to get bored of this puzzle-solving project very quickly.

I tried to come up with examples of each of the categories, to prove they existed.

Completely Ambiguous

Image a 2×2 bitmap. The clues for both rows and both columns are the same: one Black segment of length 1. This simple example is ambiguous. There are two possible solutions (left as a brief exercise for the reader).

Contextually Solvable

This was a big concern.

Some of the puzzles I solved involved pictures that were bilaterally symmetric. That was obvious from the clues at the top, but that is not rigorous enough rule for the computer to adopt it; it counts as a heuristic used to help guess well, rather than a rigorous rule to solve the problem.

Similarly, pictures normally contain large blocks of colour – two parallel orange segments are probably lined-up or at least overlapping. Again, this is only a heuristic.

If you were halfway though a puzzle, and you realised it was a face, could you use your knowledge about faces to guess that the ears are lined up between the top of the eyes and the bottom of the nose?

Is it possible that some puzzles are only solvable by using this type of heuristic?

“Yes” is the answer. Again, let’s use the 2×2 ambiguous example from above. Most Nonograms have names. If this nonogram was called “Positive Gradient”, surely it would no longer be ambiguous.

Simple Nonograms

These certainly exist. The 1×1 bitmap with a single black dot is a simple nonogram, solvable through elimination. Playing with my first few nonograms suggested that they weren’t uncommon.

Dull Nonograms

This was a tough one. Can you come up with a nonogram that after running through simple elimination rules remains elusive, but with some more mental power you can solve?

I failed to produce any examples, or any reason why such examples might not exist, and this remains an open question.

It is hard to answer this until you work out what the simple elimination rules might look like.

Elimination Rules

I pondered how the elimination rules might work. I came up with a set that seemed powerful enough, but they don’t map very closely to how a human solves the puzzle.

Instead, the software creates lots of objects that each take a local view of the world, and share that view only with their nearest neighbours. In turn, the neighbours adjust their own local view of the world, and pass that knowledge on to their neighbours in turn. Eventually filtered knowledge spreads, and (hopefully) every pixel knows it can only be one colour.

There are two types of objects in this model.

The pixel object represents a single coloured cell on the bitmap.

The segment object represents the part of a clue describing a single run and its colour. Segment objects may also represent the (invisible) white segments.

Pixel Object

Each pixel keeps track of two sets of segments that could possibly be covering it – the horizontal segments and the vertical segments.

These sets start out including every single segment appropriate for that row and column, respectively, but they slowly shrink in size as the pixel learns more, until, hopefully, each set only contains one item.

When triggered, the pixel finds the common set of colours that the horizontal and vertical segment sets contain, and inform the other segments that they can no longer be supported.

For example, if the set of horizontal segments for a pixel includes only a red one and a white one, and the set of vertical segments includes only a blue one and a white one, then the pixel itself must be white. The red segment and blue segment are notified that they cannot cross this pixel.

Segment Object

The Segment object is significantly more complex.

The segment contains a colour and a length.

The segment also contains a reference to its immediate neighbours (left and right in the case of horizontal segments, up and down in the case of vertical ones).

For every row and column, the clues about coloured segments are taken and a chain of segment objects are created, with a special variable-length white segment placed between every coloured segment and on the ends.

For example, if the grid-size is 15 and the clue is:

5 (blue), 3 (red), 2 (red)

then the chain of segments created is:

1. White segment, length 0-15
2. Blue segment, length 5
3. White segment, length 0-15
4. Red segment, length 3
5. White segment, length 1-15
6. Red segment, length 2
7. White segment, length 0-15

Some items of note here:

• The coloured segments have a fixed length.

• The white segments, having no explicit clues, are of an unknown length, ranging from zero to the size of the grid.

• Where a white segment appears between two equally coloured segments, it must not be zero length, or the two other segments would merge together.

The segment contains a sequence of pixels representing the whole row or column. For each pixel it keeps track of:

• whether that pixel is compatible in colour (i.e. false if the pixel has ever notified the segment that it is not suitable)

• whether the segment can start on this pixel, and if so how long it is (actually a set of possible lengths)

When triggered, the segment walks through all the possible positions it could start in and all the possible lengths it could be (for white segments), and calculates three sets: the possible starting points, the possible ending points and the pixels possibly covered.

If there are changes in these sets from the last time it calculated it, it notifies the interested parties:

• its left/up neighbour is informed of the current segment’s possible start positions

• its down/right neighbour is informed of the possible end positions.

  That way they can eliminate any of the options that are impossible due to a gap or overlap in neighbouring segments.

• where a pixel has been eliminated from the possible coverage of a segment, the pixel is notified.

  That way, the pixel can remove this segment its set of possible segments

Results

First, a surprise to me, while tackling this problem, was that the puzzles with lots of colours are easier not harder. In hindsight, it is obvious. Colour is extra set of clues that you are getting about how the horizontal and vertical segments fit together.

I have implemented these rules, and have submitted a total of five puzzles to the software:

• two trivial invented ones for testing

• one simple one (10×10, two colours)

• one moderately easy one (15×15, three colours)

• one moderately hard one (15×15, two colours)

The software has solved every single one, using just these rules of elimination.

Conclusion

I have shown that there completely ambiguous and contextually solvable nonograms in existence, but they are not present in the small sample of published nonograms I have tried.

I have not shown whether or not dull nonograms exist, but again they are not present in the published sample I have tried, and I haven’t been able to come up with any.

I would like to try it on more puzzles, including a 50×50 version. The bottleneck is the time take to type in all the fiddly little clues, accurately – it makes me go cross-eyed trying to get it right.

Nonetheless, following the lead of Adam Savage, I am going to impatiently skip any further rigour, and declare this one Busted.

[Update: I have now followed this up with a sequel article discussing more about the software implementation details, as opposed to the general approach used to solve the puzzle.]