Part 1

Around Christmas each year the British spy agency puts out a puzzle intended to challenge the best solvers in the world. For the 2015 puzzle it started with a Christmas card from the director with the following:

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.

Solving this puzzle by hand is possible but what's the fun in that? Instead a generic Python solver is much more interesting, and who knows, another puzzle like this could show up at any time!

Solving the Puzzle with Python

Basic setup

Create a base grid grid[x][y][color] where color is either solved as BLACK, WHITE, or unknown GRAY.

Create arrays with the X and Y directional clues.

Next, use the clues to figure out the number of extra white spaces one has to play with. For example, if we had a puzzle with 5 squares and the clue was 2, 1, we assume the most compact left justified solution and find one white space on the right: BBWBW. One space to move around. BBWBW, BBWWB, or WBBWB are the 3 possible answers.

Partitioning

Finding all of the possible solutions to a single row requires a partitioning algorithm, the most complex portion of the solver. The partitioner takes a number like 4 and breaks it up as: 1+1+1+1, 1+1+2, 2+2, 1+3, and 4. Representing the possible distribution of those extra spaces we found previously.

Convert Spacing Pattern to a Grid Pattern

Next the spacing partitions are converted into possible solutions for each row and column:

    Use a clue like [7,2,1,2,5] and a space pattern (2, 1, 0, 0, 0, 4, 2)
        to convert into:
        [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0]

Smarter - but still Brute Force

So far we are setup to try every combination of 167190 solutions, but it will take a long time. Instead we go through the solution set and throw out anything that doesn't work with the knowns. It turns out, on the first iteration the number of solutions reduces to 15355 and 108 of the 625 cells only have one answer. Continuing this process 8 times quickly solves the puzzle. On a MacBook:

    Generating Patterns
    Patterns: 167190
    setup Time: 9.916450023651123

    solved 108 of 625 cells
    Patterns: 15355
    solved 292 of 625 cells
    Patterns: 966
    solved 462 of 625 cells
    Patterns: 162
    solved 554 of 625 cells
    Patterns: 85
    solved 596 of 625 cells
    Patterns: 60
    solved 616 of 625 cells
    Patterns: 53
    solved 622 of 625 cells
    Patterns: 50
    solved 625 of 625 cells
    Total time: 11.97863483428955

In order to speed things up a little, multi-threading was introduced.

This was the first of 5 levels, each of increasing difficulty. Did you notice, as an 'easter egg', the creators of this puzzle spelled out GCHQ in Morse Code with the given cells?

The solution has been left off, so the reader can either solve by hand or run the Python program to discover the answer. Contact me below if you have questions or suggestions for improving the algorithm.

Now that we have a generic solver, waiting for another opportunity to use it...

Feel free to contact me to check your answer, get a copy of the solver or with any questions.