GCHQ throws down the gauntlet

A while back I found the GCHQ Director’s Christmas card, which came in the form of a nonogram. GCHQ has a history of puzzle setting and even hiring people through puzzles. The WWII codebreakers were hired through crosswords and other puzzles in the newspaper, which was featured in The Imitation Game.

I was new to nonograms, but quickly found out they’re a “paint by numbers” puzzle where hints for rows and columns give you series of segments (of varying lengths) to colour in. Applying all the clues together logically lets you work out whether each cell is filled in or empty progressively until you reach the final solution.

Typically you then have a badly pixelated picture of something and a sense of accomplishment. With GCHQ’s puzzle, you end up with a QR code that leads you to the next puzzle. So the picture is not very pretty and the sense of accomplishment is short lived. Here’s what GCHQ’s best Christmas wishes look like:

And I thought I was bad at Christmas cards.

Challenge accepted

I didn’t like the idea that a Christmas card might be smarter than me, so I decided to write a program to solve it. Writing the solver took a lot longer than I thought, mostly because I didn’t stop when I had solved this single puzzle. And then I just got stumped on the later GCHQ puzzles anyway. So the sense of accomplishment was fleeting, and I don’t have a job offer from GCHQ. But I’m sure it was at some point fun.

The first thing I had to do was work out how to actually solve one of these things. Doing it by hand wasn’t too hard, apart from the disastrous consequences of getting a cell wrong. Five torn up copies of the puzzle and a few hours later it was solved, and I had an idea how to approach a solver.

The approach mostly involves identifying commonalities between the various ways a row or column could be laid out. For example, a segment of length 5 that needs to fit in a space of 6 cells can either have an empty cell at the start or end. In either case, the middle 4 cells will be filled. Applying that known information to other lines in the puzzle provides avenues for progress.

Some rows and columns in the original puzzle are already deterministic – they have no room for extra spaces and so there’s only one possible way to lay them out. These are the best place to start, as they give you a lot of cells for free. For example, the third column has enough segments of enough length that there’s only one way for them to fit in the column.

Initial approach – the brutest of force

The first thing I needed to be able to do was to work out the possible layouts for a row/column, given its clues and the current state of the puzzle. The initial approach was:

• Take the list of segment clues for the line and work out how many extra empty cells are needed to fit the whole line
• Generate all possible distributions of those spaces between the segments
• Check each possible layout against the board state to find any contradictions – filter these out

From here it’s pretty simple to solve the puzzles. Given all possible layouts for a line, if a certain cell is filled in every possible layout, or empty in every possible layout, then you’ve found its actual state. The solution continually evaluates this approach until the puzzle is solved.

The run time to solve GCHQ’s puzzle was 6.5 seconds. The foe was vanquished.

The need for speed

I knew that the solution was pretty inefficient. The problem is that the search space of possible layouts can be huge, and the filtering is done after generating all of the layouts. For example, the puzzle has this row:

This row needs an extra 12 spaces around and between the 4 segments, which yields 6,188 possible layouts. If the first cell happened to be already filled, it’s wasteful to generate all the possible layouts that start with an empty cell only to filter them out later.

I revised my approach to prune the search space as early as possible. Now it worked like so:

• Maintain a set of possible layouts, starting empty
• Navigate each cell from the start of each line
• If the cell empty or unknown, try the cell as empty and recurse
• Also, if the cell is filled or unknown, try the cell as filled and recurse
• If the end of the line is reached, a valid layout has been found – add it to the set

Applying this approach brought solve time down from 6.5s to 0.07s – almost a 100x speedup. GCHQ was on the ropes.

Simulations – fake it till you make it

The puzzle has a set of cells already filled in as a starting point, like pre-filled numbers on a Sudoku board. These aren’t needed to find a solution, but they are needed to make sure there’s only one valid solution. As the solution is a QR code, it wouldn’t work well if there was more than one valid QR code you could end up with. So the pre-filled cells make all but one of the solutions impossible.

Taking the pre-filled cells away, the puzzle becomes harder because now there are some cells that can’t be evaluated to a single state based solely on the current board state and the clues. Here’s what the solution looks like without the pre-filled cells:

Note the question marks – these are cells that can’t be worked out just by reducing the number of row/column possibilities. The solver needs to simulate their state to see if it can lead to a solution. Moreover, the simulation has to be recursive – trying a certain cell state may not resolve all of the remaining unknown cells.

So each simulation may lead to multiple sub-simulations. I could see where this was heading – an exponential run time. Well, Wikipedia does say that it’s an NP-Complete problem. This is another area where the right approach will be one that cuts down search space.

Finding inspiration

About this point, I ran into Twan van Laahoven’s blog on writing a nonogram solver in Haskell, which is a really well written walk through of a nice solution. I could mostly follow Twan’s solution even though I can read Haskell about as well as I can read Japanese. Twan also had a great puzzle in the shape of a lambda, which I summarily borrowed the clues for and stuffed them into my hacked up C#.

It turns out that the lambda puzzle is a good exercise for simulation, as there’s only one valid solution, but the solution requires quite a bit of simulation to find. Here’s what it looks like, with the cells that were simulated to reach the solution highlighted:

Honing the simulation approach

My early simulation attempts indeed found the correct solution for the lambda, but they found it thousands of times by simulating many different combinations of cells that just ended up with the same result. That’s not especially efficient. You could probably go as far as calling it inefficient. Or worse. Sprinkling some dynamic programming into the code helped, but couldn’t fix what was a broken algorithm.

The approach I settled on was to take the set of unknown cells and filter it down recursively. Each simulation takes a cell from the remaining set of unknowns and simulates it being both filled and empty. If the simulation doesn’t fully resolve the puzzle, it recurses with the remaining set of unknown cells. This is basically a depth first search through the possible solutions.

It was far more efficient than my early attempts, and the duplicate solutions disappeared. Running time for the lambda puzzle dropped from 1.4s to 0.04s. Surely this was victory most supreme.

Don’t get cocky, kid

I found an interesting survey of different nonogram solvers. I read far more than I’d ever wanted to know about solving nonograms and started to wonder how mine would stack up.

The 9-Dom puzzle is an interesting one because the information is very sparse, and a brute force solver will be forced into a very costly evaluation to find the solution. It’s also hard for a human, but a human will eventually work out the pattern that must apply to the whole puzzle. Or they’ll read the discussion forum and learn the pattern from other people, like I did.

Unfazed, I threw the puzzle at my firmly industrialised solver. After a few minutes without a solution, I hit the kill button. The fastest solver in the survey found the solution in just 1.8 seconds.

Calling it a day

The truly fast solvers have algorithms to pick good simulation candidates based on how much of the board is resolved by simulating a particular cell. Some try simulating multiple cells, picking the one that resolved the most cells and continuing from there. That’s an approach I’m interested to try, but it’s a problem for another day. I’d beaten GCHQ thoroughly (but briefly), and that was enough for me.

If you’re interested in the series of GCHQ puzzles and approaches for solutions, there’s a Reddit thread full of short cuts to cheat through puzzles you’re stuck on spoilers of impressive solutions that makes an interesting read.