Solving the 2015 GCHQ Christmas Puzzle part 1

This year GCHQ released a Christmas Puzzle, in this post I'll show you how to solve the series of puzzles, and also, the thought process that I used to get to the solutions.

If you would like to attempt to solve the puzzle yourself then here is the link to the first part of the puzzle. The solution to the first part will then lead to the second part of the puzzle. In total there are five parts.

http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx

From the GCHQ website:

"In this type of grid-shading puzzle, each square is either black or white. Some of the black squares have already been filled in for you.

Each row or column is labelled with a string of numbers. The numbers indicate the length of all consecutive runs of black squares, and are displayed in the order that the runs appear in that line. For example, a label "2 1 6" indicates sets of two, one and six black squares, each of which will have at least one white square separating them."

I decided to solve this puzzle in excel. The main reason for this was that I wanted to be able to fill in squares automatically rather than shading them by hand. I've posted a link to an excel file below which matches the start of the puzzle. In my version if you press Ctrl+a then the selected cell will turn black, and if you press ctrl+d then the selected cell will turn blue. I'll explain the use of blue cells later.

gchq_qr.xlsm
File Size:	19 kb
File Type:	xlsm

Download File

---

 The first step to solving this puzzle is to count the number of rows and columns in the grid. In this case we have a 25 by 25 grid. In excel I then calculated the minimum number of cells required for each row and column. For example, the third column is listed as 1,3,1,3,1,3,1,3,1. Since there must be a blank space in between each block of black cells, this combination must take up a minimum of 25 cells but since there are only 25 cells in the column we now know which cells in this column need to be coloured black. We can now go ahead and fill in this column. We also know that the spaces in between the blocks of black cells need to be blank, to signify this we can colour these cells blue. Repeating this process allows us to complete 3 columns and 2 rows.

The next step is to look at rows and columns which have high minimum values but which are less than 25 but still high. For example, looking at the first row, it is listed as 7,3,1,1,7 with a minimum of 23. Since the first two blocks on either side are 7 long, cells 17:23 must be coloured in as a minimum, but as a maximum cells 19:25 must be filled in. Since there is an overlap between these two we can colour in the cells in the overlap. Here is an image demonstrating this. There are three copies of the first row, the first row contains the minimum cells and the second row contains the maximum cells. I have then coloured the overlap on the blocks of seven in black.

Filling in the first cell in a row is also useful as it lets us immediately use the information about that column. For example we know that the third cell in the first row is black, looking at the listing for this column we see that the first block of blacks is a 1, therefore the cell below it in the second column must be blank and can be filled in blue. Using this these techniques we eventually complete the grid. Giving the following image.

You may recognise this kind of pattern as a QR code. A QR Code is a 2 dimensional bar code. I downloaded a QR reader to my phone and scanned the image which takes you to the following url:

http://www.gchq.gov.uk/puzz/Pages/index.aspx