A nonogram is a type of Japanese crossword type puzzle with numbers. You fill in boxes based on numbers in the rows and columns and eventually make a picture.
The SecCon implementation looked like this (NO! added for comedic effect :P ):
I looked into solving the puzzle category itself but grew tired of reading the rules and instead looked at solving engines other people had written.
I first selected this one from Github. The solver worked and was simple to integrate with some simple network code but it was very slow and often tried to perform useless exhaustive searches for perfect solutions which just didn't ever seem to end.
That was where I spent most of my time on this challenge, diagnosing why Nonograms take time to solve. I found that there's often more than one solution and sometimes there are many possible solutions.
So I went back on the hunt for a better Nonogram solver and came across this article about using Google CP solver for faster Nonogram solutions using DefaultSearch.
Sounded good and, again was in Python, so I basically swapped out the old engine of my solution for this one in a couple of minutes and immediately saw results. The solver was way faster and knew how to give up after finding 2 (or, modified as many as you like) possible solutions.
With that engine, some very rough web and table parsing code, and we had a solver for this challenge that would:
- Grab the first / next challenge nonogram table
- Parse for the values in the first column and top row into two zero padded lists
- Feed that into the Google constraint programming engine via some borrowed Python code
- Get a text output, write that using Python Image Library to a PNG file
- Parse the PNG for a QR code
- Send the QR code decoded output to the server and fetch the next challenge
We had to do this a total of 30 times and the solutions aren't always perfect and the QR codes don't always work so a few attempts need to be run.
Anyway, I include the code before, sorry you have to see this messy hack but I don't mind, 300 points it got me :)
And when we run it we get the even less impressive wall of mangled output:
Anyway, it was actually fun to solve this as I always do like the challenge response type problems. I probably suffered a bit here from trying to reuse some of the code I previously used for another challenge but not too badly.
Overall I really enjoyed SecCon 2015!