nonogram

A nonogram, also known as a paint by numbers puzzle or agriddler, is a puzzle in which the solver must reconstruct apicture drawn in a grid using clues which give the distribution ofpixels 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 whitenonogram:

Figure 1: A nonogram in its unsolved state.

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

For instance, the clue for the first row is $(1,1)$. Since there aresix different ways of selecting two nonadjacent squares in a row oflength five, we cannot yet conclude anything from this clue. The nextclue, $(5)$, indicates that the second row is completely filled inwith black squares. Such clues are rare on real puzzles. Slightlymore common are clues such as the fourth row clue $(3)$. Although wecannot yet know precisely where the run of three black squares ispositioned, by the pigeonhole principle the middle square of that rowmust be black. Finally, since two runs of black must be separated byat least one square of another color, the clue $(2,2)$ tells us thatthe fifth row has two black squares followed by a white square andthen 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 moreuseful information. For instance, the first vertical clue says thatthe first column has exactly two black squares, and we have alreadydrawn two squares in that column, so the other three squares must allbe white. By using the positions of the squares in the second andfourth columns we can finish those columns as well. By using onlyvertical 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 musthave two black squares while the third row only has one. In the fifthrow we therefore place a black square in the first position and awhite square in the third position.

Figure 4: A solved nonogram.

We are done.

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

Figure 5: An ambiguous nonogram.

Logic puzzles with multiple solutions can be interesting formathematical reasons, but they are unacceptable as puzzles. Theproblem of determining whether a puzzle has a unique solution issometimes 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 allowingmore colors to be used in the picture. The clues then must indicateboth which non-background colors appear in which order in a row orcolumn and how long each run is. Another generalization is to use anon-square grid. For example, there are triddlers, which arenonograms on a grid tiled by equilateral triangles and which thereforerequire clues for three directions. One could also imaginegeneralizations to higher dimensions, leading to building-blocksculpture puzzles and the like.