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.

Sikuli plays Hexiom for me

[Update: with some tweaking, my script sometimes succeeds with size-6, see at the end]

Yeah! Here is one of the first successful automatic runs of my Hexiom-playing bot. This is the combination of the solver I wrote about recently, and a bot coded with Sikuli.

Sikuli itself is a combination of OpenCV for the back-end, screen vision part, a Java middle layer and a scripting engine using Python as its language. It comes with an IDE that is quite easy to learn too.

What's great

The scripting part of Sikuli being Jython (Python implemented on top of the JVM) is great. It allows to code quickly and to fall back to Java for more preformance-sensitive parts. In my case, all the screen reading and playing logic is implemented in pure Python, but the problems are handed to Java for resolution.

OpenCV itself is great and fast enough.

And as previously said, the IDE is easy to learn and loaded with helpful tools like the screen capture utility and above all the pattern testing screen. It is invaluable to tweak the parameters of image matching, because small patterns like the digits of Hexiom can sometime lead to misses or false positives.

What's not so great

Sikuli, do no seem to offer a non-rectangular matching function. There's an open request for that on Launchpad, but from my quick investigation, it might be an OpenCV limitation. The only workaround is to match the biggest rectangular area that can fit in the preferred non-rectangular pattern. That is quite annoying: first, in Hexiom's case, all the patterns I'd like to use are hexagonal and second, using a smaller patterns leads to worse detection. After some tweaking, I succeeded in making the bot work every time on a size-4 puzzle, but it's not yet working on a size-6 one, because the board reading procedure making too many mistakes.

Wanna try?

Following these steps, you should be able to run the bot:

• Install Java, Sikuli and Firefox
• Fetch my code from github
• Compile java sources (in src/main/java to build/main/classes) or use Eclipse
• Open a Firefox window
• Set JAVA_HOME and SIKULI_HOME environment variables in a terminal
• Run ./autorun.sh 4 to solve a size-4 puzzle

You can also try with 6 instead of 4, but the results will probably be disappointing. Don't try 3 or 5: I haven't captured the appropriate digits yet.

Breaking news!

Sometimes, it works with size-6.

Daniel Hartmeier on his site with a somewhat different approach also succeeded, with a fully functional C program, see: http://www.benzedrine.cx/hexiom.html

Solving Hexiom using constraints

After my first try using brute force search to solve the Hexiom puzzler, and following recommandations I received in comments, I switched to an approach using constraint solving principles. It's not yet finished (I can still think of new constraints to add), but it's already working more or less as efficiently as the search version. I will try to highlight my findings in this post.

Search algorithm

My search algorithm was quite simple:

1. choose an empty cell
2. look for all tiles that can possible fit and try each one in turn
3. decide if the resulting position is solved, still open, or impossible
4. if still open, continue at step 1.

That being said, the latest implementation already took the current position into account in step 2. and 3. For instance, when looking for possible tiles, I only tried tiles with available numbers (obviously), and in a range of values that would still be correct considering surrounding values. That last element is already a kind of constraint application, albeit a simple one.
The third step is quite powerful too, in deciding whether a position is impossible to solve. It also computes possible values and detects mismatches. It can prune out a good deal of possiblities by finding violated constraints.

Constraint solving algorithm

The algorithm is, in fact, an hybrid between constraint solving and search.

1. When reading the input file, each cell is filled with the list of possible tiles, depending on available numbers, number of neighboring cells and locked tiles
2. A set of constraints is used to remove possibilities from cells. This step is repeated until nothing moves any longer.
3. Then we fall back on search, as before:
4. choose a cell
5. find all possible tiles and try each one in turn
6. decide if the resulting position is solved, still open, or impossible
7. if still open, repeat a step 2.

The tricky parts are number 2. and number 4.

Regarding constraints (step 2.), some are easy to find, some require a bit more work. I currently use three constraints, but I have thought of some more. The first constraint I use is the same as was implemented in the search algorithm: remove values that are outside the range of possible neighbors. For instance on the following figure, black cells have not been solved yet and we are trying to find which values are still possible in the blue cell. The minimum value is two, because we already have two neighbors. The maximum value is five, because we already have one empty cell as neighbor and the other ones are either filled or could be filled.

The second and the third constraints are mostly like the ones used in sudoku: when all tiles of a current value have been used, remove that possibility from all other cells, and when the number of cells that can host a given value is exactly the same as the number of available tiles with that value, fill all the cells with that value.

Step 4. is where heuristic is important: I have to decide which cell to try first and in which order to try the possible tiles. I have implemented four strategies to choose the next cell. One finds the cell with the fewest choices, the second finds the cell with the most choices, the third finds the cell with the highest possible value and the last just scans cells linearly, from top to bottom (like the search algorithm).

Results

The current results are good but not perfect. On the one hand, with the good heuristic, I can now solve level 40 in under a second and level 38 in two hours, whereas they completely resisted the search algorithm. On the other hand, solving the 38 other easy levels is a little slower than with the search. The code is available as usual on github. The java version could probably do with some low level optimization, like minimizing the number of instanciated objects.

Among heuristics, the one that chooses cells linearly does globally better than others. I does not fit my immediate intuition. I was inclined to choose cells with the least choices, thinking I would get better chances. It seems intuition is not always the friend of science.


What's next

This puzzle is a suprisingly rich field of exploration. I have a few more directions to go.

The first is expanding the set of constraints. I'm thinking of one constraint that could help remove the "empty" possibility from cells, when it's mandatory to fill remaining cells with tiles in order to reach a given count. Another one, or the same in reverse, could force empty cells when the correct number of neighbors is already present.

The second is around heuristics. What bothers me is that several of the ones I have implemented are perfect in some situation and awful in others. I can try to find new ones. Or I can try to take advantage of multiple cores by running several solvers in parallel, with different heuristics, and hope that one of them finishes quickly.

The third is another approach to the problem. Only choosing which cells to leave empty is sufficient to determine the complete board. Then it's only a question of matching the resulting board with the set of available tiles to see if it works. I'll describe that approach later, but I'm not sure it can lead to a workable solver. I'm afraid I won't be able to prune out branches as effectively.

The fourth is about automation. If you remember, my goal was to get the 60 Kongergate points granted for solving a random size-6 board in less than three minutes. To reach that goal, I have started using http://sikuli.org/ to play for me. It's not yet done, but it can almost read a size-4 board. After that, it will only need to launch the solver, read the results, and move the tiles accordingly. Should be fun to watch...


Credits

Thanks to fellow redditor julesjacob who described the general principles of constraint propagation that I implemented here and gave invaluable advice and pointers to good resources. And also to leonardo_m who piqued my curiosity for the D language by porting the Java version of the search algorithm.

You can also comment on reddit.