[Jeu d'échecs] Problème du cavalier

Bonjour,

Je cherche à résoudre un problème voisin du problème connu du cavalier (parcours de toutes les cases):

Trouver pour un cavalier le chemin le plus court pour aller d'une case départ à une case arrivée.

Il me parait naturel de qualifier de chemin le plus court celui qui demande le moins de coups (avec en question annexe, y-en-a-t-il plusieurs et dans ce cas les trouver tous).

Par contre, dans la stratégie d'approche, faut-il privilégier la recherche de tous les chemins qui aboutissent à la case arrivée, et ne conserver que le(s) plus courts, ou bien imaginer un critère de proximité-rapprochement au plus près de la case arrivée. Le critère serait alors la "distance" de la case départ (ou de la (des) suivante(s)) à la case d'arrivée. Comment alors qualifier la distance ? nombre de cases à parcourir ? distance géométrique de centre à centre ? ...

A vos neurones.

Merci

Tu pourrais utiliser l'algorithme de Dijkstra.

Pour l'exemple, en partant de la position (0, 0) l'algorithme te donnera le résultat suivant:

Code:

---

1 2 3 4 5 6 7 8 9

0 3 2 3 2 3 4 5 3 4 1 2 3 4 3 4 2 1 4 3 2 3 4 5 3 2 3 2 3 4 3 4 2 3 2 3 4 3 4 5 3 4 3 4 3 4 5 4 4 3 4 3 4 5 4 5 5 4 5 4 5 4 5 6

---

Si j'ai bien compris, le critère retenu est le nombre de coups.
Chaque case, à partir de la case origine, est marquée avec la longueur du chemin pour y arriver, et ainsi de suite.
Pour une case déjà marquée, si le marquage trouvé (la longueur du chemin) est supérieur au marquage effectué, on passe au marquage suivant.
Jusqu'à avoir marqué toutes les cases.
Tous les chemins sont mémorisés, et il suffit alors d'extraire ceux qui aboutissent à la case destination.

Je m'y colle bientôt (j'avais oublié l'algorithme de Dijkstra que j'ai étudié il y a trente ans environ) avec du code Python, et je publie :P le résultat.

Merci