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