nonogram

A nonogram, also known as a paint by numbers puzzle or a griddler, is a puzzle in which the solver must reconstruct a picture drawn in a grid using clues which give the distribution of pixels in each row and column.

The simplest nonograms use two colors, white (usually the background) and black (usually the foreground). Here is a sample black and white nonogram:

The numbers to the left of a row indicate how many runs of black squares there are in that row and how long each such run is. The numbers above a column serve the same purpose for that column.

For instance, the clue for the first row is $(1,1)$. Since there are six different ways of selecting two nonadjacent squares in a row of length five, we cannot yet conclude anything from this clue. The next clue, $(5)$, indicates that the second row is completely filled in with black squares. Such clues are rare on real puzzles. Slightly more common are clues such as the fourth row clue $(3)$. Although we cannot yet know precisely where the run of three black squares is positioned, by the pigeonhole principle the middle square of that row must be black. Finally, since two runs of black must be separated by at least one square of another color, the clue $(2,2)$ tells us that the fifth row has two black squares followed by a white square and then two more black squares.

Applying the information we have so far yields the following picture.

With some of the squares filled in, the remaining clues give us more useful information. For instance, the first vertical clue says that the first column has exactly two black squares, and we have already drawn two squares in that column, so the other three squares must all be white. By using the positions of the squares in the second and fourth columns we can finish those columns as well. By using only vertical clues, we can finish every column but the last.

To complete the puzzle, we appeal to the fact that the first row must have two black squares while the third row only has one. In the fifth row we therefore place a black square in the first position and a white square in the third position.

We are done.

Given a picture, it is straightforward to generate the clues for that picture: simply determine for each row and column the lengths of the runs of the non-background colors. However, it is not always straightforward to recover the picture from the clues, and a designer can exploit this fact to make puzzles of varying levels of difficulty. A challenge facing the designer is the fact that not every puzzle has a unique solution. In particular, if we view solutions as rectangular matrices with entries $0$ and $1$, where $0$ represents the background color and $1$ the foreground color, then any 5-by-5 permutation matrix is a solution to the following puzzle.

Logic puzzles with multiple solutions can be interesting for mathematical reasons, but they are unacceptable as puzzles. The problem of determining whether a puzzle has a unique solution is sometimes called the Another Solution Problem, or ASP, and is known to be NP-complete for many puzzles, including nonograms.

Nonograms as we have described them can be generalized by allowing more colors to be used in the picture. The clues then must indicate both which non-background colors appear in which order in a row or column and how long each run is. Another generalization is to use a non-square grid. For example, there are triddlers, which are nonograms on a grid tiled by equilateral triangles and which therefore require clues for three directions. One could also imagine generalizations to higher dimensions, leading to building-block sculpture puzzles and the like.

References

• 1 N. Ueda and T. Nagao. NP-completeness results for NONOGRAM via parsimonious reductions. Technical Report TR96-0008, Department of Computer Science, Tokyo Institute of Technology, 1996.
• 2 T. Yato. Complexity and completeness of finding another solution and its application to puzzles. Thesis in information science, the University of Tokyo, 2003
 Title nonogram Canonical name Nonogram Date of creation 2013-03-22 17:09:21 Last modified on 2013-03-22 17:09:21 Owner mps (409) Last modified by mps (409) Numerical id 8 Author mps (409) Entry type Definition Classification msc 68Q17 Classification msc 15A36 Classification msc 05B99 Classification msc 00A08 Defines paint by number Defines griddler Defines another solution problem Defines ASP