# 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.