Grid shading by simulated annealing (or what I did on my holidays)

The UK spy agency GCHQ is often in the news for the wrong reasons and has recently been on something of a charm offensive to improve its tarnished image. This campaign includes stencilling job adverts on the pavement in the trendy Shoreditch area of London  and, more recently, setting a series of incredibly difficult puzzles for the general public to solve. GCHQ director Robert Hannigan included a grid shading puzzle in his Christmas cards that received wide attention in the UK press.

Hannigan’s grid puzzle is shown below. For each row and column, the marginal numbers show the length of each contiguous block of shaded squares, where the blocks are separated by at least one white square. Some of the squares have already been filled in. The problem is to find the unique shading pattern that is consistent with the row and column constraints.

gchq-puzzle

I wanted to solve the puzzle but did not want to sit down with a pencil and paper. So I decided to write an R program to solve it instead. Is this cheating? Crafty Alison seems to think so, but I was inspired by Christian Robert’s regular series of R-based solutions to the weekly Le Monde puzzle. He often uses probabilistic solutions to logical problems and I realised that this grid shading puzzle could be treated as a Bayesian inference problem.

For each row, the given constraints allow us to enumerate all possible block positions. For example, rows 7 and 22 are uniquely determined by the row constraints whereas rows 2 and 24 both have 18564 possibilities. The possible row and column configurations define our parameter space and I started by defining a uniform prior distribution over it, treating rows and columns as independent a priori. Then I introduced the constraint that the row and column configurations should be consistent via the pseudo log-likelihood NT where

  • N is the number of squares that are consistent between the state of the rows and the state of the columns (i.e. both shaded or unshaded).
  • T is a temperature parameter. T=0 gives independence between the rows and columns while large values of T give high likelihood to agreement between rows and columns

I call it a pseudo-likelihood because, although I am using the formalism of Bayesian inference, NT  does not correspond to any probability distribution. It is just a way to enforce a soft constraint that favours agreement between rows and columns.

Finally we need a way of exploring the parameter space of row and column configurations. I used an independence Metropolis-Hastings sampler (no need for cutting edge methodology here) starting with T=0 and slowly increasing T at each iteration to enforce agreement between rows and columns. A solution is shown below, derived in 4 minutes on my desktop and visualized using the R function image().

GCHQ-solution

I call it a solution and not the solution because the simulated annealing algorithm has not converged. The grey squares show where the row and column configurations do not match (i.e. a grey square is shaded according to the row state but unshaded according to the column state, or vice versa). But this does not matter. The solution is easily recognizable as a QR code, which has enough redundancy in its specification for this partial solution to work with a QR scanner. This was an unexpected advantage of my probabilistic approach.

Scanning the QR code took me to a web page containing more puzzles, and solving these led to further puzzles which were less accessible to brute force and relied instead on flashes of insight. This kept me entertained and away from the keyboard over the Christmas period so I was happy to make a donation to the charity NSPCC as requested by the puzzle setters. I reached level 5, the last level, and managed to solve some of the puzzles while others remained impenetrable. I had to give it all up when I came back to work but the puzzles remained open until the end of January, which is why I delayed this post until now.

We were invited to submit our partial solutions to the level 5 problems by email but I decided not to. Do I really want them to know I can crack their code? I think not.

 

Advertisements

One thought on “Grid shading by simulated annealing (or what I did on my holidays)

  1. Pingback: Grid shading by simulated annealing (or what I did on my holidays) | Hypergeometric

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s