# Nonograms

Call a row or column a line. Each line is marked by a sequence of numbers \((a_1,\,a_2, \,\ldots,\,a_n).\) We say that a line "has clues" \((a_1,\,a_2, \,\ldots,\,a_n),\) if it is marked by that sequence.

If a line has clues \((k),\) on a \(k \times k\) grid, then all cells in that line are shaded.

If a line has clues \((a_1,\,a_2, \,\ldots,\,a_n),\) on a \(k \times k\) grid, with

$$a_1 + a_2 + \ldots + a_n = k - (n - 1)$$then you can fill in the first \(a_1\) cells, leave one blank, fill in the next \(a_2\) cells, leave on blank, and so on. For example, on a \(5 \times 5\) grid, \((2,\,2)\) means 2 on, 1 off, 2 on. \((1, 3)\) means 1 on, 1 off, 3 on. Here's a picture of both:

If a line has clues \((a),\) then there are \((k - a) + 1\) possible ways to shade that line. For example, on a \(5 \times 5\) grid, if a line has clues \((4),\) then there are \(5 - 4 + 1 = 2\) ways to shade that line: shade the first 4, or shade the last 4. From this observation, we can also deduce that if \(a \gt k / 2,\) then the middle \(\lceil a - k / 2 \rceil\) cells must be shaded. Thus, on a \(5 \times 5\) grid, if a line has (4), then the middle $$(4 - 5 / 2) \cdot 2 = (4 - 2.5) \cdot 2 = 1.5 \cdot 2 = 3$$

cells must be shaded.

Here's an excellent video on solving "Crossing the Streams" nonograms, a variant invented by Grant Fikes.