A Christmas Cracker!


Calling all aspiring spooks. Robert Hannigan, director of Britain’s security and intelligence organisation GCHQ, has included a rather tantalising puzzle with his Christmas card this year. He hopes that it will exercise your grey cells over the holiday period.

 

Snoopy-Christmas-peanuts-452770_1280_960If you can solve the puzzle, along with the others that it will lead to, you can email the solution to GCHQ (the Government communications headquarters) before January 31. A winner will be drawn from all the correct answers – and doubtless be named to much fanfare.

So what do you need to do to be in with a chance?

image-20151215-23202-jzr0rd

 

How to crack British intelligence service’s devilish Christmas puzzle

Graham KendallUniversity of Nottingham

The puzzle requires that you shade in squares on the 25×25 grid shown above. But which ones? Well, a few of the “black” squares have been completed for you, but most you will have to do yourself. By way of a clue, each row and cell has a sequence of numbers attached to it. The numbers represent a sequence of shaded cells, that need to separated from each other by at least one blank cell. For example, the row marked “7 3 1 1 7” should contain a sequence of seven shaded cells, followed by at least one blank cell, then three shaded cells, followed by at least one blank cell – and so on. The problem is made trickier because each horizontal row intersects a vertical column, each with its own sequence code.

Paper and pen

So how do you reach the solution? One way of cracking it is to resort to old-fashioned paper and pen. Just sit down, put on your thinking cap and try to reason it out.

It is not that difficult to get started. In fact, it is already started, and it is easy to fill in a few more squares. Take a look at row 22 on the horizontal axis – the one that has the sequence “1 3 1 3 10 2”. These numbers add up to 20 and as there are six blocks, you need at least five blank squares to separate them. As we only have 25 squares in the row, this pattern can only fit in one way – the first square in the row has to be shaded, and the rest just follow, with only one blank square between each run of shaded squares.

Are there any others like this? Column seven (“7 1 1 1 1 1 7”) sums up to 19. As we have seven numbers we need at six least separators. This also adds up to 25, so this row is easy to complete, too. The figure below shows the grid once we have filled in row 22 and column seven (the blank squares are marked in yellow).

State of grid after completing row 22 and column seven.

Any others where the row or column is also easy to complete? Yes, but I’ll leave it to you to find them.

Once you have completed the “easy” rows/columns, you then need to start looking for other ways of completing the remaining rows and columns, or even reasoning about individual cells. In many ways, it is like completing a Sudoku puzzle. You should find that you never have to guess, but perhaps using a pencil and having a rubber to hand might be a good idea.

One more hint, colour in the blank squares, too – just use a different shade. This might sound obvious but leaving a square blank, once you have determined that it “must” be blank, might mean that it gets mistakenly shaded later. You can see in the figure above that I’ve have coloured the blank squares yellow, so we know that we should not make them black later.

Getting mathematical

If you don’t want to exercise the brain, you can get a computer to do it for you.

Jean Francois Puget presents one such – SPOILER ALERT: the next link reveals the solutionmethodology, which is based on mixed integer programming.

You define the problem using variables, zeroes for white cells and ones for black cells. You next define constraints. For example, each row/column has to have the correct sequence of blacks cells in each row/column, separated by at least one white cell. You also need to define an objective function. This is usually something you are trying to minimise (for example, waste) or maximise (for example, profit). In the case of this puzzle, there is nothing to minimise or maximise, as once we have a valid solution we cannot improve on it.

Once we have defined the variables, constraints and objection function, we can hand it over to one of the many solvers that are available online and it will return the solution.

The downside of mathematical approaches to complex problems is that there may be a solution, but it could take millions of years to find it. Fortunately, this puzzle can be solved quickly.

Other approaches

If you don’t fancy either of the above two approaches, there are many other options. In a previous article we discussed how ants could be used to solve chess puzzles. So if ants can play chess, they could certainly solve the GCHQ puzzle.

Whether it is worth the effort to develop the computer model required, however, is open to debate. The same could also be argued for the many other meta-heuristic approaches. Almost any of them could solve this puzzle, but is it worth the development effort?

The puzzle has generated a lot of media interest and many people are trying to solve it. As we have shown above, there are already solutions on the internet and there is even more information about the subsequent puzzles on Reddit. That does seem to go against the spirit of the puzzle, however, and the spirit of the season. Why not just print the grid, get out a pen and exercise the grey matter sometime over the festive period? You may even win the honest way.

The Conversation

Graham Kendall, Professor of Operations Research and Vice-Provost, University of Nottingham

This article was originally published on The Conversation. Read the original article.

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

The Bulletin

This site was created for members and friends of My Telegraph blog site, but anyone is welcome to comment, and thereafter apply to become an author.

TCWG Short Stories

Join our monthly competition and share story ideas...

The Real Economy

Hello, I’m Ed Conway, Economics Editor of Sky News, and this is my website. Blogposts, stuff about my books and a little bit of music

Public Law for Everyone

Professor Mark Elliott

Bleda

Am I my Brothers keeper?

An Anthology of Short Stories

Selected by other writers

davidgoodwin935

The Short Stories of David Goodwin (Capucin)

The Bulletin

This site was created for members and friends of My Telegraph blog site, but anyone is welcome to comment, and thereafter apply to become an author.

TCWG Short Stories

Join our monthly competition and share story ideas...

The Real Economy

Hello, I’m Ed Conway, Economics Editor of Sky News, and this is my website. Blogposts, stuff about my books and a little bit of music

Public Law for Everyone

Professor Mark Elliott

Bleda

Am I my Brothers keeper?

An Anthology of Short Stories

Selected by other writers

davidgoodwin935

The Short Stories of David Goodwin (Capucin)

%d bloggers like this: