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:

Figure 1: A nonogram in its unsolved state.

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.

Figure 2: The nonogram after some clues have been applied.

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.

Figure 3: The nonogram in a nearly complete state.

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.

Figure 4: A solved nonogram.

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.

Figure 5: An ambiguous nonogram.

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.

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