Récursivité pour placer des reines

Notions utilisées

récursivité
tableaux dynamiques à deux dimensions

Cahier des charges

On considère un échiquier carré ayant un nombre quelconque, noté ici dim, de lignes (et de colonnes). On dispose de dim reines ; il s'agit de placer toutes les reines sur l'échiquier de façon à ce que deux quelconques ne soient pas en prises ; cela signifie qu'il ne doit pas y avoir deux reines sur une même ligne, ou sur une même colonne, ou sur une même parallèle à une diagonale. Le programme doit déterminer et afficher toutes les solutions possibles. Les lignes et les colonnes sont numérotées à partir de 0.

Spécifications

On utilise un tableau dynamique à deux dimensions d'entiers correspondant aux cases de l'échiquier. Ce tableau est initialisé en mettant la valeur dim dans toutes les cases, ce qui signifie que toutes les cases sont au départ disponibles. Lorsqu'une case n'est plus libre, c'est-à-dire lorsqu'une reine déjà placée interdit de mettre une nouvelle reine dans cette case, l'entier contenu par la case corresondante du tableau est le plus petit indice de colonne d'une reine interdisant cette case.
On utilise aussi un tableau dynamique de longueur dim pour noter, par colonne, la ligne de la reine placée.
Les deux tableaux dynamiques sont désalloués à la fin du programme.

On utilise récursivement une fonction de prototype :

void cherche (int colonne);
Losque l'on rentre dans cette fonction, les reines des colonnes 0, 1, ..., colonne - 1 sont déjà placées. Cette fonction cherche toutes les solutions possibles avec les reines des colonnes 0, 1, ..., colonne - 1 placées comme actuellement. Si colonne vaut dim - 1, les solutions sont affichées au fur et à mesure où elles sont trouvées. Sinon, pour chaque case libre de la colonne d'indice colonne :

on positionne une reine dans cette case ;
on note à "droite" de cette case les cases nouvellement interdites par la reine que l'on vient de positionner en y mettant un entier égal à colonne ;
on appelle la fonction cherche avec le paramètre égal à colonne + 1 ;
on retire la reine que l'on vient de positionner ce qui signifie qu'on "libère" les cases interdites par cette reine (et pas interdites par une reine qui se trouverait plus "à gauche" sur l'échiquier).

Corrigé

Voir le corrigé

Irene Charon

Last modified: Tue Sep 7 16:20:28 MET DST 1999