Nonogram

This is the Nonogram Puzzle, also known as Crucipixel, Paint by Numbers, Griddlers, and other names.

The objective is to paint cells to form horizontal and vertical strings. The length of each horizontal string is prescribed by the number on the left. The length of each vertical string is prescribed by the number on the top.

For example, the third row must have three strings of filled cells, the first with length 2, the second with length 4, and the third with length 2 (the order must be preserved).

Finally, there must be at least one empty cell between any two horizontal/vertical consecutive strings.

 
 
Nonogram Puzzle
 
 

Source: Integer Programming Book.

 
 

Diving Deeper

  • What makes the Nonogram relatively hard to solve by hand is that we need to consider information from rows and columns at the same time.

    Computers are generally good at handling multiple sources of information concurrently, but for humans, this can be quite challenging.

    Nevertheless, in a small puzzle like this, some rows or columns may provide especially useful information that we can use in a logical way to cut down possibilities and converge to some conclusions, after which the problem becomes easier.

  • In a sense, the Nonogram is a baby version of the system behind a tomography machine. Signals sent in multiple directions, two directions in the case of the Nonogram above, provide partial information of an object, such as a tumor, or a 2D image in our case.

    Reconstruction of objects from partial information (often called projections) is a subject of an active field of research called inverse problems. And tomography is just one example of an inverse problem.

  • Nonogram is a classic example in mixed-integer programming textbooks but there are so many other alternatives out there. Visit the Nonogram page on Wikipedia for a comprehensive list of solution techniques.