Hexiom Puzzle

Hexiom is a very interesting game that you can play online here

“The object of Hexiom is to arrange all tiles in a way that they are adjacent to exactly the number of other tiles as they are showing.”

Two solutions are for instance:

This puzzle can be solved with CP in a nice way (like most of the problems of course ;-)).

If you don’t want to see my model right now, just think about which decision variables and constraints you would use before continuing the reading of this post.

I use 3 types of variables in this model:

1) Type1: I call them used(i) with domain {0,1} to tell whether or not there is a tile in position i.

2) Type2: I call them nbNeighbors(i) is a variable representing the number of neighboring tiles of position i. The domain of these should be {0,1,2,3,4,5,6} because tiles are hexagons

3) Type3: I call them card(i). Those are almost the same as Type 2 but I also include 7 so their domain will be be {0,1,2,3,4,5,6,7}. It will become clear with the explanation on the constraints why we also need Type3 variables.

Now the constraints:

If you have for instance in input 3,4,0,2,2… it means that you must have one tile with 3 adjacent tiles, one tile with 4 adjacent ones, one isolated tile, two tiles with two adjacent tiles, ….

All of this can be imposed with just one Global Cardinality Constraint (GCC ) posted on the card variables. The problem is that we don’t want to count a value in the card variables if there is not tile placed in this position. This is why I introduced the value 7 in the domain of the card variables: If there is not tile in a position i, card(i) will take value 7 rather than taking as value the number of adjacent tiles to position I (i.e. nbNeighbors(i)). Of course in our GCC the number of occurrences for value 7 is not constrained.

To enforce the value 7 when there is no tile we have several options but not all of them are equivalent in terms of filtering. The optimal filtering is obtained by using a table constraint where you specify that the three variables (nbNeighbors(i),used(i),card(i)) altogether must be equal to one of those tuples: (0,0,7), (1,0,7), (2,0,7), (3,0,7), (4,0,7), (5,0,7), (6,0,7), (0,1,0), (1,1,1), (2,1,2), (3,1,3), (4,1,4), (5,1,5), (6,1,6)

Where nbNeighbors(i) is equal to sum(neighbors(i))(i => used(i)).

If you have a MIP background, you might be tempted to write something like:

card(i) == (used(i) * nbNeighbors + (1- used(i)) * 7)

Unfortunately, using sum and prods to do it would have a weaker pruning than with the table option because products and summations mainly reason on the bounds of the domains in CP.

In this model, it is also important to try to place tiles on the left branch and remove it on the right branch during the search tree exploration (optimistic heuristic). With this strategy we can find a solution to the hardest instance with only two backtracks!

Here is it's solution (level 40)

The source file of this model in Scampi is available here

In the real hexiom, I think some positions of some tiles are forced. Of course it is not difficult to enfore that in this model (just force the value of card(i)).

An interesting variant to me would be to consider the overconstrained problem and try to place as many tiles as possible, or try to collect has many points as possible (number on the tiles).

Let me know if you also implement a model for Hexiom in another system such that I attach a link to them on this blog.