OddThinking

After the Snail Puzzle, I took a huge departure from my previous attempts at newspaper puzzle solving. Basically, I broke all of my self-imposed rules.

I had a discussion about Constraint Programming with some other developers. My contribution to the discussion was basically “I don’t know anything about Constraint Programming,” so I decided to give it a try to see what I was missing. This is the journey of a newbie, so please don’t take anything I say as gospel.

I decided to tackle Cross-A-Pix, which can be found at Conceptis Puzzles.

Here’s an example – a screenshot from Conceptis Puzzles:

Once again, there is a grid of cells. Each cell can be black or white. Between the cells are borders that divide the grid into small abstract shapes. All the cells in a single shape must be marked with the same colour.

There are two variants to the puzzle.

In the “Single Clue” variant, each row and each column has a number clue which indicates the number of black cells in that row.

In the “Double Clue” variant (like the one pictured), you get a second number for each row and column which indicates the number of runs of black cells. i.e. a value of “5 1” means there are 5 black cells and they are all touching in 1 run.

This is a puzzle that I find challenging to solve in real-life. I get stuck all the time. It is also a puzzle that I have always thought would not be a good fit for the Puzzle Solving Framework, because it seem to be less focused on step-by-step filling in the blanks by repeatedly following a simple rule, and more “if you look at every possible combination you’ll see only one fits”. (Caveat: Or else there exists a simple rule that I have never deduced.)

First Challenge: Importing Clues

One of the big challenges with this puzzle is that it isn’t easy to generate your own puzzles, and it isn’t easy to transcribe all the clues. I wrote some fiddly code to accept a screenshot from Conceptis Puzzles and detect where the borders were.

Here is the same puzzle, reverse-engineered:

PuLP and Linear Programming

The first step in my journey of discovery was a Python library called PuLP from the University of Auckland. It allows you to construct a model from scratch with Python objects. You can create a set of (typed and ranged) Variables that the solver will try to find values for, and define constraints based on Affine Expressions – e.g. this set of variables must sum to less than this one.

What you don’t do is specify how to solve it. The solver can work out its own strategy (possibly involving a lot of brute force!) based on the declaration.

When it is specified, the library generates a human-readable intermediate language – an LP file. That format is readable by at least four different solver engines written in faster languages than Python.

I made good progress with this library – I learnt the key concepts, and managed to get as far as modelling the single clue puzzles with it. The constraints I implemented were: (1) if a cell was in the same group as its neighbour above or to the left, it must have the same value, (2) the sum of all the cells in the row or column must equal to clue given.

I fed it the puzzle above (understanding that it was underspecified, because there was no support for the second clue.)

The default solver that PuLP called stumbled and rejected it is as undefined (despite handling much smaller test examples). I installed the GLPK, the GNU Linear Programming Kit, as an alternative solver. It ran for 13 minutes, and dumped out a solution that met all the constraints, but looked like gibberish. Success!

Now, I just needed to solve the second clue part, so I would get a real picture as the solution.

My strategy was to create two more grids of Boolean variables (one for columns, one for rows) representing whether the corresponding cell in the first grid was the start of a run. i.e. it detected the transition from white to black between two cells. e.g. IsStartOfRowRun[5,4] = Cell[5,4] and not Cell[4,4]. I could once again sum them and constrain the sum to match the clue.

If you have any familiarity with linear programming, you’ll immediately see the problem. If you have my level of familiarity with linear programming, it will take a few hours before the problem becomes clear.

PuLP’s manual emphasizes the difference between Linear Programming and Integer Programming. In linear programming, the constraints must be linear expressions. I thought I was clearly in the Integer Programming category, and my constraints didn’t need to be linear.

However, neither the PuLP models nor the LP file format allow anything but linear expressions, even in Integer Programming. Remember the definition of IsStartOfRowRun used an “and” operator? Nope. Can’t be (easily) expressed.

Wrong technology! Try again.

Claspy and Answer Set Programming

The second step in my journey of discovery was a Python library called Claspy from an engineer who likes to use it to tackle similar puzzles.

It allows you to construct model from scratch with Python objects. Hey, this is familiar! You can create a set of (typed and ranged) Variables that the solver will try to find values for, and define constraints – but this time, it supports “and”, “or” and “if”.

When it is specified, the library internally generates a human-unreadable intermediate language that can be understood by the CLASP engine, part of the University of Potsdam’s Ansert Set Solving Collection, Potassco.

The Claspy code is both old and immature. I started fixing it up – porting it to Python 3, cleaning up the output, fixing an egregious bug I could recognise. However, when CLASP complained that the generated intermediate language had a parse error, I had to walk away. I didn’t know the intermediate language, the specification wasn’t immediately available and I couldn’t debug it.

Minizinc

The third step in my journey of discovery was Minizinc from Monash University.

With Minizinc, I was back to a human-readable domain-specific language.

I briefly checked out a Python library, PyMzn but it seemed focussed on *launching* an existing Minizinc program from within Python, and not *constructing* a Minizinc model from scratch.

So I ported my existing Python code over to the new language. The structure of the code was pretty familiar by now, but, as was entirely predictable, the random new syntax of a new language took dozens of iterations to get right.

On the other hand, it was only 38 lines of code (excluding the clues, which sit in a separate data file)

Once it was ported across, Minizinc ran for 5 minutes, and spat out a correct answer – in a gibberish format – it is hard to do string manipulation in the new language, so I cut and pasted it back into Python to parse, and render as a picture.

Voila!

(That’s a picture of a sky-diver.)

I confirmed it was correct by checking it on Conceptis Puzzles.

Conclusion

I explored several dead-ends. I learnt a new technique and a new tool. I still need work out how to use PyMzn as a Python wrapper so I can model without having to think about new syntaxes and IDEs and so I can get data into and out of Minizinc. I completely violated my values and let brute force and alien AI optimisations win over more human-like solving techniques and decentralised architectures..