Hybridation de la programmation par contraintes et d'un voisinage à très grande taille pour Eternity II

Résumé : Eternity II est un puzzle avec compatibilité entre côtés des pièces créé par Christopher Monkton pour l'éditeur de jeu Tomy (TM). Étant donné 256 pièces carrées dont chaque côté est colorié et un tableau de 16*16, le but est de placer toutes les pièces sur le plateau de sorte que deux pièces adjacentes ont leur côté commun de même couleur. Ce problème est NP-complet, il possède très peu de structure et est fortement combinatoire (256! .4²⁵⁶ combinaisons possibles). Christopher Monkton est tellement confient du fait de la difficulté de trouver une solution à son problème qu'il promet un prix de $2 millions à la première personne qui trouvera une solution. Nous n'avons (désormais) plus grand espoir de trouver une solution à ce problème, mais nous avons néanmoins décidé d'expliquer notre stratégie pouvant être utile à quelqu'un croyant toujours en ses chances de succès. Notre procédure consiste en une initialisation par programmation par contrainte en relâchant le problème. Ensuite, nous améliorons la solution avec une recherche locale stochastique utilisant un voisinage de très grande taille. Notre voisinage est de très grande taille (exponentielle) mais peut néanmoins être exploré en temps polynomial en solutionnant un problème d'appariement avec poids dans un graphe biparti. Notre procédure nous permet d'obtenir rapidement de bonnes solutions avec des scores jusqu'à 458/480 jonctions satisfaites. Notre grand voisinage peut également être utilisé dans une approche bruteforce pour tester 256!/128! . 4¹²⁸ combinaisons au lieu de 256! . 4²⁵⁶. Cette article est également un exemple de VLNS (Very Large Neighborhood Search) pouvant être appliqué à d'autres types de problèmes de placement avec compatibilité entre les objets.