"Retour sur trace" - backtracking

Bonjour,

Voila, j'ai un petit soucis avec un morceau de code. Mon programme consiste a trouver comment positionner 8 reines sur un échiquier de taille N sans qu'aucune d'entre elles ne soient en prise. Ce qui pose problème, c'est malheureusement la partie la plus importante :roll:

http://pastebin.com/andqRWv3

Je comprends pas pourquoi cette fonction ne fonctionne pas, quelqu'un pourrait il m'éclairer svp ? :aie:

Salut !

Si tu dois placer 8 reines, il faudrait peut-être pouvoir t'arrêter justement quand les 8 sont placées :aie:.

Donc tu stopperas la récursivité une fois que 8 reines seront placées (tu dois donc passer en paramètre le nombre de reine restante à placer).

Ensuite, avoir une variable globale n'est jamais conseillé, c'est mieux si tu la passes en paramètre également.

Code:

---

1 2 3

if(colonne == N-1){ ligne++; }

---

Ce que tu fais : lorsqu'on est sur la dernière colonne, on augmente d'une ligne. Mais on reste quand même sur la dernière colonne...

Code:

---

while(ligne < N && colonne < N){

---

Ça pose aussi un petit souci, ça veut dire qu'une fois que tu as parcouru toute une ligne, tu t'arrêtes, sans essayer les prochaines lignes.

Le mieux (à mon avis) c'est de faire quelque chose comme ça :

Code:

---

1 2 3 4 5 6 7

for(; ligne < N && reine_restante != 0; ++ligne) { for(colonne %= N; colonne < N && reine_restante != 0; ++colonne) // colonne %= N permet de ne pas ré-initialiser la variable colonne à zéro à la première itération (et utiliser la valeur reçue en paramètre) mais aux prochaines { //... } }

---

La variable "reine_restante" permet de t'arrêter quand tu as réussi à placer toutes les reines.

Code:

---

1 2 3

printf("\nReine ajoute en (%d,%d)", ligne, colonne); grid[ligne][colonne] = 1; showSolution(grid);

---

Ca doit t'en faire de l'affichage, ce n'est peut-être pas utile.

Citation:

---

Envoyé par nurks

Bonjour,

Voila, j'ai un petit soucis avec un morceau de code. Mon programme consiste a trouver comment positionner 8 reines sur un échiquier de taille N sans qu'aucune d'entre elles ne soient en prise. Ce qui pose problème, c'est malheureusement la partie la plus importante :roll:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

void backtracking(int **grid,int ligne, int colonne){ printf("(ligne: %d, colonne: %d\n", ligne, colonne); while(ligne < N && colonne < N){ printf("test colonne : %d\n",colonne); if(colonne == N-1){ ligne++; } if(acceptable(grid, ligne, colonne) == 1){ printf("\nReine ajoute en (%d,%d)", ligne, colonne); grid[ligne][colonne] = 1; showSolution(grid); backtracking(grid, ligne+1, 0); }else{ colonne ++; } } printf("Solution found ! "); showSolution(grid); }

---

Je comprends pas pourquoi cette fonction ne fonctionne pas, quelqu'un pourrait il m'éclairer svp ? :aie:

---

Salut

Tu aurais pu au-moins avoir la politesse de poster ton code ici au lieu d'envoyer les intervenants (qui prennent de leur temps pour venir ici aider) cliquer sur un lien qui les renvoie sur un autre site. Surtout que ton code n'est pas si long que ça !!!

A chaque niveau de récursivité tu places la reine associée à ce niveau à un emplacement libre. Mais quand la fonction revient des appels récursifs inférieurs, la reine est déplacée sur la case d'à coté mais la case d'où elle vient n'est pas marquée comme étant "libérée"...

Accessoirement le puzzle est résolu quand les 8 reines sont placées. Mais pour que tu saches qu'elle en a placé 8, il te faut une info pour ça. Par exemple une variable qui enregistre la profondeur courante et une autre qui enregistre la profondeur max atteinte. Dès qu'une reine de profondeur X est placée, si X est plus grand que le max alors le max récupère ce X.
Remonté au niveau principal, si le niveau max vaut 8 ça veut dire que tu auras réussi à placer tes 8 reines...

salut !
http://c.developpez.com/telecharger/...e-des-N-Reines
rien à rajouter aux posts précédents.

A+

Merci pour vos réponses, ça m'a bien aidé :)