IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Cours sur la récursivité


précédentsommairesuivant

III. Les échecs

III-A. Le parcours du fou

Nous avons un échiquier et un fou situé dans un coin noir. Il faut faire arriver ce dernier dans le coin opposé, en le faisant passer une seule fois sur une case, dans le même sens de déplacement. Cela signifie que le fou ne peut pas passer deux fois par la même case en ayant le même sens de déplacement.

exemple : un fou a deux sens de déplacement. On décide que le premier sens, nommé A, et le deuxième sens, nommé B, sont indiqués sur les dessins suivants :

Image non disponible
sens A
Image non disponible
sens B

Ainsi, le parcours correspondant à l'image ci-dessous n'est pas possible, car le fou parcourt les cases 1,2,3,4,5,6 sans problème, mais ensuite il va de 7 (numéroté aussi 1) en 8 (numéroté aussi 2) dans le sens B (défini ci-dessus). Or, la case 1 avait déjà été visitée dans le sens B, pour aller dans la case 2. De même, le fou ne peut aller de la case 9 à la case 6 en passant par les cases 2 et 1, car ces deux cases ont déjà été visitées dans le sens B.

Image non disponible

En revanche, le parcours correspondant au dessin suivant est possible, car le fou parcourt les cases 1,2,3 dans le sens B. Ensuite, une fois arrivé en 5 il passe à nouveau dans la case 2 (numérotée aussi 6), mais cette fois-ci dans le sens A. Une fois en 6, il ne pourra aller qu'en 7 car les cases 1 et 3 ont déjà été parcourues dans le sens B, et la case 5 a déjà été parcourue dans le sens A quand on est allé de 5 vers 6.

Image non disponible

Nous allons créer l'algorithme de ce programme. On a un échiquier dont chaque case est associée à deux sens. Pour savoir si toutes les cases ont été parcourues, on ne peut pas compter le nombre de sauts, car on ne sait pas combien il y en a. En effet, le fou peut passer 2 fois sur une même case, et ceci pour n cases. Nous devons donc associer aussi aux cases une valeur booléenne, dont le rôle sera d'indiquer qu'elle a été visitée ou non. Si toutes les cases noires ont été visitées, alors on obtient un total de 32. Pendant le parcours, on doit mémoriser les numéros des cases parcourues, et, comme une case peut être visitée au maximum 2 fois, on a prévu un tableau de mémorisation dont la taille est égale au double du nombre de cases noires. Il est vrai que le fou ne peut aller dans les coins qu'une fois, donc il faudrait enlever 2 au résultat, mais le fait d'ajouter 2 éléments au tableau n'est pas un lourd handicap.

exemple : pour un échiquier de 8*8 cases, il y a (8*8)/2 = 32 cases noires. Le nombre de coups théorique est de 32*2 (passage 2 fois dans chaque case) moins 2 (les coins), soit 62.

Structures des données

 
Sélectionnez
const lim1 = 8;
  lim2 = 8;
type case_ec = record
    sensA,
      sensB,
      visite: boolean;
  end;
  echiquier = array[1..lim1, 1..lim2] of case_ec;
var ech: echiquier; //--- echiquier des coups joués
  coups: array[1..lim1 * lim2] of integer; //--- liste des coups mémorisés

On écrit ensuite la fonction qui vérifie que toutes les cases ont été visitées:

 
Sélectionnez
function tout_a_ete_visite: boolean;
var i, j, total: integer;
begin
  total := 0;
  for i := 1 to lim1 do
    for j := 1 to lim2 do
      if ech[i, j].visite then inc(total);
  tout_a_ete_visite := (total = (lim1 * lim2 div 2));
end;

La procédure qui simule le parcours du fou est bien entendu récursive. Elle a trois paramètres :
- x1 et y1 sont les coordonnées du fou au coup précédent
- coup : numéro du coup, utilisé pour mémoriser les déplacements du fou

Nous avons décidé d'arrêter l'algorithme après le premier parcours trouvé, mais rien ne vous empêche de supprimer le test sur la variable fini, pour laisser le programme chercher toutes les solutions.

Voyons le coeur du programme : on a quatre directions possibles, représentées par les tableaux dx et dy. A partir de chaque case, on essaye d'aller dans chacune des quatre directions, ce qui nous amène à l'utilisation d'une boucle for i:=1 to 4 do. On calcule ensuite les coordonnées de la prochaîne case, en utilisant les tableaux dx et dy : new_x:=x1+dx[i]; new_y:=y1+dy[i]; et on s'assure que cette case est bien sur l'échiquier. Suivant la valeur de i, on se trouve ou bien dans le sens A, ou bien dans le sens B. Supposons que nous sommes dans le sens A. Comme on va se déplacer dans une autre case, il faut sauvegarder les paramètres de la case en cours, marquer son sens A, marquer le sens A de la case où on va sauter (de cette façon, si on y repasse au bout de n sauts, on ne pourra pas utiliser le sens A), faire un appel récursif avec les coordonnées de la nouvelle case, et quand on sort de la récursion, restaurer les valeurs telles qu'elles étaient avant le saut. Il ne faut évidemment pas oublier de positionner à true le booléen visite de chaque case qui a été visitée au moins une fois.

Le même ensemble d'instructions s'applique pour le sens B; nous obtenons le programme suivant :

 
Sélectionnez
procedure chemin(x1, y1, coup: integer);
const dx: array[1..4] of integer = (1, 1, -1, -1); //--- 1 et 3 : sens 1
  dy: array[1..4] of integer = (1, -1, -1, 1); //--- 2 et 4 : sens 2
var i, new_x, new_y: integer;
  old_s11, old_s12, old_s21, old_s22, visit: boolean;
begin
  coups[coup] := y1 * 10 + x1;
  if tout_a_ete_visite then
  begin
    max_coups := coup;
    fini := true;
  end
  else
  begin
    for i := 1 to 4 do
    begin
      new_x := x1 + dx[i];
      new_y := y1 + dy[i];
      if not fini then
        if (new_x >= 1) and (new_x <= lim1) and
          (new_y >= 1) and (new_y <= lim2) then
          if (i mod 2) = 1 then
          begin
            if not ech[new_x, new_y].sensA then
            begin
                    //--- sauvegarde anciennes valeurs
              old_s11 := ech[new_x, new_y].sensA;
              old_s12 := ech[x1, y1].sensA; //--- sauvegarde sensA
              visit := ech[new_x, new_y].visite;
                    //--- modifications
              ech[new_x, new_y].sensA := true;
              ech[new_x, new_y].visite := true;
              ech[x1, y1].sensA := true; //--- modif sensA
                    //--- appel récursif
              chemin(new_x, new_y, coup + 1);
                    //--- restauration anciennes valeurs
              ech[x1, y1].sensA := old_s12; //--- restaure sensA
              ech[new_x, new_y].sensA := old_s11;
              ech[new_x, new_y].visite := visit;
            end;
          end
          else
          begin
            if not ech[new_x, new_y].sensB then
            begin
                    //--- sauvegarde anciennes valeurs
              old_s21 := ech[new_x, new_y].sensB;
              old_s22 := ech[x1, y1].sensB;
              visit := ech[new_x, new_y].visite;
                    //--- modifications
              ech[new_x, new_y].sensB := true;
              ech[new_x, new_y].visite := true;
              ech[x1, y1].sensB := true;
                    //--- appel récursif
              chemin(new_x, new_y, coup + 1);
                    //--- restauration anciennes valeurs
              ech[x1, y1].sensB := old_s22;
              ech[new_x, new_y].sensB := old_s21;
              ech[new_x, new_y].visite := visit;
            end;
          end;
    end;
  end;
end;

Code des exemples : chap_III_1.zip Miroir 1 , chap_III_1.zip Miroir 2

III-B. Le problème du cavalier

Un autre problème bien connu est le parcours du cavalier : comment faut-il faire jouer un cavalier sur un echiquier de façon à ce qu'il passe par toutes les cases de l'échiquier ?

On distingue 2 types de parcours pour le cavalier :
  1. les parcours constituant un cycle fermé (c'est à dire que le cavalier, après avoir parcouru toutes les cases de l'échiquier se retrouve à la même position qu'au départ)
  2. les parcours constituant un cycle ouvert (le cavalier part d'une case quelconque et après avoir parcouru les 63 cases restantes il se retrouve sur une autre position que celle de départ.

Le problème du cavalier, par rapport à celui du fou ou des reines, est qu'il demande un temps considérable pour être résolu, cela à cause du grand nombre de combinaisons possibles.

Nous allons voir deux manières de résoudre ce problème.

Première solution

On considère l'échiquier comme un tableau en deux dimensions, représenté par la variable suivante : t : array[1..8,1..8] of byte.

Pour représenter les 8 directions, on s'aide de deux tableaux "t_x" et "t_y".

Quand le cavalier a sauté sur une case, alors la case est initialisée à 1, sinon à 0.

Un cavalier peut sauter dans 8 directions, mais le saut n'est pas toujours possible, notamment si le cavalier se trouve sur les bords de l'échiquier.

Pour chaque position du cavalier, on essaie les 8 directions; pour chaque direction possible, on met la case à 1 (simulation du saut), on sauvegarde la position dans un tableau et on fait un appel récursif; ensuite, une fois revenu, il faut annuler le coup, donc on remet la case à 0.

Voici le programme :

 
Sélectionnez
const t_x: array[1..8] of integer = (1, 2, 2, 1, -1, -2, -2, -1);
  t_y: array[1..8] of integer = (-2, -1, 1, 2, 2, 1, -1, -2);
 
var t: array[1..8, 1..8] of byte; //--- l'échiquier
  p: array[1..65] of integer; //--- mémorise les sauts consécutifs
  s: string; //--- variable auxiliaire d'affichage
 
procedure remplir;
begin
  fillchar(t, sizeof(t), 0);
end;
 
function on_peut_jouer(y, x, nr: byte): boolean;
begin
  on_peut_jouer := false;
  inc(x, t_x[nr]); inc(y, t_y[nr]);
  if (x in [1..8]) and (y in [1..8]) then //--- si le cavalier est dans l'échiquier
    on_peut_jouer := t[y, x] = 0; //--- et si la case n'est pas occupée
end;
 
procedure récursive(y, x, cpt: byte);
var a: byte;
begin
  if cpt = 64 then
  begin
    s := '';
    for a := 1 to 64 do s := s + inttostr(p[a]) + ';';
    inc(nb);
    form1.edit1.text := 'solution numéro : ' + inttostr(nb) + ' : ' + s;
  end
  else
    for a := 1 to 8 do
      if on_peut_jouer(y, x, a) then
      begin
        t[y + t_y[a], x + t_x[a]] := 1;
        p[cpt] := x * 10 + y;
        récursive(y + t_y[a], x + t_x[a], cpt + 1);
        form1.edit2.text := inttostr(y + t_y[a]);
        t[y + t_y[a], x + t_x[a]] := 0;
      end;
end;
 
procedure debut;
var ligne, colonne: byte;
begin
  remplir;
  ligne := 1;
  colonne := 1;
  t[ligne, colonne] := 1;
  récursive(ligne, colonne, 1);
  t[ligne, colonne] := 0;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  debut;
end;

Le problème de cette solution est qu'elle est extrêmement lente : le cavalier ne parcourt que 250.000 cases par minute.

Deuxième solution

Voici maintenant une deuxième solution beaucoup plus efficace :

on ne considère plus le parcours de l'échiquier comme un ensemble de cases devant être initialisées à 1 quand le cheval est passé dessus (et remise à 0 quand le cheval revient d'une descente récursive) mais comme un ensemble de liens; on numérote les cases de 1 à 64. Ainsi quand le cavalier saute de la case 1 à la case 11, on initialise le lien "1->11" avec la valeur 1, ensuite on initialise tous les liens arrivant en 11 avec la valeur 1 (ce sont "5->11","17->11","21->11","26->11","28->11"); ainsi, quand l'ordinateur arrivera sur l'une de ces cases, il ne prendra aucun de ces chemins. Le fait de couper à chaque mouvement les sauts possibles pour une case donnée fait que le nombre de possibilités est réduit (malgré cela, il est encore très grand) et le programme trouve des solutions beaucoup plus rapidement. A titre indicatif, la première solution est trouvée en quatre minutes sur un K6-350, au bout de 17 millions de sauts du cavalier. Dans cette version du programme, le cavalier parcourt 4,4 millions de cases par minute. Le gain de temps est énorme. Nous avons laissé tourner le PC pendant deux jours (ensuite nous l'avons arrêté); il a exploré 12 milliards de coups et a trouvé environ 9000 solutions.

Voici une représentation de l'échiquier utilisé dans cette version:

 
Sélectionnez
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

Si on saute de 1 en 11 alors les liens "05->11, 17->11, 21->11,26->11, 28->11" sont coupés; il faut les mémoriser avant le saut, pour les restaurer après, pendant la remontée des niveaux récursifs

Les autres structures de données nécessaires sont le tableau "nb_sauts", qui indique le nombre de sauts possibles pour chaque case de l'échiquier :

 
Sélectionnez
nb_sauts: array[1..64] of integer =
(2, 3, 4, 4, 4, 4, 3, 2,
  3, 4, 6, 6, 6, 6, 4, 3,
  4, 6, 8, 8, 8, 8, 6, 4,
  4, 6, 8, 8, 8, 8, 6, 4,
  4, 6, 8, 8, 8, 8, 6, 4,
  4, 6, 8, 8, 8, 8, 6, 4,
  3, 4, 6, 6, 6, 6, 4, 3,
  2, 3, 4, 4, 4, 4, 3, 2);
 
pos_saut: array[1..64] of integer = // pour savoir à quelle position on doit
(1, 3, 6, 10, 14, 18, 22, 25, // chercher la case suivante lors d'un
  27, 30, 34, 40, 46, 52, 58, 62, // saut;
  65, 69, 75, 83, 91, 99, 107, 113, // on recherche la case suivante dans le
  117, 121, 127, 135, 143, 151, 159, 165, // tableau "liens"
  169, 173, 179, 187, 195, 203, 211, 217,
  221, 225, 231, 239, 247, 255, 263, 269,
  273, 276, 280, 286, 292, 298, 304, 308,
  311, 313, 316, 320, 324, 328, 332, 335);
 
liens: array[1..336] of integer =
(11, 18, //----- liens "1->11", "1->18"
  12, 17, 19, //----- liens "2->12", "2->17", "2->19"
  9, 13, 18, 20,
  10, 14, 19, 21,
  ...

On a un total de 336 sauts pour 64 cases, soit une moyenne de 5,25 sauts par case.

Et comme on a 64 cases à parcourir, alors le nombre total de possibilités est de 5,25 élevé à la puissance 64, soit 1,23*1046.

On utilise aussi des tableaux auxiliaires, comme "occupe" qui est un tableau de 336 booléens indiquant si un lien a déjà été visité ou pas. Pour chaque lien occupé (1->11) on occupe les liens allant vers 11. Mais une fois remonté, on les restaure; on a donc besoin de tableaux mémorisant les liens qu'on va occuper à chaque saut. Cette mémorisation s'effectue de la façon suivante :

 
Sélectionnez
por := 0;
  for j := 1 to 336 do // on occupe les liens
    if liens[j] = new_x then
    begin
      inc(por);
      po[por] := j;
      oc[por] := occupe[j];
      occupe[j] := true;
    end;

et la restauration des liens après le remontée récursive s'effectue de la manière suivante :

 
Sélectionnez
for j := 1 to por do occupe[po[j]] := oc[j];
 
 
procedure TForm1.Button4Click(Sender: TObject);
var num_saut, posit: integer;
 
  procedure remplir1;
  begin
    fillchar(occupe, sizeof(occupe), #0);
  end;
 
  procedure sauter(x, numero_saut: integer);
  var po: array[1..8] of integer;
    oc: array[1..8] of boolean;
    i, ii, j, k, m, por, new_x, c: integer;
    s1: string;
  begin
    inc(num_saut);
    if numero_saut > 63 then
    begin
      memo1.lines.clear;
      memo1.lines.add('saut=' + inttostr(num_saut));
      memo1.lines.add(soluce);
      memo1.refresh;
      exit;
    end;
    for i := 1 to nb_sauts[x] do
      if not occupe[pos_saut[x] + i - 1] then
      begin
        c := pos_saut[x] + i - 1;
        occupe[c] := true; // si x=1, "occupe[1]:=true" indique : lien "1->11" occupé
        new_x := liens[c]; // new_x:=11,18
          //--------- on occupe les liens
        por := 0;
        for j := 1 to 336 do
          if liens[j] = new_x then
          begin
            inc(por);
            po[por] := j;
            oc[por] := occupe[j];
            occupe[j] := true;
          end;
          //--------- appel récursif
        s1 := inttostr(new_x) + ';';
        soluce := soluce + s1;
        sauter(new_x, numero_saut + 1);
        delete(soluce, length(soluce) - length(s1) + 1, length(s1));
          //--------- restauration des liens occupées
        for j := 1 to por do occupe[po[j]] := oc[j];
        occupe[c] := false;
      end;
  end;
begin // chercher solution
  remplir1;
  soluce := ''; num_saut := 1;
  occupe[2] := true; // on interdit le saut "1->18" car symétrie avec "1->11"
  posit := 1;
  sauter(posit, 1);
end;

Code des exemples : chap_III_2.zip Miroir 1 , chap_III_2.zip Miroir 2

III-C. 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 :

 
Sélectionnez
+--------+  X représente une reine.
&#166;        &#166;
&#166;444X0000&#166;  Etant donné qu'on pose les 8 reines en descendant sur
&#166;  321   &#166;  l'échiquier, cela n'a pas de sens de compléter les 3
&#166; 3 2 1  &#166;  directions vers le haut, car on vient d'en haut et l'échiquier
&#166;3  2  1 &#166;  a déjà été complété par un coup précédent.
+--------+
 
Sélectionnez
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.

 
Sélectionnez
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.

 
Sélectionnez
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:

 
Sélectionnez
ligne 3, colonne 1  ---> première diagonale, gauche,haut
ligne 3, colonne 3  +
ligne 2, colonne 4  &#166;--> 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 :

 
Sélectionnez
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 :

 
Sélectionnez
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;

Code des exemples : chap_III_3.zip Miroir 1 , chap_III_3.zip Miroir 2


précédentsommairesuivant

Copyright © 2005 Axel CHAMBILY et Pétrut CONSTANTINE. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.