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