The GCHQ’s Christmas Challenge puzzle shown in the picture below has been making rounds on social media and in the news so I decided to try modeling it in AMPL and solving with a constraint programming solver.
Here are the rules of the puzzle:
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.
The first step is declaring parameters and sets to represent the input data:
N: the number of rows or columns (they are the same in this problem)
MaxRun: the maximum length of a run
RC: a set of rows or columns to simplify indexing expressions.
ColRunLen: the lengths of row and column runs respectively with zero representing “no value” for the cases when the number of runs is smaller than
KnownPos: positions of known black squares
ColRuns: set of row and column runs respectively
The most challenging part of this particular puzzle for me was to enter the data. Fortunately AMPL has a powerful data specification language so I came up with a tabular format similar to the form used in the original puzzle which was easy to verify.
Now to the interesting part: I used two sets of decision variables,
ColRunStart, to represent start positions of row and column runs respectively:
A good thing about constraint programming formulation is that it is pretty straightforward because you can model logic, such as disjunctions, directly and don’t need to introduce binary variables as in MIP case.
This is a constraint satisfaction problem, so we don’t need an objective, just constraints. The first group of constraints makes sure that row runs don’t overlap and the same for column runs:
The next constraint links row and column runs by stating that every element of a row run should belong to some column run:
It might be possible to model this more efficiently, but I didn’t bother because even this naive formulation was solved in less than a minute.
And the last constraint brings in known black squares stating that each of these squares should belong to some row run:
And that’s the whole formulation. The following little script solves it with
IBM ILOG CPLEX CP Optimizer
ilogcp and displays the solution in a terminal:
And this post would be incomplete without mentioning related approaches to solving this puzzle, Solving The GCHQ Christmas Puzzle As A MIP With Python by Jean-Francois Puget and Solving the GCHQ christmas card with Python and pycosat by Matthew Earl.
You can find the complete AMPL code to solve this puzzle here.comments powered by Disqus