  The present paper considers a hybrid local search approach to the Eternity II
puzzle and to unsigned, rectangular, edge matching puzzles in general. Both an
original mixed-integer linear programming (MILP) formulation and a novel
Max-Clique formulation are presented for this NP-hard problem. Although the
presented formulations remain computationally intractable for medium and large
sized instances, they can serve as the basis for developing heuristic
decompositions and very large scale neighbourhoods. As a side product of the
Max-Clique formulation, new hard-to-solve instances are published for the
academic research community. Two reasonably well performing MILP-based
constructive methods are presented and used for determining the initial
solution of a multi-neighbourhood local search approach. Experimental results
confirm that this local search can further improve the results obtained by the
constructive heuristics and is quite competitive with the state of the art
procedures.
