5.11 Exemple de contrôle du flux
    interrompre une recursivité
    (Les 8 reines sur un echiquier)


    Plan du chapitre:

    1. Le programme pascal
     

    1.1 Un listing classique de récursivité
    1.2 Une sortie d’exécution


    2. L’interface en Delphi
     

      2.1 Interrompre la récursivité avec ProcessMessages
      2.2 Temporisation pendant l’attente



    Les8Reines
     

    1. Le programme pascal

    Nous utilisons un exemple très connu utilisant la récursivité en pascal : comment placer 8 reines sur un échiquier sans qu'elles soient en prise. Nous allons l’utiliser comme un autre exemple de contrôle du flux de l’exécution en Delphi.
     

    1.1 Un listing classique de récursivité

       

      Les8Reines\Reines8.pas
       
       

    Le programme ci-dessous fournit 92 solutions comme sur un échiquier à deux joueurs sans tenir compte des effets de symétrie.
       
    program echec;
    const Faux=false;
          Vrai=true;
    type
      echiquier=array[1..8,1..8] of boolean;
      diagonale_1=array[-7..7] of boolean;
      diagonale_2=array[2..16] of boolean;
      line=array[1..8] of boolean;
    var
      k:integer;
    procedure ecrire(Queen:echiquier);
    {écrit sur l’écran une représentation d’une solution :
    c’est à dire un placement des 8 reines sur l’échiquier}
    var
      i,j:integer;
    begin
     k:=k+1;
     writeln;
     writeln('Solution N° : ',k:3);
     writeln('-------------');
     writeln;
     for i:=1 to 8 do begin
      for j:=1 to 8 do
       if Queen[i,j]=Vrai then write('* ')
       else write('. ');
      writeln
     end
    end;{ecrire}
    procedure placer(var diag1:diagonale_1;var diag2:diagonale_2;
         var ligne:line;var reine:echiquier; var j:integer);
    {procedure récursive assurant le placement des reines}
    var
      i0,i:integer;
    begin
     if flag_exit then exit;
     if j=9 then ecrire(reine)
     else
     for i0:=1 to 8 do begin
      i:=i0;
      if(ligne[i]=Faux)and(diag1[i-j]=Faux)
      and(diag2[i+j]=Faux) then
      begin
       ligne[i]:=Vrai;
       diag1[i-j]:=Vrai;
       diag2[i+j]:=Vrai;
       reine[i,j]:=Vrai;
       j:=j+1;
       placer(diag1,diag2,ligne,reine,j);
       j:=j-1;
       ligne[i]:=Faux;
       diag1[i-j]:=Faux;
       diag2[i+j]:=Faux;
       reine[i,j]:=Faux;
      end
     end
    end;{placer}
    procedure Reines_8;
    {initialisations et lancement de la récursivité}
    var
     i,j:integer;
     diag1:diagonale_1;
     diag2:diagonale_2;
     ligne:line;
     reine:echiquier;
    begin
     for i:=1 to 8 do begin
      ligne[i]:=Faux;
      for j:=1 to 8 do begin
       diag1[i-j]:=Faux;
       diag2[i+j]:=Faux;
       reine[i,j]:=Faux;
      end
     end;
     j:=1;
     k:=0;
     placer(diag1,diag2,ligne,reine,j);
    end;{Reines_8}
    begin
      Reines_8
    end.
     
     

    1.2 Une sortie d’exécution

    Nous obtenons un listing séquentiel construit ligne par ligne avec des ‘.’ Pour représenter les cases vierges et des ‘*’ pour représenter la position d’une des huit reines.
     
     
       ..................

    Nous allons utiliser le RAD Delphi pour reprendre et réutiliser le maximum de ce programme pascal tout en améliorant l’interface. Le lecteur se rendra compte que la réutilisation pascal Delphi est dans ce cas très correcte. Comme nous l’avons déjà affirmé, il est possible dans un premier temps, de reprendre un grand nombre d’exemples développés en pascal pour les réinterfacer avec Delphi.
     
     
     

    2. L’interface en Delphi
     

    Nous voulons adopter la stratégie qui a été mise en place dans l’exemple d’interruption d’une itération. C’est-à-dire que nous voulons interrompre non plus la boucle, mais la profondeur de récursivité : à chaque appel récursif nous voulons mettre le logiciel en attente afin que l’utilisateur puisse conserver la vue de l’échiquier autant de temps qu’il le veut. Sur une vue donnée nous laissons à l’utilisateur la possibilité en sélectionnant une reine en place, de visualiser toutes lignes, colonnes et diagonales qui sont en " prise " par la position de cette reine.

    Nous allons utiliser une combinaison des deux outils cités précédemment :
     

    • le contrôle par ProcessMessages pour interrompre l’empilement récursif (boucle d’attente infinie passant la main aux messages systèmes), puis reprendre la récursivité.
    • la temporisation de la visualisation des cases en prise à l’aide d’un Timer (deuxième boucle d’attente infinie mais temporisée automatiquement).

     
     

    2.1 Interrompre la récursivité avec ProcessMessages

       
      Les8Reines\Les8Reines.v1.0


    Aspect de l’échiquier dans la fiche form1

       
       
    Les modifications ont lieu dans la procédure écrire et dans la procédure placer. La procédure ecrire affiche les 8 images des reines dans les cases appropriées.

    Nous introduisons dans la procédure écrire une boucle d’attente permettant de savoir si l’utilisateur a clické sur l’un des deux boutons " arrêt " ou  " voir solution suivante ". La technique employée est celle du chapitre précédent : utilisation de flags flag_suite et flag_exit qui sont levés chacun respectivement par le bouton " voir solution suivante " et le bouton " arrêt ".
     
    procedure ecrire(Queen:echiquier);
    var i,j:integer;
    begin
    flag_suite:=false;{flag de passage au suivant baissé}
     ......
     for i:=1 to 8 do
      for j:=1 to 8 do
       if Queen[i,j]=Vrai then
       {affiche l'icone reine8}
    repeat{boucle de messages}
      Application.processmessages
    until (flag_suite=true)or(flag_exit);
     ......
    {remplacer la reine par l'image initiale et restaurer l’échiquier}
     ......
    end;{ecrire}

    L’arrêt de la récursivité est provoqué par le flag_exit qui ferme la fiche " form1 " qui contient l’échiquier. Nous n’avons qu’une seule modification à apporter dans la procédure placer :
     
    procedure placer(var diag1:diagonale_1;
    var diag2:diagonale_2;var ligne:line;var reine:echiquier; var j:integer);
    var
      i0,i:integer;
    begin
    if flag_exit then form1.close
    else
    begin
       if j=9 then ecrire(reine)
       else
       ........( le reste est identique )

     

       
    2.2 Temporisation pendant l’attente

    Les8Reines\Les8Reines.v1.1

    Dans cette version nous introduisons une nouvelle fonctionnalité sur le contrôle du flux d’exécution. Pendant que le programme attend dans la " boucle infinie " de la procédure écrire, l’utilisateur peut vouloir visualiser pendant quelques instants les cases qui sont en prises pour une reine quelconque de l’échiquier. Cette action s’effectuera par un click sur une case occupée par une reine et nous lui colorions, en rouge par exemple, toutes les lignes en prise pour cette reine (une verticale, une horizontale et deux diagonales).

    Nous utilisons un timer nommé " timer1 " qui permettra l’affichage temporisé des quatre lignes occupées. Nous affichons les quatre lignes en rouge, puis nous bloquons de nouveau l’exécution séquentielle du programme par une autre boucle infinie de " temporisation " qui attend que le timer ait fini son décompte pour continuer ensuite par restaurer l’échiquier.
     
    repeat  {boucle de messages à windows}
      Application.processmessages
    until (timer1.enabled=false);

    Résultat de l’action de temporisation :


     

    Au bout de n millisecondes (valeur interval de timer1) l’interface reprend son aspect précédent.

    Tout ceci a lieu pendant que la boucle infinie d’attente générale continue à s’exécuter. Nous avons donc deux boucles qui ont été synchronisées entre elles grâce à la méthode ProcessMessages.

    Nous pouvons grâce à ce procédé déporter le flux d’exécution sur une autre zone d’action de l’interface puis revenir au déroulement antérieur. Ceci ressemble aux interruptions hiérarchisées dans un système d’exploitation.