Le problème d'Einstein

 

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.

Indices :

1) L'anglais vit dans la maison rouge

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

3) Le danois boit du thé.

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

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

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

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

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

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

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

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

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

13) L'allemand fume des Prince.

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

15) 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 1205 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.

 

Télécharger le code source Delphi