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++.
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!
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.
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.
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 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
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 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.
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 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.
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.