Hybridization of CP and VLNS for Eternity II.

 Title Hybridization of CP and VLNS for Eternity II. Publication Type Conference Paper Year of Publication 2008 Authors Schaus, Pierre, and Deville Yves Conference Name Quatrième Journées Francophones de Programmation par Contraintes (JFPC'08) Abstract Eternity II is an edge-matching puzzle created by Christopher Monckton for the game editor Tomy(TM). Given 256 squared pieces with a color on each of the four sides of pieces and a $16 \times 16$ board, the goal is to place all the pieces such that two adjacent pieces have their common side of same color. This problem is NP-complete, has very few structure and is highly combinatorial ($256!\cdot 4^{256}$ possible combinations). Christopher Monkton is so confident in the difficulty of the problem that he promises a \$2 million prize to the first person who finds the solution. We don't have any hope (anymore) to find a solution to this problem, but we nevertheless decided to explain our strategy which might be useful for someone else still believing in his/her chances of success. Our procedure first initializes the board with constraint programming by relaxing the problem. Then we improve the solution with a very large neighborhood stochastic local search. Our neighborhood is very large (i.e. exponential) but can be explored in polynomial time by solving an assignment problem. Our procedure allows us to obtain rapidly good solutions with scores reaching 458/480 number of satisfied junctions. Our very large neighborhood can also be used in a brute-force approach to test$256!/128! \cdot 4^{128}$combinations instead of$256!\cdot 4^{256}\$. This paper is also an example of VLNS that can be applied on other matching problems.