3ème défi C & C++ : Découverte du jeu de l'Ane Rouge

Bonjour à toutes et à tous,

Le 3ème défi C & C++ est lancé. Il s'agit de rechercher une solution au jeu de l'Ane Rouge. Ce défi commence aujourd'hui (dimanche 22 mars 2009) et les copies sont ramassées le dimanche 26 avril 2009 à minuit.

Pour plus d'information, les différents points d'entrée sont :

• Serveur des défis C & C++
• Les règles générales des défis C & C++
• Les règles particulières de ce défi

Si vous prévoyez de participer au défi, envoyez un petit MP aux organisateurs. Il ne s'agit nullement d'un engagement de votre part mais cela nous permet de composer un jury avec suffisamment de membres en fonction du nombre de réponses prévisibles.

Si vous avez la moindre question concernant ce défi ou si un point du règlement vous parait obscur, il suffit de poster dans la suite de ce message (les questions et les réponses sont publiques).

Bon courage à tous

j'ai hâte de voir celui qui fera moins de 81 coups:P

Citation:

---

Envoyé par Senji

j'ai hâte de voir celui qui fera moins de 81 coups:P

---

Peut être le tien, il suffit de se lancer ;)

j'ai pas envie de tricher puisque je l'ai déjà fait quand j'étais étudiant mais en java. :aie: donc je vais m'abstenir pour ne pas défavoriser les autres :)

bye ;)

Bonjour !

Dites moi, quand vous écrivez dans l'énoncé :

Citation:

---

Le nombre de déplacements à afficher est le nombre de déplacements pour aller le plus directement possible de la position initiale à la position finale. Il ne comprend pas les éventuels errements dûs à la recherche de la solution.

---

Vous voulez dire que la solution ne doit pas comporter de cycle c'est cela ? Ou vous demandez de reproduire la solution optimale ?

Bien à vous.

Dans mon esprit, la solution optimale correspond à la solution qui possède le nombre de coups minimum pour aller de la position initiale (fournie par le fichier au démarrage) à une des positions gagnantes (pour info, il y a toujours plusieurs positions gagnantes car la position des autres pièces est sans importance, seule l'ane rouge doit être bien placé).

Effectivement, il est possible d'avoir des cycles dans une solution et dans ce cas, il risque de ne pas avoir de solution gagnante car la solution courante risque de se promener indéfiniment sur ce cycle et de ne jamais pouvoir s'en échapper.

Est ce que j'ai répondu à la question ?

Oui c'est très clair.

Ainsi, il n'est pas obligatoire de fournir la solution de 81 déplacements.

Il faut simplement que la solution proposée au final ne comporte pas d'aller-retour de pièces (ce que j'appelle les cycles).

Merci !

Salut, et bienvenue sur le forum

Il faut que ton programme trouve une solution correcte, de préférence, en évitant les allers-retours inutiles...

En effet, si tu commence à déplacer un pion vers un endroit pour le re-déplacer tout aussi vite vers sa place d'origine, tu risque d'augmenter le nombre de coups à jouer "jusqu'à la fin des temps" sans pour autant te rapprocher de l'une des solutions finales potentielles.

Le terme optimal dit en cela bien ce qu'il veut dire "qui demande le minimum de traitement possible" ;)

Evidemment, si tu trouve une solution en 90 ou en 100 déplacements sans (par exemple) errements, ta solution sera validée, bien que n'étant pas "optimale" pour autant que l'âne rouge se trouve bel et bien à la place qui lui est assignée ;)

En effet, les 81 déplacements dont il est question dans l'énoncé sont donnés à titre indicatif, car c'est LA solution par excellence qui n'a pas encore pu être battue ;)

Par contre, il s'agit de veiller à supprimer de la solution tous les errements dus à la recherche, ne serait-ce que parce que c'est sans doute encore le meilleur moyen d'avoir une chance d'obtenir le résultat souhaité ;)

Citation:

---

Envoyé par koala01

En effet, les 81 déplacements dont il est question dans l'énoncé sont donnés à titre indicatif, car c'est LA solution par excellence qui n'a pas encore pu être battue ;)

---

Je complète en disant, c'est LA solution optimale pour cette position initiale.

C'est tout bon !

Merci pour les éclaircissement.

Je complète un point que j'avais laissé en suspens lors de la rédaction du défi : je ne savais pas si il y avait des solutions impossibles.

J'en suis sûr maintenant, il y a bien des positions initiales qui n'ont pas de solution, je vous laisse en trouver quelques unes car il y en a beaucoup.

Votre programme devra donc tenir compte de cela et réagir correctement lorsqu'il se trouve en face d'un tel cas de figure.

La page du défi a été modifiée en conséquence.

La solution animée sur Wikipédia compte bien 81 coups cependant :

• quand il y a déplacement d'un carré en x puis en y ou en y puis en x ça n'est compté que comme 1 seul coup
• quand une barre est déplacée de deux cases c'est aussi compté comme 1 seul coup
• j'ai cru comprendre que dans le cadre du défi il fallait compter 2 coups pour ces mouvements

Citation:

---

Je complète en disant, c'est LA solution optimale pour cette position initiale.

---

C'est discutable. C'est la solution publiée par Martin Gardner en 1964.
SBPSolver trouve une solution en 59 coups différente de celle de Martin Gardner, mais là encore il compte différemment, il peut bouger plusieurs blocs en un seul mouvement.

J'ai l'intention de produire une solution en langage Objective-Caml.
En fait je l'ai déjà terminée (il ne reste plus qu'à déboguer :aie:).
Pouvez-vous me donner une démarche à suivre pour participer autant que possible sans perturber le déroulement du défi C ?
(puis-je poster un lien vers un exécutable, puis-je l'uploader sur le serveur du défi, dois-je occulter ma source et mes algos, ...)

:merci:

Effectivement, il faut comparer ce qui est comparable. Donc les 81 coups de Wikipédia ne pourront pas être comparés avec ce défi car le comptage des coups n'est pas tout à fait pareil.

Citation:

---

Envoyé par SpiceGuid

• quand il y a déplacement d'un carré en x puis en y ou en y puis en x ça n'est compté que comme 1 seul coup
• quand une barre est déplacée de deux cases c'est aussi compté comme 1 seul coup
• j'ai cru comprendre que dans le cadre du défi il fallait compter 2 coups pour ces mouvements

---

OUI, dans ce défi, un objet déplacé de 2 cases (quelque soit l'objet), cela doit être compté comme 2 coups.

Pour l'instant je trouve 8 solutions en 116 coups, 46s à 1Ghz et 56Mo de mémoire.

Ma configuration initiale :

Code:

---

1 2 3 4 5 6

GLLH GLLH IKKJ ICDJ EABF

---

Une des 8 solutions en 116 mouvements, qui n'est ni celle de Martin Gardner ni celle de SBPSolver :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Right E. Down I. Left F. Left K. Down J. Up D. Right D. Right K. Up I. Left E. Left F. Left J. Down D. Right K. Up C. Up F. Right E. Down I. Left C. Left K. Down H. Down D. Down H. Right L. Right G. Up C. Up I. Up C. Up I. Left F. Left E. Left J. Left D. Down H. Right K. Up J. Up D. Right E. Right E. Down J. Down G. Right C. Up I. Up F. Left J. Down G. Down G. Right F. Up F. Left K. Up H. Right E. Left K. Down D. Left H. Up E. Right D. Down H. Right K. Down I. Left C. Right K. Up F. Up G. Up G. Left H. Left D. Down E. Down K. Down L. Right F. Right F. Right C. Right C. Up G. Up H. Up I. Left D. Up J. Left E. Left D. Left E. Down K. Down L. Down C. Right C. Right G. Up H. Up H. Left L. Down C. Down F. Down C. Down F. Right G. Right H. Right I. Up J. Up J. Left L. Left C. Up C. Up K. Right E. Right E. Right D. Right D. Down L. Left C. Left F. Left C. Left F. Up K. Up E. Right D. Right L.

---

Voilà une configuration qui n'a pas de solutions :)

Code:

---

1 2 3 4 5

LLKA LLKB JJII GGHH CDEF

---

Sinon on peut arriver à la solution en 6200 coups sans jamais retomber sur la même configuration! oO

Peut-être qu'il faudrait changer 81 coups en 116 coups dans la page du défi? (pour ceux qui s'arracheront les cheveux en ne trouvant pas 81 coups :aie:)

Citation:

---

Envoyé par coyotte507

Peut-être qu'il faudrait changer 81 coups en 116 coups dans la page du défi? (pour ceux qui s'arracheront les cheveux en ne trouvant pas 81 coups :aie:)

---

Je veux d'abord attendre d'être sûr que 116 coups, c'est LA solution optimale.

Je crois de mon coté qu'il faut s'attacher à ce qui a *reellement* de l'importance...

Le nombre de coups à jouer pour obtenir une solution n'est clairement pas le sujet le plus important du défi:

Qu'avec une position de départ donnée, la solution optimale soit réalisable en 70, 86 ou 116 coups dépend entièrement de la position de départ et n'influe absolument pas dans la résolution du défi qui vous est proposé ici, ni dans la note que vous obtiendrez si vous décidez de le relever.

Ce qui importe par contre c'est que votre application soit en mesure soit de trouver une solution (si possible la solution optimale) à une situation de départ donnée, soit de nous indiquer qu'il n'y a pas de solution, s'il apparait qu'il n'y en a effectivement pas, soit encore de nous faire savoir que le fichier qui est destiné à nous donner la situation initiale n'est pas valide.

Pour le reste, la notion même de solution optimale tient beaucoup plus à l'intérêt de trouver cette solution particulière qu'à une "limite" à respecter en terme de nombre de coups à jouer ;)

Citation:

---

Envoyé par coyotte507

Sinon on peut arriver à la solution en 6200 coups sans jamais retomber sur la même configuration! oO

---

Approche originale et solution originale ;)

Je pense aussi que 116 coups c'est à titre indicatif, pour déboguer votre programme c'est mieux si vous avez une limite concrête.

Citation:

---

Envoyé par koala01

soit de nous indiquer qu'il n'y a pas de solution, s'il apparait qu'il n'y en a effectivement pas

---

Ça veut dire quoi "effectivement" ?
Avec quel algorithme ?

• il n'y a pas de résultat théorique connu sur le sujet
• le résultat d'Erik Demaine sur la PSPACE-complétude du problème incite à penser qu'en fait ça pourrait ne pas être décidable (ça reviendrait à faire une preuve de non-terminaison pour une machine de Turing universelle)

J'ai été tenté de résoudre ce défi (en C) par curiosité (je n'ai pas le droit de concourir :( ).
Finalement, j'arrive à une solution en 116 coups, après avoir examiné à peu près 24000 configurations (ce qui est finalement assez peu) et utilisé 500kbytes environ d'allocation dynamique de mémoire, en un peu moins de 0.18s (Athlon 32bits 2.2Ghz).

Je pense (évidemment) que 116 coups est certainement la solution optimale (pour la position initiale proposée) avec le critère retenu pour le compte des coups qui simplifie très notablement le problème. Ceci fait qu'effectivement, on ne peut pas, à mon avis, le retenir comme critère de notation (sauf peut être comme un malus si ce chiffre est dépassé car il y a alors un problème dans l'algorithme utilisé). Durcir les critères retenus pour le compte des coups donnerait lieu à un défi plus sélectif (mais peut-être dissuasif).