Hexiom, constraints and libraries

After my own forays into constraints programming, I received a comment by Pierre Schaus who solved the problem with his own Scala CP library. The solution is very elegant, and once the boilerplate code is removed (file parsing...), is very short and to the point. The constraints are expressed very clearly using a kind of DSL that is made possible by Scala's flexible syntax. Really enlightening!

This prodded me into looking at what were the available options in my preferred languages. I have learned a lot (but still have a long way to go) and I found two open-source libraries that are very powerful and quite performant, one for Java and the other for C++.

JaCoP: Java Constraint Programming

JaCoP, as its name implies, is a library for constraint programming in Java. It's been developed by two people from academia for more than ten years now. It's flexible, well documented and it ships with a wealth of good examples that are really helpful to get started.

The pros

Java is a big pro for me. Also, the way boolean variables are defined is handy: they are integer variables whose values are restricted to 0 and 1, so they can be used in arithmetic constraints without conversion. In Hexiom, to count the number of actual neighbors of a cell, I only had to sum the boolean variable telling me if a tile was present on each side. And finally, I liked the way constraints can be composited from some primitive constraints. For instance, I found the IfThenElse constraint very helpful and intuitive to use.

The cons

Composition of constraints being so cool, I was a bit disappointed to realize that only primitive constraints could be used as building blocks. The algorithm for the propagation of constraints has probably very good reasons for that, but still. For instance, seeing that X+Y=Z (XplusYeqZ) was a primitive constraint, I hoped that the Sum could also be a primitive, but it's not. That's not too bad, because often the solution only requires to decompose the constraint and introduce one or a few auxiliary variables. You only have to learn this habit.

The result

The code can be found in: https://github.com/slowfrog/hexiom/blob/master/src/com/slowfrog/hexiom/Main3.java

It uses the same constraints as the one from Pierre Schaus, even though the way they are expressed is a bit less elegant:

• the variables to resolve represent cells and the values represent either a tile (0 to 6) or the empty value (7 here)
• auxiliary boolean variables are used to model filled or empty cells
• a GCC (Global Cardinality Constraint) ensures that the correct tiles are used
• a local counting constraint is created for each cell, combined with a condition: if the cell is empty, its value is 7, if it's not empty, its value must be the count of filled neighboring cells

The code performs pretty well and solves all 40 levels in less that a minute. In fact, it solves 39 levels almost instantly, and the remaining one (level 38) in about a minute. However, I had to tweak the branching choice algorithm to get that result. As for my own constraint solver, the best result is obtained when solving variables in row-scan order, and choosing the most discriminating values first. Those values are 0 and 6, which impose respectively that all neighbors be empty or filled. The empty  value must be considered last. The good point is that JaCoP makes it really easy to define that strategy by just listing all values in the required order.

Gecode

Gecode is a C++ library that has been in development for a bit more than five years. It's also very flexible and quite well documented. Being C++, it's also quite easier to shoot oneself in the foot with it, but I guess that's to be expected. It also comes with a pre-compiled solver that accepts the flatzinc syntax as input (but I am still evaluating that part). And the library has won constraint processing contests several years in a row.

The pros

The performance of the program is excellent, with the right tweaks (same as always: the branching heuristics). One advertised advantage is that Gecode supports parallelism. I did not try it, but if it works, it's nice. So it's a virtual pro for me.

The cons

Compared to JaCoP, the variables and constraints seem more primitive and sometime more difficult to handle. Boolean variables cannot be used in arithmetic constraints: auxiliary integer constraints must be created. The difference between variables and arguments is not yet clear to me but seems to revolve around memory allocation. And I met several segfaults before the program ran successfully, because some functions allow nonsensical arguments. Maybe they could be checked better and meaningful exceptions could be raised. There is no obvious constraint composition mechanism, and the branching strategy seems less flexible. To implement the same one as with JaCoP, I had to change the empty value from 7 to -1, to make sure the values were tried in descending order starting at 6. In that case, zero is treated almost last, but it's not too problematic, because it does not appear in a lot of levels.

The result

The code can be found in: https://github.com/slowfrog/hexiom/tree/master/cpp

I have only tested it on Windows 7, with VC++ 10 express and Gecode 32bit.

It uses the same constraints as before, with a few more auxiliary variables and constraints to accommodate the library.

As already said, performance is awesome: all 40 levels are solved in less than half a second, including the dreaded level 38. I can officially call that fast!

Conclusions

Both libraries are very good! Even for a beginner like me, it's possible to get impressive results with a few hours of work. In the future, I might try Gecode standalone solver, to get the performance without the C++ troubles. I'll see if I can find an equivalent Python library. 

Overall, programming with constraints is fun, contrary to what the term might suggest.