Solving the Sunday Telegraph's Griddler using Python

29 November 2009

For many years now, The Sunday
Telegraph has published a grid-based puzzle each week. Originally
this was called a Nonogram, although it is now called a
Griddler.

Basically, you are given an empty grid (typically 30 × 35 squares)
together with the pattern of filled squares for each row and column of the
grid. For example, for the first row this might be "5.3.10" meaning that
there are three blocks – of lengths 5, 3 and 10 respectively –
each separated from each other by one or more blank cells, and from the edge
of the grid by zero or more blank cells. The objective of the puzzle is to
reconstruct the original picture (the filled cells on the grid) by using the
information about the block lengths.

I was recently inspired by a presentation by Michael Foord showing an
elegant solution by Peter
Norvig to the problem of finding "did you mean this?" alternatives to a
search term in a search engine using surprisingly few lines of Python.

I saw a parallel between generating the alternative spellings and
generating the possible fits of blocks in a row or column of a grid. I decided
to write a Python program using this technique (syntax colouring courtesy of
Vim).

The algorithm, which generates every possible fit, is slower than some
of the alternative ways of tackling this type of puzzle. In particular, it
probably doesn't scale very well. However, it does work in a few minutes for
the standard size of puzzle, and the code is reasonably concise.