Author:

Keywords:

Puzzle, Edge-matching

Abstract:

The Eternity II (EII) puzzle is a commercial edge matching puzzle in which 256 square tiles with four coloured edges must be arranged on a 16 by 16 grid such that all tile edges are matched. In addition, a complete solution requires that the `grey' patterns, which appear only on a subset of the tiles, should be matched to the outer edges of the grid. The puzzle belongs to the more general class of Edge Matching Puzzles, which have been shown to be NP-complete. In July 2007, toy distributor Tomy UK Ltd. released this challenging edge matching puzzle with a $2 million prize. However, to the best of our knowledge, no complete solution has ever been found. Meanwhile, the final scrutiny date for the cash price, 31 December 2010, has passed, leaving the large money prize unclaimed. In its 10 years of existence many people tried to solve EII and some are still trying. Many approaches to Edge Matching Puzzles are reported in the literature. Among these approaches are constraint programming and backtracking, metaheuristics, and evolutionary methods. Other approaches translate the problem into SAT, MILP or max-clique and then solve it with appropriate state of the art solvers. Some approaches have also been implemented on parallel computing or dedicated hardware.