Le problème des huit reines

Un problème dont tout le monde a entendu parler et qui peut se résoudre facilement par l'ordinateur est le suivant: comment placer 8 reines sur un échiquier sans que chacune "mange" au moins une des 7 autres ?

Ce problème se résout par des essais successifs; on applique la récursivité. Nous allons présenter ici plusieurs solutions, à commencer d'abord par une solution itérative, que nous transformerons ensuite en une solution récursive.

Première solution, itérative :

On dispose de l'échiquier, qui est vide au début. On sauvegarde l'échiquier dans un tableau auxiliaire. On fait 8 boucles imbriquées qui représentent les 8 lignes; chaque boucle va de 0 à 7 ce qui représente une boucle de la première colonne à la huitième colonne. On utilise aussi une chaîne de caractères qui va représenter les positions des reines sur l'échiquier.

Pour chaque position définie par les coordonnées "ligne,colonne" :

- on vérifie si la case est vide

- si oui alors :

- on occupe toutes les cases de l'échiquier dans les cinq directions décrites ci-dessous à partir de la position actuelle

- on mémorise la colonne dans une chaîne de caractères, qui représente en réalité la position da la reine se trouvant sur la ligne en cours

- on sauvegarde l'échiquier car il sera modifié par les coups suivants

- on passe à la ligne suivante, à la première colonne

- si on est à la dernière ligne alors on affiche la chaîne

- sinon :

- on essaye la colonne suivante

- si on est à la huitième colonne on sort de la boucle et on restaure

l'échiquier

Voici les cinq directions dont il s'agissait ci-dessus :

+--------+ X représente une reine.

¦ ¦

¦444X0000¦ Etant donné qu'on pose les 8 reines en descendant sur

¦ 321 ¦ l'échiquier, cela n'a pas de sens de compléter les 3

¦ 3 2 1 ¦ directions vers le haut, car on vient d'en haut et l'échiquier

¦3 2 1 ¦ a déjà été complété par un coup précédent.

+--------+

const max = 8;
 dx: array[0..4] of integer = (1, 1, 0, -1, -1);
 dy: array[0..4] of integer = (0, 1, 1, 1, 0);
 
type tab = array[0..max - 1, 0..max - 1] of byte;
 
procedure occuper_toutes_les_directions(var tt: tab; xx, yy, valeur: byte);
var i, colonne, ligne: integer;
begin
 tt[xx, yy] := valeur;
 for i := 0 to 4 do
 begin
 colonne := xx; ligne := yy;
 inc(colonne, dx[i]); inc(ligne, dy[i]);
  while (ligne in [0..7]) and (colonne in [0..7]) do
 begin
 tt[ligne, colonne] := valeur;
 inc(colonne, dx[i]); inc(ligne, dy[i]);
 end;
 end;
end;
 
procedure jouer;
var x0, x1, x2, x3, x4, x5, x6, x7: byte;
 st: string[8];
 tab_sauve: array[0..7] of tab;
begin
 st := ' '; // pour mémoriser les positions
 fillchar(t[0], sizeof(t), #0); // initialisation plateau
 move(t, tab_sauve[0], 64);
 form1.memo1.lines.clear;
 for x0 := 0 to max - 1 do
 if t[0, x0] = 0 then
 begin
  occuper_toutes_les_directions(t, x0, 0, 2);
 st[1] := chr(48 + x0);
 move(t, tab_sauve[1], 64);
 for x1 := 0 to max - 1 do
 if t[1, x1] = 0 then
 begin
 occuper_toutes_les_directions(t, x1, 1, 2);
 st[2] := chr(48 + x1);
 move(t, tab_sauve[2], 64);
 for x2 := 0 to max - 1 do
 if t[2, x2] = 0 then
 begin
 occuper_toutes_les_directions(t, x2, 2, 2);
 st[3] := chr(48 + x2);
 move(t, tab_sauve[3], 64);
 for x3 := 0 to max - 1 do
 if t[3, x3] = 0 then
 begin
 occuper_toutes_les_directions(t, x3, 3, 2);
 st[4] := chr(48 + x3);
 move(t, tab_sauve[4], 64);
 for x4 := 0 to max - 1 do
 if t[4, x4] = 0 then
 begin
 occuper_toutes_les_directions(t, x4, 4, 2);
 st[5] := chr(48 + x4);
  move(t, tab_sauve[5], 64);
 for x5 := 0 to max - 1 do
 if t[5, x5] = 0 then
 begin
 occuper_toutes_les_directions(t, x5, 5, 2);
 st[6] := chr(48 + x5);
 move(t, tab_sauve[6], 64);
 for x6 := 0 to max - 1 do
 if t[6, x6] = 0 then
 begin
 occuper_toutes_les_directions(t, x6, 6, 2);
 st[7] := chr(48 + x6);
 for x7 := 0 to max - 1 do
 if t[7, x7] = 0 then
 form1.memo1.lines.add(st + chr(48 + x7));
 move(tab_sauve[6], t, 64);
 end;
 move(tab_sauve[5], t, 64);
 end;
 move(tab_sauve[4], t, 64);
 end;
  move(tab_sauve[3], t, 64);
 end;
 move(tab_sauve[2], t, 64);
 end;
 move(tab_sauve[1], t, 64);
 end;
 move(tab_sauve[0], t, 64);
 end;
end;
 

Deuxième solution, récursive :

Nous allons maintenant transformer toutes ces boucles imbriquées en une procédure récursive, comme on l'a déjà vu.

En tenant compte du fait que la récursivité a la propriété d'empiler les variables locales à une procédure, nous allons déclarer un échiquier local dans lequel on va faire les sauvegardes de l'échiquier, ainsi que la position du pion en cours, c'est à dire la chaîne "st".

Etant donné que la procédure comporte huit boucles, nous allons rajouter un paramètre à la procédure "jouer", qui représente le numéro de la ligne, et un autre paramètre pour la chaîne de caractères; en même temps il ne faut pas oublier que d'une procédure à l'autre (en réalité d'un niveau "n" pendant la récursivité, au niveau "n+1") on doit transmettre l'échiquier.

procedure jouer1(ligne: integer; var t: tab; st: string); // récursive 1
var colonne: byte;
 tab_sauve: tab;
begin
 move(t, tab_sauve, 64);
 for colonne := 0 to max - 1 do
 if t[ligne, colonne] = 0 then
 begin
 occuper_toutes_les_directions(t, colonne, ligne, 2);
 if ligne < 7 then
 jouer1(ligne + 1, st + chr(49 + colonne))
 else
 form1.memo1.lines.add(st + chr(49 + colonne));
 move(tab_sauve, t, 64);
 end;
end;
 

Troisième solution, récursive :

Nous allons voir maintenant comment on peut améliorer ce programme du point de vue de la rapidité; pour commencer, nous n'allons plus remplir l'échiquier dans les 5 directions à chaque coup, mais nous allons vérifier si une case se trouve dans la ligne de mire d'une reine précédente; pour cela on fait une fonction "occupé", qui ne vérifie que les trois directions manquantes, celles qui vont vers le haut.

const max = 8;
 dx2: array[0..2] of integer = (-1, 0, 1);
 dy2: array[0..2] of integer = (-1, -1, -1);
 
function occupe2(x, y: integer; t: tab): boolean;
var i, colonne, ligne: integer;
 sortir: boolean;
begin
 i := -1; sortir := false;
 repeat
 inc(i); colonne := x; ligne := y;
 dec(colonne, dx2[i]); dec(ligne, dy2[i]);
 repeat
 inc(colonne, dx2[i]); inc(ligne, dy2[i]);
 if (colonne in [0..max - 1]) and (ligne >= 0) then
 sortir := (t[ligne, colonne] <> 0);
 until (colonne = -1) or (colonne = max) or (ligne = -1) or sortir;
 until (i = 2) or sortir; // i=0,1,2 : les trois directions
 occupe2 := sortir;
end;
 
procedure jouer2(ligne: byte; var t: tab; st: string);
var x: byte;
begin
 for x := 0 to max - 1 do
 if not occupe2(x, ligne) then
 begin
 t[ligne, x] := 1; // on pose une reine
  if ligne < max - 1 then
 jouer(ligne + 1, t, st + chr(49 + x))
 else
 form1.memo1.lines.add(st + chr(49 + x));
 t[ligne, x] := 0; // on enlève la reine
 end;
end;
 

Quatrième solution, récursive :

Il y a d'autres solutions à ce problème. Par exemple, l'échiquier est représenté par une chaîne de 8 caractères. Chacun des 8 caractères représente une ligne de l'échiquier, et la colonne est représentée par le numéro inscrit dans la chaîne.

Supposons qu'on a la situation suivante :

- une reine en ligne 1, colonne 1

- une reine en ligne 2, colonne 3

- une reine en ligne 3, colonne 5

La chaîne est donc égale à : st='13500000'.

Supposons qu'on veuille placer une reine sur la quatrième ligne; pour cela il faut que la quatrième ligne de l'échiquier soit vide, c'est à dire qu'il faut que le quatrième élément de la chaîne soit '0'.

Ensuite il faut parcourir les huit colonnes de cette ligne et dès qu'il y a une case qui ne soit pas en danger, y placer une reine. Pour savoir si la case n'est pas en danger il faut vérifier si la colonne n'a pas déjà été occupée.

Ainsi si on veut placer une reine en quatrième ligne et première colonne, on ne peut pas car la première colonne (notée par "1" dans la chaîne "st" ) a déjà été utilisée par la première reine.

Par contre la deuxième colonne n'a pas encore été utilisée, car la chaîne "st" ne contient pas le chiffre "2"; pour savoir si on peut placer une reine, il ne nous reste plus qu'à vérifier les diagonales en partant de la position actuelle qui est ligne 4, colonne 2; il ne faut pas qu'on ait une reine sur les positions suivantes:

ligne 3, colonne 1 ---> première diagonale, gauche,haut

ligne 3, colonne 3 +

ligne 2, colonne 4 ¦--> deuxième diagonale, droite, haut

ligne 1, colonne 5 +

On remarque que pour faire les tests sur la diagonale on décrémente de 1 la ligne et on décrémente (ou incrémente) de 1 la colonne, et ceci jusqu'à sortir de l'échiquier (en fait arriver aux bords de "st") ou rencontrer une reine. La fonction qui vérifie les diagonales s'appelle "test" et elle est récursive. La procédure qui place les reines sur l'échiquier est elle aussi récursive. On a le programme :

function test(ligne, colonne, delta: integer; var st: string): boolean;
begin
 if (ligne in [0, max + 1]) or (colonne in [0, max + 1]) then
 test := true
 else
 test := (st[ligne] <> chr(48 + colonne)) and test(ligne - 1, colonne + delta, delta, st)
end;
 
procedure jouer3(lg: integer; st: string);
var col: integer;
begin
 if lg = max + 1 then
 form1.memo1.lines.add(st)
 else
 for col := 1 to max do
 if (pos(chr(col + 48), st) = 0) and test(lg, col, -1, st) and test(lg, col, 1, st) then
 begin
 st[lg] := chr(48 + col);
 jouer3(lg + 1, st);
 st[lg] := '0';
 end;
end;
 

Et voici les appels à chacune de ces quatre procédures :

procedure TForm1.Button1Click(Sender: TObject);
var t: tab;
begin // cherche solution
 memo1.Clear;
//---- solution itérative à 8 boucles
// jouer;
 
//---- solution récursive 1
//fillchar(t,sizeof(t),#0);
//jouer1(0,t,'');
 
//---- solution récursive 2
//fillchar(t,sizeof(t),#0);
//jouer2(0,t,'');
 
//---- solution récursive 3
 jouer3(1, ' '); // chaîne de 8 espaces
end;

Télécharger le code source Delphi