Salut,
Ravi que nous soyons au moins une petite poignée sur le sujet.
Perso, je ne sais pas si je suis d'accord avec Marge vu que j'ai rien compris.
Alors je passe.
J'ai donc fait tourner une casio fx-CP400 toute la nuit sur un échiquier 5x5 en commençant dans un coin (je l'ai laissée tourner 2 heures avant de me coucher). L'écran affiche l'échiquier au fur et à mesure des déplacements.
Le programme sauvegarde juste l'image de l'écran lorsque l'échiquier est complet.
Et au matin, j'avais une solution avec un joli écran et les 25 positions successives de mon cavalier... mais pas d'info sur la longueur du traitement.
Du coup, j'ai relancé ce matin sur un échiquier 6x6 avant de quitter la maison non sans avoir ajouté deux compteurs que j'affiche à l'écran en fin de traitement:
- le nombre total de coups en avant de mon cavalier,
- le nombre total de coups en arrière (en cas de blocage).
Mon algo est pour l'instant ultra bestial. Les huit déplacements possibles rappelés par c.ret sont numérotés (n = 1...8 ).
J'avance mon cheval sur une case libre en commençant par n=1.
Lorsque je suis bloqué (pas de prochaine case libre), j'annule le précédent déplacement n et je passe au n suivant.
Si je suis déjà à n=8, je remonte encore d'un déplacement et ainsi de suite.
Quelles sont vos pistes d'optimisation ?
J'attends impatiemment vos retours.
De mon côté, je vais essayer de voir si la traque des cases orphelines (c'est à dire impossible à rallier) n'est pas un moyen économe de couper une branche par anticipation. J'ai juste peur que le temps passé à les détecter soit contre-productif.
Je vais peut-être commencer par les cases orphelines sur les côtés, plus rapidement décelables.
Autre optimisation possible mais qui rend l'usage moins sympa et ne respecte pas le cahier des charges : ne rien afficher avant la fin ou seulement tous les NB déplacements. En effet, afficher chaque coup en avant et effacer chaque coup en arrière consomme certainement énormément…
A suivre,
Rem : il est difficile de comparer deux programmes différents. Le nombre de coups pour atteindre la solution dépend du sens de parcours des déplacements possibles à chaque étape.
Les plus belles, les solutions fermées, permettent de rejoindre la première case à partir de la dernière case visitée.
Dans une solution fermée, toute position de départ peux conduire à la solution dans les deux sens de circulation.
