OddThinking

After the recent discussions about Sudoku, Richard A. described to me another Japanese puzzle with a similar style. It goes under various names: Tsunami (perhaps an unfortunate name in 2005), Paint-by-Numbers (another unfortunate name), Nonograms and Griddlers, and more! I am calling them nonograms, because it is the name I find least embarrassing.

The concept is kind of odd. There are various descriptions on the web. Let me add my own description to the mix, using all of the computer jargon at my disposal.

Start with a small bitmap of a mystery icon – say 15×15. Using only a 1-bit bitmap is traditional, but not required. Use of limited colours is recommended. Use of white as one of those colours is mandatory.

For each row, summarise it with run-length encoding. That is, summarise sequences of pixels of the same colour with a description of the colour, and the number of pixels in a row of that colour. Do the same for each column.

Hide the pixels, but leave the encodings. So now you have an empty grid, and two sequences of encodings, each with a list of (colour, run-length) pairs, acting as clues. The puzzle will be to reconstruct the bitmap from the clues.

So far it is easy. You have enough information to reconstruct the bitmap perfectly. In fact, you have redundancy; there is twice as much data as you need. You could encode it with the row clues alone or with the column clues alone.

So, here is the sneaky part that makes it a challenging puzzle: Remove from your two lists all of the encodings describing runs of white squares.

The result is two partial descriptions of the picture, from which (hopefully) you can still reconstruct the bitmap with a little bit of logic.

Like Sudoku, there is a lot of elimination. There is very little arithmetic involved (although there is some, unlike Sudoku.)

This description may not be satisfying, so here are some reference sites with online versions of it to get a feel for it.

• Griddlers.Net -Probably the best site, with some interesting variations, and sophisticated user interface.
• Online Tsunami – first site I found, colour images, large database, mediocre usability.
• The Activity Workshop’s Nonograms – black-and-white, small selection, better usability
• Cool Nonograms – black-and-white, medium-sized database, very plain user-interface
• Wikipedia entry on Paint By Numbers – includes a description, and links to more sites with links to puzzles.

Go ahead. Spend 20 minutes playing a few games. When you have finished, come back and read a follow up article about how I solved them algorithmically.