Discussion :

[buddhazero]

Bonjour, je suis en train de programmer une résolution du probléme du cavalier, qui consiste a parcourir toutes les cases d'un echiquier en ne passant qu'une seule fois par case.
J'utilise pour cela le backtracking, il tourne bien dés qu'il est bloqué (sinon il joue toujours le premier coup possible), il tente une autre voie.. mais voila, il revient toujours vers les cases de depart...sic..
Quelqu'un pourrait-il m'expliquer pourquoi..?
Et pour le code, je sais qu'il n'est pas trés propre, mais je suis tellement embété du fait que ca tourne pas ... j'attends que ca fonctionne pour l'ameliorer.
Amicalement.

nb: J'ai oublié de dire qu'il seg/fault au bout d'une trentaine de secondes de recherches (je ne pense pas que ce soit par depassement de tableau, car je demande 20000 cases, et il n'effectue que 2000 tests et des poussiéres

[ToTo13]

Bonjour,

je viens de jeter un coup d'oeil à ta fonction boucle et je pense que le problème vient de là.
Si j'ai bien compris, "chemin[x][y]=1;" signifie que la case a été visitée par le cavalier.
Et bien il faut mettre à 1 chaque fois que tu vas visiter la case, puis remettre à 0 afin de pouvoir faire la backtrack.

Code C :

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

1
2
3
4
5
6
7
 
if ( CoupValide(x+r,y+c) )
   {
   chemin[x+r][y+c] = 1 ; // La case est jouée...
   boucle(x+r,y+c) ; // On y va
   chemin[x+r][y+c] = 0 ; // On backtrack, donc la case n'est plus jouée...
   }

[buddhazero]

Je ne pense pas que le problème vienne de là, car la valeur qur reçoit 'chemin[x][y]' à chaque tour n'est pas 1, mais le numéro du tour joué, c'est plus pratique pour moi de faire comme ça parce que je n'ai pas a garder en memoire les coups joués, un max du tableau me donne le dernier coup,
qu'en pensez-vous ?

[ToTo13]

Bonjour,

je pense que c'est une solution, voire même une bonne idée, mais qu'il faut quand même supprimer la valeur pour pouvoir backtracker sinon la case sera toujours considérée comme étant visitée...
Donc on aura quelque chose comme ça :

Code C :

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

1
2
3
4
5
6
7
8
9
 
if ( coup == 64 ) {...}
...
if ( CoupValide(x+r,y+c) )
   {
   chemin[x+r][y+c] = Coup ; // La case est jouée...
   boucle(x+r,y+c, Coup+1) ; // On y va
   chemin[x+r][y+c] = 0 ; // On backtrack, donc la case n'est plus jouée...
   }

[buddhazero]

Ok merci, j'ai passé la journée a refondre le code, et là j'ai quelque chose qui tourne a peu prés, tout dans mon code était de travers,
moralité: toujours penser a l'avance a toutes les fonctions, une sorte de plan-schéma de la mort,
ou rien ne peut t'echapper et prévoir des plans B, C ...Z
Bon pour delestage !

Merci pour l'attention accordée aux messages ToTo13.
Amicalement.