Problème du cavalier

Mon prof d'algo m'a donné un SUPER problème qu'évidemment je n'arrive pas à résoudre... 8-)

Voici ce super truc :
Trouver un algorithme tel que la cavalier du jeu d'échec passe sur toutes les cases.

N.B: Lol
Pour info les déplacements possibles par un cavalier : Pièce jointe 397229

Donc me voilà dedans. Voici l'algo que j'ai pondu:

Code:

---

1 2 3 4 5 6

Tant que la file est non vide*:   Pour i dans l’ensemble des positions*:   déplacer le cavalier Si la case n’est pas dans la file*: tester la position suivante

---

Donc le cavalier tourne dans ses positions. Mais si la case à déjà été chevauchée (XD) on va au suivant.

J'aimerais avoir vos avis merci.

s

Code:

---

1 2 3 4 5 6

Tant que la file est non vide*:   Pour i dans l’ensemble des positions*:   déplacer le cavalier Si la case n’est pas dans la file*: tester la position suivante

---

Tu as donc une file.
Soit cette file est vide au début du traitement, et dans ce cas, le programme s'arrête immédiatement.
Soit cette file est non-vide, et comme il n'y a aucune instruction qui modifie cette file, le programme va boucler indéfiniment.

Tu es très loin, très très loin de la solution.
Ton programme doit pouvoir gérer des cas comme ça : le cavalier a le choix entre le mouvement A1 A1 A3 ... , explorons le mouvement A1. Au 2ème mouvement, on n'a pas le choix, seule option = B1... explorons B1. Zut plus de mouvement possible. Revenons en arrière. Et donc il faut considérer le mouvement A2 au lieu de A1.

Le mot clé pour t'aider, c'est :parcours d'arbre.

hello,

Citation:

---

J'aimerais avoir vos avis merci.

---

l'idée est correcte.

il faut etre plus précis en revanche:

Code:

---

1 2 3 4 5 6 7 8 9 10

pour la position actuelle pour chaque case de destination possible du cheval (pas seulement "la suivante") si case visitée rien faire... sinon marquer case actuelle comme visitée visiter(case) demarquer case actuelle comme visitée finsi

---

il reste à définir la condition d'arret, ainsi que "backtracker" l'information que l'arret a été satisfait (ou qu'il n'y a pas de solutions??)

salut

tu peut travailler par symétrie avec un cavalier

nous savons que celui ci se déplace de deux case sur un axe est d'une case sur l'autre ce qui pourrait nous faire penser a cercle de défense
nous savons qu'un cercle a 4 quadrants avec ces deux information tu n'as besoin de connaitre que deux déplacements
le reste étant des symétrie, il te faut donc connaitre disons le déplacement selon l'axe des x et celui des y

si nous comptons bien le cheval ne peut donc avoir que 8 déplacements possible 4 horizontales et 4 verticales



mes deux cents ;)

salut

tu peut pour simplifier ta recherche de parcourt noter les case
par exemple par le nombre de possibilité de saut

exemple pour un echiquier de 8 par 8

2	3	4	4	4	4	3	2
3	4	6	6	6	6	4	3
4	6	8	8	8	8	6	4
4	6	8	8	8	8	6	4
4	6	8	8	8	8	6	4
4	6	8	8	8	8	6	4
3	4	6	6	6	6	4	3
2	3	4	4	4	4	3	2

a chaque saut tu décrément de 1 les cases "a proximité" de la case selectionné
et tu met la case sélectionné a zéro ensuite tu cherche la case "a proximité"
ayant le moins de possibilité sauf évidement les case a zéro puisque qu'elles sont
déjà utilisé

Intéressante application de la récursivité.Pièce jointe 399212