Solving the GCHQ Christmas puzzle with Python

I recently started re-acquainting myself with Python, and I thought solving the GHCQ nonogram would be a good problem to dive in to. Here’s what I came up with.

Method

The puzzle is a 25×25 nonogram. I decided to write a program thatĀ uses the same methodĀ that I would use if solving the puzzle by hand:

  1. For each row and column, generate the set of patterns that match the given clues
  2. For each row, eliminate the patterns that don’t match the cells we already know
  3. For each row, deduce the known cells based on the reduced pattern set
  4. For each column, eliminate the patterns that don’t match the cells we already know
  5. For each column, deduce the known cells based on the reduced pattern set
  6. Go back to 2. and repeat, unless we’ve solved it

Code

I call it “yangs” - Yet Another NonoGram Solver.

View the Jupyter notebook on nbviewer or download a .py file fron GitHub

comments powered by Disqus