Nonograms

According to the UK's "Sunday Telegraph" newspaper: "Nonograms are puzzles from Japan and are currently published each week only in The Sunday Telegraph. Simply use your logic and skill to complete the grid and reveal a picture or diagram."

Essentially, each row and column of a rectangular bitmap is annotated with the respective lengths of its distinct strings of occupied cells.

The puzzlee must complete the bitmap given only these lengths:

is solved as:

Published puzzles are larger than this, e.g. 25 x 20, and apparently always have unique solutions.

This suggests some meta-puzzles, e.g.

1. What is the simplest Prolog program to find solutions?

2. What heuristics and strategies can expedite the search?

3. How can we best implement these strategies in Prolog?

4. Can constraint-solvers express these strategies more elegantly?

I have some offerings for 1) and 2), am grappling with 3), and have a hunch that the answer to 4) is "yes".

Paul Singleton
paul@cs.keele.ac.uk