Skip to Main content Skip to Navigation
Conference papers

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! .4256 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! . 4128 combinaisons au lieu de 256! . 4256. 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00291137
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, June 26, 2008 - 5:44:51 PM
Last modification on : Thursday, July 10, 2008 - 4:47:39 PM
Long-term archiving on: : Friday, May 28, 2010 - 10:53:52 PM

File

pages-115-122-article31.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00291137, version 1

Collections

Citation

Pierre Schauss, Yves Deville. Hybridation de la programmation par contraintes et d'un voisinage à très grande taille pour Eternity II. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.115-122. ⟨inria-00291137⟩

Share

Metrics

Record views

134

Files downloads

211