Discussion :

[bj303931]

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

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 :

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[tbc92]

s

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Invité]

hello,

J'aimerais avoir vos avis merci.

l'idée est correcte.

il faut etre plus précis en revanche:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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??)

[anapurna]

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

[anapurna]

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é

[Nebulix]

Intéressante application de la récursivité.