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