Discussion :

[Spahi]

Salut les gars, je sais pas si quelqu'un peut m'aider pour cela, mais toute aide est toujours la bienvenue.

Je dois rendre un travail en informatique pour vendredi où le but est de créer un algorithme qui fait voyager le cavalier d'un jeu d'échec par toutes les cases de l'échiquier sans passer 2 fois par la même case). Il faut utiliser un le backtracking je sais pas si vous savez ce que c'est mais ca consiste en le fait que tu retournes en arrière si la solution trouvée n'est pas bonne (exemple : on fait x déplacements et il s'avère que pour le x+1ème déplacement, on se retrouve soit en dehors de l'échiquier, soit sur une case déjà jouée, on doit donc revenir en arrière pour trouver la solution correcte, qui nous permet de continuer le problème !)

Donc je voulais savoir si quelqu'un pouvait m'aider là-dessus...

Merci d'avance !

[ToTo13]

Bonjour,

- tu démarres d'une case de l'échiquier.
- tu marques que cette case a été visitée.
- tu calcules toutes les cases non visitées où tu peux aller.
- tu rappelles ta fonction avec les cases possibles.
- (ne pas oublier de libérer les cases lors du backtrack).

[Trap D]

Bonjour,

- tu démarres d'une case de l'échiquier.
- tu marques que cette case a été visitée.
- tu calcules toutes les cases non visitées où tu peux aller.
- tu rappelles ta fonction avec les cases possibles.
- (ne pas oublier de libérer les cases lors du backtrack).

Prolog fait ça tout seul !

[ToTo13]

Prolog fait ça tout seul !

C'est quoi ça Prolog ???
Je croyais être le seul à en avoir fait parce que mes profs en étaient les concepteurs...

[Trap D]

Je croyais être le seul à en avoir fait parce que mes profs en étaient les concepteurs...

Prolog is well, alive and living all over the world !

[henderson]

Salut !

http://glouise.developpez.com/Hamilton/

A plus !

[Spahi]

Yes merci, je vais checker tout ca

[Trap D]

Voila un code basique en Prolog qui fait ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
% N est le nombre de lignes de l'échiquier
test(N) :-
	% max est le nombre de caes
	Max is N * N,
	% on crée l'échiquier, une simple liste 
	% dont les éléments ne sont pas initialiséx
	length(L, Max),
	% on lance la recherche
	cavalier(N, 0, Max, 0, 0, L),
	affiche(N, 0, L).
 
% cavalier(NbCol, Coup, Max, Lig, Col, L),
% NbCol est le nombre de colonnes par ligne
% Coup est le numéro du déplacement en cours d'étude
% Max est le noimbre maximum de déplacements
% Lig/ Col : la position courant du cavalier
% L est la liste "échiquier"
 
% ici on est arrive 
cavalier(_, Max, Max, _, _, _) :- !.
 
cavalier(NbCol, N, MaxN, Lg, Cl, L) :-
	% On s'assure d'abord que la position est valide
	Lg >= 0, Cl >= 0, Lg < NbCol, Cl < NbCol,
	% On calcule la position de la case sur l'échiquer
	Pos is Lg * NbCol + Cl,
	% on calcule le numéro du coup
	N1 is N+1,
	% on met dans la case le numéro du coup
	% spécificité Prolog, si la case est déjà occupée il y a echec
	% donc backtrack ici
	nth0(Pos, L, N1),
	% on calcule les différentes cases accessibles
	LgM1 is Lg - 1, LgM2 is Lg - 2, LgP1 is Lg + 1, LgP2 is Lg + 2,
	ClM1 is Cl - 1, ClM2 is Cl - 2, ClP1 is Cl + 1, ClP2 is Cl + 2,
	% et on essaye les cases suivantes
	% le ; permet, s'il y a echec d'une recherche, 
	% de continuer avec la suivante
	(
	cavalier(NbCol, N1, MaxN, LgP1, ClM2, L);
	cavalier(NbCol, N1, MaxN, LgP2, ClM1, L);
	cavalier(NbCol, N1, MaxN, LgP2, ClP1, L);
	cavalier(NbCol, N1, MaxN, LgP1, ClP2, L);
	cavalier(NbCol, N1, MaxN, LgM1, ClM2, L);
	cavalier(NbCol, N1, MaxN, LgM2, ClM1, L);
	cavalier(NbCol, N1, MaxN, LgM2, ClP1, L);
	cavalier(NbCol, N1, MaxN, LgM1, ClP2, L)
	).

11 minutes pour trouver un chemin sur l'échiquier de 64 cases !

[pseudocode]

11 minutes pour trouver un chemin sur l'échiquier de 64 cases !

On peut utiliser l'heuristique de Warnsdorff pour avoir des temps raisonnables.

[Trap D]

J'ai dit algo basique !!

[ToTo13]

J'ai dit algo basique !!

Et moi : prolog <=> Basic

[pseudocode]

J'ai dit algo basique !!

Certes, j'en conviens. D'autant plus que l'heuristique de Warnsdorff permet d'implémenter l'algo sans utiliser la récursion/backtracking, ce qui serait hors-sujet d'après le PO.