BackTracking |
|
Prenons le problème des huit
reines, on
essaie de placer une reine par colonne, la première en ligne 1, la deuxième en ligne 3, la troisième en ligne 5, la quatrième en ligne 2, la cinquième en ligne 4, pour la 6ième aucune ligne ne convient !... On va donc être obligé de remettre en cause les positions des reines déjà en place: voila le principe du retour sur trace, backtracking.... |
|
On essaiera donc de placer la cinquième reine en ligne 8, la première prochaine position possible, mais aucune ligne ne convient quand même pour la reine 6!... | |
Comme on a épuisé toutes les possibilités pour la reine 5, il va falloir "backtracker" jusqu'à la reine 4 qui viendra en ligne 7,on pourra alors placer la reine 5 en ligne 2, la 6 en ligne 4, la 7 en 6, mais on n'arrivera pas à placer la 8 ....une fois encore il faudra backtracker... Heureusement la récursivité va
nous
permettre d'écrire une procédure qui fera tout cela simplement... |
PositionneReine(N) { |