A few months ago, Laurent Vaucher wrote a couple of articles (starting with this one) about solving the puzzle game Hexiom using search algorithms and hand-crafted constraint propagation. It looked like an interesting puzzle, and I was curious about how well a generic constraint solver would perform and how to model the problem. Here I describe how I used MiniZinc and Gecode to tackle it.

(If you’re unfamiliar with the rules of Hexiom, the best way to learn is to try playing it, which you can do on Kongregate.)

Modelling

I modelled the game with one integer variable for each cell on the board. Each cell’s variable takes a value from 0 to 7: values 0 to 6 represent a tile numbered 0 to 6, and value 7 means that the cell is empty.

Each level has a hexagonal board of varying size. One step of modelling this problem is to map the hexagonal coordinates of the board onto rectangular coordinates. First, I added a few “dummy” cells to make the board more rectangular. The rows can be numbered in an obvious way, but the columns are trickier; I numbered the leftmost and next-to-leftmost columns as 1, the next two columns 2, and so on. This is perhaps not the best numbering, because it makes calculating the neighbours of a cell harder.

Here are examples of the numbering. The # characters represent the dummy cells that are not part of the original puzzle, but fill out the rows. With these added, the cells form a “square” of size (2*size-1).

                                       Size 4        
          Size 3                                           
                                  1  # * * * * # #   
       1 # * * * #                2 # * * * * * #    
       2  * * * * #               3  * * * * * * #   
Row    3 * * * * *          Row   4 * * * * * * *    
       4  * * * * #               5  * * * * * * #   
       5 # * * * #                6 # * * * * * #    
         1122334455               7  # * * * * # #   
                                    11223344556677   
          Column                                     
                                       Column

With this numbering scheme, calculating the neighbours of a given cell is not simple. It took me a while to realise that it depends on both the row and the size of the grid. Here is the formula, where i and j are the row and column respectively:

neighbours(i,j) =  { (i, j±1),
                     (i±1, j-1+(size+i) mod 2),
                     (i±1, j+(size+i) mod 2) }

A level is specified by a few components:

  • the size of the board
  • the number of each kind of tile
  • the positions of the fixed tiles

For example, level 10 looks like this in Laurent’s format:

3
  +.+. .
 +. 0 . 2
 . 1+2 1 .
  2 . 0+.
   .+.+.

This level has a board of size 3, two “0” tiles, two “1” tiles, three “2” tiles and many “blank” tiles. The seven tiles that are prefixed by “+” symbols are fixed in place.

Hexiom comes with a set of 40 levels, which Laurent has kindly made available in a machine-readable format. My first task was to translate these from Laurent’s format into one that can be used with MiniZinc. The program itself is not very interesting, but here is the output for level 10:

size = 3;
counttiles = array1d(0..7, [2,2,3,0,0,0,0,18]);
numfixed = 13;
fixedrow = [1,1,1,1,2,2,3,4,4,5,5,5,5];
fixedcol = [1,2,3,5,1,5,3,4,5,1,3,4,5];
fixedval = [7,7,7,7,7,7,2,7,7,7,7,7,7];

Note that the dummy tiles are included here; they are counted as blanks, and are fixed in their positions.

MiniZinc model

Here I describe some of the interesting parts of the MiniZinc model. The whole thing is available here.

The rows and columns are numbered from 1 to 2*size-1 – I call this range “r”.

% The dimensions of the square array that encloses the hexagon.
set of int : r = 1..2*size-1;

There are two sets of decision variables.

% The decision variables.  If x[i,j]=v, then we place a tile marked
% "v" at position (i,j).  Value 7 represents "no tile".
array [r,r] of var 0..7 : x;

% Auxiliary decision variables.  We have t[i,j]=1 if and only if
% x[i,j] < 7.  In other words, t[i,j]=1 if and only if there is a
% tile at position (i,j).
array [r,r] of var 0..1 : t;

% Link x and t variables.
constraint forall (i,j in r) (t[i,j] = bool2int(x[i,j] < 7));

The rest of the model follows in a straightforward manner. I tried not to make it complicated. One awkward part is calculating the number of neighbouring cells that contain tiles, because we have to check that the coordinates refer to a cell on the board before accessing the variable at those coordinates.

% The primary constraint of the puzzle.  Each cell either has a
% tile or it does not.  If it does not, then it has value 7 and
% there are no further constraints.  If there is a tile, then the
% number of tiles among its neighbouring cells is equal to the
% value on the tile.
%
% The constraint looks more complicated than it is, due to the way
% we force a Hexiom to look like a square, and that we have to
% check the bounds of every array access.
constraint
  forall (i,j in r)
       ( (t[i,j] = 0) \/
         (x[i,j] =
           sum([ if j+1 in r then t[i,j+1] else 0 endif
               , if j-1 in r then t[i,j-1] else 0 endif
               , if i-1 in r /\ j-1+((size+i) mod 2) in r
                   then t[i-1,j-1+((size+i) mod 2)] else 0 endif
               , if i-1 in r /\ j+((size+i) mod 2) in r
                   then t[i-1,j+((size+i) mod 2)] else 0 endif
               , if i+1 in r /\ j-1+((size+i) mod 2) in r
                   then t[i+1,j-1+((size+i) mod 2)] else 0 endif
               , if i+1 in r /\ j+((size+i) mod 2) in r
                   then t[i+1,j+((size+i) mod 2)] else 0 endif
               ])) );

The other two constraints are simple; they ensure that we have placed the right number of each kind of tile, and that the fixed tiles are in their place.

% There must be the specified number of each value of tile.
constraint forall (v in 0..7)
  (count([x[i,j] | i,j in r], v, counttiles[v]));

% Put each specified fixed tile in its place.
constraint forall (i in 1..numfixed)
             ( x[fixedrow[i], fixedcol[i]] = fixedval[i] );

Finally, the search heuristic is crucial. Here I follow Laurent’s advice, which is to pick the cells in order, and try high value tiles first. In MiniZinc terms, I interleave the t variables with the x variables, and try larger values first (indomain_max).

solve :: int_search([ if k = 0 then t[i,j] else x[i,j] endif
    | i,j in r, k in 0..1], input_order, indomain_max, complete)
satisfy;

Results

Without the heuristic above, the results are mixed. Most of the levels can be solved quickly, but levels 38 and 40 in particular take a very long time. However, with the heuristic the results are much better. Level 40 is now trivial, and level 38 takes about 15 seconds. In fact, the times can be summarised as follows:

Level 38 ~15 seconds
Level 36 ~120 milliseconds
All other levels < 20 milliseconds

(These are just for running Gecode to find a solution, and don’t include the level translation or MiniZinc parsing.)

Other notes

Before I used Laurent’s heuristic, I experimented briefly with singleton arc consistency, a strong but very expensive kind of constraint propagation. It improved performance on some levels, but not to the degree I got just by changing the search.

Laurent has also tried applying Gecode to this problem (directly, rather than via MiniZinc) and got even better results! It would be interesting to see how his model differs from mine.

I tried a lazy clause generation solver with my model, but it performed worse than Gecode. I had expected LCG to perform well on this problem, so I’m curious to figure out why it didn’t work.