Cours sur la récursivité

De son vivant, Einstein a posé un petit problème de logique, destiné à tout le monde. Le problème n'est pas compliqué en soi, mais il demande un peu de réflexion et une très bonne organisation.

On a cinq maisons alignées de couleurs différentes.
Dans chaque maison vit une personne de nationalité différente.
Chaque personne boit une boisson différente.
Chaque personne fume un type de cigarette différent.
Chaque personne élève un animal différent.

Il faut trouver qui élève les poissons.

• L'anglais vit dans la maison rouge
• Le suédois élève des chiens
• Le danois boit du thé.
• La maison verte est juste à gauche de la maison blanche.
• Le propriétaire de la maison verte boit du café.
• Le fumeur de Pall Mall élève des oiseaux.
• Le propriétaire de la maison jaune fume des Dunhills.
• L'homme qui vit dans la maison du centre boit du lait.
• Le norvégien vit dans la première maison.
• L'homme qui fume des Blends vit à côté de celui qui élève des chats.
• L'homme qui élève des chevaux vit à côté du fumeur de Dunhills.
• L'homme qui fume des Blue Masters boit de la bière.
• L'allemand fume des Prince.
• Le norvégien vit à côté de la maison bleue.
• L'homme qui fume des Blends a un voisin qui boit de l'eau.

Nous allons par commencer par définir les types de données utilisés :

type_homme = set of (anglais, suedois, danois, norvegien, allemand);
type_boisson = set of (the, cafe, eau, lait, biere);
type_cigarette = set of (pall_mall, dunhills, blends, blue_masters, prince);
type_animal = set of (chiens, oiseaux, chats, chevaux, poissons);
type_couleur = set of (rouge, verte, blanche, jaune, bleue);
maison = record
  couleur: type_couleur;
  homme: type_homme;
  boisson: type_boisson;
  cigarette: type_cigarette;
  animal: type_animal;
end;

Pour résoudre ce problème, nous allons utiliser le programme récursif de "permutations" ou "anagrammes", que nous avons déjà étudié précédemment. Il nous donne toutes les façons possibles de placer les 5 maisons. Les variables qu'on utilisera sont donc un tableau de 5 maisons et une liste contenant les anagrammes.

maisons: array[1..5] of maison;
permutations: tStringList;

Nous allons maintenant traduire en langage informatique les contraintes du problème; on utilise un tableau de 15 booléens, car on a 15 contraintes:

1) L'anglais vit dans la maison rouge

for i:=1 to 5 do
    if (maisons[i].homme=[anglais]) and (maisons[i].couleur=[rouge ]) then ok[1]:=true;

2) Le suédois élève des chiens

for i:=1 to 5 do
    if (maisons[i].homme=[suedois]) and (maisons[i].animal =[chiens]) then 
       ok[2]:=true;

3) Le danois boit du thé.

for i:=1 to 5 do
    if (maisons[i].homme=[danois ]) and (maisons[i].boisson=[the   ]) then   
       ok[3]:=true;

4) La maison verte est juste à gauche de la maison blanche.

Pour une maison donnée "i", le "juste à gauche" se traduit par la maison "i-1".

for i:=1 to 5 do
    if (i>1) and (maisons[i].couleur=[blanche]) and (maisons[i-1].couleur=[verte]) 
       then ok[4]:=true;

5) Le propriétaire de la maison verte boit du café.

for i:=1 to 5 do
    if (maisons[i].couleur=[verte]) and (maisons[i].boisson=[cafe]) then 
       ok[5]:=true;

6) Le fumeur de Pall Mall élève des oiseaux.

for i:=1 to 5 do
    if (maisons[i].cigarette=[pall_mall]) and (maisons[i].animal=[oiseaux]) then 
       ok[6]:=true;

7) Le propriétaire de la maison jaune fume des Dunhills.

for i:=1 to 5 do
    if (maisons[i].cigarette=[dunhills ]) and (maisons[i].couleur=[jaune ]) then 
       ok[7]:=true;

8) L'homme qui vit dans la maison du centre boit du lait.

Comme on a 5 maisons, celle du centre est la numéro 3.

for i:=1 to 5 do
    if (maisons[3].boisson=[lait]) then ok[8]:=true;

9) Le norvégien vit dans la première maison.

for i:=1 to 5 do
    if (maisons[1].homme=[norvegien]) then ok[9]:=true;

10) L'homme qui fume des Blends vit à côté de celui qui élève des chats.

Pour une maison donnée "i", "à côté" signifie "i-1" ou "i+1".
Il faut donc faire attention aux bords :

    for i:=1 to 5 do
        if (maisons[i].animal=[chats]) then
        begin
           if (i<5) and (maisons[i+1].cigarette=[blends]) then ok[10]:=true;
           if (i>1) and (maisons[i-1].cigarette=[blends]) then ok[10]:=true;
        end;

11) L'homme qui élève des chevaux vit à côté du fumeur de Dunhills.

    for i:=1 to 5 do
        if (maisons[i].cigarette=[dunhills]) then
        begin
           if (i<5) and (maisons[i+1].animal=[chevaux]) then ok[11]:=true;
           if (i>1) and (maisons[i-1].animal=[chevaux]) then ok[11]:=true;
        end;

12) L'homme qui fume des Blue Masters boit de la bière.

for i:=1 to 5 do
    if (maisons[i].cigarette=[blue_masters]) and (maisons[i].boisson=[biere]) then 
       ok[12]:=true;

13) L'allemand fume des Prince.

for i:=1 to 5 do
    if (maisons[i].homme=[allemand]) and (maisons[i].cigarette=[prince]) then 
       ok[13]:=true;

14) Le norvégien vit à côté de la maison bleue.

    for i:=1 to 5 do
        if (maisons[i].couleur=[bleue]) then
        begin
           if (i<5) and (maisons[i+1].homme=[norvegien]) then ok[14]:=true;
           if (i>1) and (maisons[i-1].homme=[norvegien]) then ok[14]:=true;
        end;

15) L'homme qui fume des Blends a un voisin qui boit de l'eau.

    for i:=1 to 5 do
        if (maisons[i].cigarette=[blends]) then
        begin
           if (i<5) and (maisons[i+1].boisson=[eau]) then ok[15]:=true;
           if (i>1) and (maisons[i-1].boisson=[eau]) then ok[15]:=true;
        end;

Et maintenant voici la procédure de recherche de la solution; avant d'arriver ici, nous avons stocké dans une liste "permutations" les 120 façons différentes de placer les 5 maisons.

Le principe est le suivant :
on choisit une par une les façons de placer les maisons (120 possibilités).
pour chaque façon trouvée :
- on choisit une par une les façons de placer les hommes (120 possibilités)
- pour chaque façon trouvée :
-- on choisit une par une les façons de placer les boissons (120 possibilités)
-- pour chaque façon trouvée :
--- on choisit une par une les façons de placer les cigarettes (120 possibilités)
--- pour chaque façon trouvée :
---- on choisit une par une les façons de placer les animaux (120 possibilités)
---- on teste si toutes les contraintes sont vérifiées.

Le problème de cet algorithme, tel qu'il est décrit ci-dessus, est que le temps requis est énorme.

En effet, il revient à tester 120^5 possibilités, soit environ 25 milliards. Il faut donc le modifier et rajouter les tests après chaque façon de placer les maisons, hommes, ...

Nous obtenons donc le programme suivant :

on choisit une par une les façons de placer les maisons (120 possibilités).
pour chaque façon trouvée :
- si conditions(4) alors
--- on choisit une par une les façons de placer les hommes (120 possibilités)
--- pour chaque façon trouvée :
----- si condition( 1) alors
----- si condition( 9) alors
----- si condition(14) alors
------- on choisit une par une les façons de placer les boissons (120 possibilités)
------- pour chaque façon trouvée :
--------- si condition(3) alors
--------- si condition(5) alors
--------- si condition(8) alors
----------- on choisit une par une les façons de placer les cigarettes (120 possibilités)
----------- pour chaque façon trouvée :
------------- si conditions( 7) then
------------- si conditions(12) then
------------- si conditions(13) then
------------- si conditions(15) then
--------------- on choisit une par une les façons de placer les animaux (120 possibilités)
----------------- si conditions( 2) alors
----------------- si conditions( 6) alors
----------------- si conditions(10) alors
----------------- si conditions(11) alors
------------------- affiche_solution;

La solution est donnée instantanément : c'est l'allemand.

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

Quatre musiciens sont à gauche d'un pont; il fait nuit et il y a une seule torche; deux personnes au maximum peuvent traverser à la fois, et celui ou ceux qui traversent doivent avoir la torche pour éclairer le pont, sinon ils tombent dans l'eau. Le premier met 10 minutes pour traverser le pont, le deuxième 5 minutes, le troisième 2 minutes et le quatrième une minute.

Si le premier traverse en même temps que le deuxième, le temps de leur traversée sera de 10 minutes.

Ils doivent traverser le pont en 17 minutes.

Introduction

Nous allons réaliser le programme qui trouve les solutions de ce problème.

1. les musiciens qui sont à gauche du pont
2. les musiciens qui sont à droite du pont
3. le temps de traversée pour chacun
4. le temps total de traversée
5. l'endroit où se trouve la torche.

1. gauche : array[1..4] of boolean;
   Si le premier musicien est à gauche du pont alors gauche[1]=true, sinon false. En même temps que gauche[1]=true, on a droite[1]=false, car le musicien ne peut pas se trouver en deux endroits différents au même moment
2. droite : array[1..4] of boolean;
   Si le premier musicien est à droite du pont alors droite[1]=true, sinon false.
3. const temps : array[1..4] of integer = (10,5,2,1); // minutes nécessaires
4. var minutes : integer;
5. var torche_a_gauche : boolean;

Analyse du problème

Les musiciens traversent le pont au maximum deux à la fois.

S'ils sont deux, les possibilités sont :
1,2; 1,3; 1,4; 2,3; 2,4; 3,4

Cela se traduit par deux boucles imbriquées :

for i:=1 to 4 do  
for j:=i+1 to 4 do

Si à un instant donné on a la torche à gauche et qu'on veut traverser le pont, alors on considère que la torche va passer à droite, donc on écrit tout simplement :

torche_a_gauche:=false;

La traversée d'un musicien de gauche à droite se traduit par :

gauche[i]:=false; 
droite[i]:=true;   //--- "i" étant le numéro du musicien

Ce programme étant récursif (c'est à dire qu'il fait des essais de traversée successifs de la gauche vers la droite, de la droite vers la gauche et ainsi de suite), il faut mémoriser la position en cours avant chaque traversée (de façon à la restaurer si la traversée faite débouche plus tard sur un échec (temps total supérieur à 17 minutes)).

On note le sens de traversée par un entier égal à "1" ou "-1", ce qui facilite l'appel récursif avec un appel "chercher(-sens)"; au début sens=1, ensuite dans le parcours de l'arbre, suivant le niveau de profondeur, il sera égal à 1 ou -1.

On va ajouter un autre paramètre à la procédure "chercher" qui représente le chemin parcouru à un instant donné, au bout de n traversées.

Si, par exemple, on a deux musiciens ("i" et "j") qui traversent le pont, alors on les mets dans une chaîne de caractères "s1" :

s1:=inttostr(i)+','+inttostr(j);

On appelle ensuite récursivement la procédure "chercher", avec le chemin déjà parcouru noté "s" auquel on ajoute le sens de la traversée (indiqué par une flèche "<-" ou "->";

chercher(-sens,s+' <-'+s1+';');

On doit ensuite prendre en compte le dernier déplacement effectué par un ou deux musiciens. En effet, rien n'empêche le programme récursif de faire le mouvement suivant:

• déplacement vers la droite du musicien 1. La torche se trouve donc à droite.
• déplacement vers la gauche du musicien 1. La torche est maintenant à gauche.
• déplacement vers la droite du musicien 1. La torche est maintenant à droite.

Et ainsi de suite, ce qui nous entraîne dans une boucle infinie (en fait ici elle n'est pas infinie à cause du temps qui s'additionne pendant les traversées; mais cela nous fait perdre énormément de temps pendant la récursivité). On doit donc sauvegarder le dernier mouvement effectué et le comparer à celui que nous allons effectuer. Supposons que nous déplaçons le musicien "1" vers la droite; on mémorise dans une chaîne "1". Si ensuite on veut déplacer "1" vers la gauche, on compare avec la chaîne mémorisée, et on voit qu'elles sont égales, donc ce mouvement ne sera pas effectué.

Voici l'entête de la procédure "chercher" :

procedure chercher(sens : integer; s,last : string);

où "s" est le chemin parcouru et "last" le(s) musicien(s) ayant effectué la dernière traversée; pour deux musiciens on a :

s1:=inttostr(i)+','+inttostr(j);
if s1<>last then
   chercher(-sens,s+' <-'+s1+';',s1);

Une traversée complète d'un musicien "i" sera donc codée par :

droite[i] := true; gauche[i] := false; // traversée
torche_a_gauche := false; // on déplace la torche à droite
inc(minutes, temps[i]); // addition nombre de minutes
s1 := inttostr(i);
if s1 <> last then // si mouvement différent du mouvement précédent
  chercher(-sens, s + s1 + '->;', s1); // alors appel récursif
droite[i] := false; gauche[i] := true; // restauration positions initiales
torche_a_gauche := true; // on remet la torche à gauche
dec(minutes, temps[i]); // restauration nombre de minutes

La procédure récursive sera donc constituée de deux boucles imbriquées, et de nombreux tests pour déterminer quels sont les musiciens qui se déplacent, d'affectations de positions et de restauration de positions. Il est plus intéressant de commencer par déplacer les musiciens deux par deux au lieu de un par un (c'est à dire tout seuls).

Le point d'arrêt de la procédure est le suivant :

  if minutes = 17 then
  if droite[1] and droite[2] and droite[3] and droite[4] then
  begin
    fini := true;
    listbox1.items.add('trouvé !');
    listbox1.items.add(s);
    listbox1.refresh;
    exit;
  end
  else
    exit;

En exécutant cette procédure on constate que le programme affiche des solutions doubles. Cela est dû à l'opération suivante :

une fois qu'on a fait "3,4 ->" alors on teste :
"<- 1,2"
"<- 1,3" 3 part tout seul à gauche car droite[1]=false; (*)
"<- 1,4" 4 part tout seul à gauche car droite[1]=false;
"<- 2,3" 3 part tout seul à gauche car droite[1]=false; (*)

L'ordinateur prend donc deux fois le musicien "3" (pendant le parcours récursif) et le déplace à gauche, et comme ce mouvement mène à la solution, on a des doublons dans l'affichage.

Il faut donc mémoriser les solutions trouvées et comparer chaque nouvelle solution à celles déjà trouvées.

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