A Guide‐and‐Observe Hyper‐Heuristic Approach to the Eternity II Puzzle

The present paper considers the optimisation version of the Eternity II puzzle problem and unsigned edge matching puzzles in general. The goal of this optimisation problem is to maximise the number of matching edges in the puzzle. In 2010, the META Eternity II contest awarded the best performing metaheuristic approach to this hard combinatorial optimisation problem. The winning hyper‐heuristic of the contest is subject of this paper. Heuristic design decisions are motivated based on the results of extensive experiments. Furthermore, new results for the Eternity II puzzle problem are presented. The main contribution of this paper is the description of a novel guide‐and‐observe search mechanism combining a set of objectives. The approach significantly outperforms search methods guided by the default objective only.