Das Einsteinrätsel

1. Aufgabe

Ein Logikrätsel ist ein Rätsel, das nur durch logische Schlussfolgerungen lösbar ist. Das bekannteste Logikrätsel dürfte wohl das Einstein-Rätsel sein, auch unter dem Namen Einsteins Fischrätsel bekannt. Interessanterweise soll Albert Einstein zu seinem Rätsel die Formulierung geäußert haben, dass er nur 2% der Bevölkerung befähigt sieht, dieses Rätsel zu lösen – wenn gleich sich für diese Aussage kein historischer Beleg finden lässt. Interessanterweise existieren auch keinerlei Hinweise zur Autorenschaft des Rätsels selbst, von dem mehrere Versionen vorhanden sind. Die Ursprungsversion wurde im Life International Magazine am 17. Dezember 1962 abgedruckt. Erst am 25. März des Folgejahres erfolgte die Lösung an gleicher Stelle mit der Bekanntgabe der Namen mehrerer hundert Personen auf der ganzen Welt, die eine richtige Lösung gefunden haben.

Eine häufig anzutreffende Variante des Logikrätsels lautet folgendermaßen:

Voraussetzungen:

01. Es gibt fünf Häuser in je einer anderen Farbe. 
02. In jedem Haus wohnt eine Person einer anderen Nationalität. 
03. Jeder Hausbewohner bevorzugt ein bestimmtes Getränk. 
04. Jeder Hausbewohner bevorzugt eine bestimmte Zigarettenmarke. 
05. Jeder Hausbewohner hält ein bestimmtes Haustier.

Hinweise:

01. Der Brite lebt im roten Haus.
02. Der Schwede hält einen Hund.
03. Der Däne trinkt gerne Tee.
04. Das grüne Haus steht direkt links vom weißen Haus.
05. Der Besitzer des grünen Hauses trinkt gerne Kaffee.
06. Die Person, die Pall Mall raucht, hält einen Vogel.
07. Der Mann, der im mittleren Haus wohnt, trinkt gerne Milch.
08. Der Besitzer des gelben Hauses raucht Dunhill.
09. Der Norweger wohnt im ersten Haus.
10. Der Marlboro-Raucher wohnt neben dem, der eine Katze hält.
11. Der Mann, der ein Pferd hält, wohnt neben dem, der Dunhill raucht.
12. Der Winfield-Raucher trinkt gerne Bier.
13. Neben dem blauen Haus wohnt der Norweger.
14. Der Deutsche raucht Rothmanns.
15. Der Marlboro-Raucher hat einen Nachbarn, der Wasser trinkt.

Die Frage des Rätsels lautet: Wem gehört der Fisch ?

Sie können jetzt zum einen versuchen, durch logische Schlussfolgerungen das Rätsel zu lösen. Da wir als Informatiker immer dazu tendieren, dem „Computer das Denken zu überlassen“, wollen wir das Rätsel mit einem rechnergestützten Ansatz lösen. Dabei bieten sich im Prinzip zwei Vorgehensweisen an. Zum einen gibt es da den Brute-Force-Ansatz, zu Deutsch etwa „Lösen mit roher Gewalt“. In der Informatik stellt dies durchaus eine Lösungsmethode für unterschiedlichste Probleme dar, die in einer stupiden Berechnung aller Kombinationen mit anschließender Betrachtung der Voraussetzungen nach Lösungen sucht. Auf das Einsteinrätsel übertragen würde dies bedeuten: Wir haben es mit sechs Kategorien zu tun: Nationalität, Haustier, Getränk, Zigarette, Hausnummer und -farbe. In jeder Kategorie gibt es 5 zugeordnete Begriffe. Pro Kategorie gibt es folglich 5! = 120 Lösungsmöglichkeiten. Da diese voneinander unabhängig sind, gelangen wir bei sechs Kategorien insgesamt zu 1206 = 2985984000000 verschiedenen Lösungsmöglichkeiten. Diese Anzahl dürfte selbst bei einem schnellen Rechner nicht unmittelbar zu einem Resultat führen.

Deshalb trachten wir nach einem zweiten Ansatz. Diesem würde zunächst einmal ebenfalls ein Brute-Force-Vorgehen zu Grunde liegen, das aber die Berücksichtigung der Hinweise geschickter integriert, um so die immens große Anzahl aller Kombinationen soweit möglich zu reduzieren versucht.

Erstellen Sie ein C++-Programm, dass die (eindeutige) Lösung des Einstein-Rätsels ermittelt. Sie dürfen in einer ersten Implementierung durchaus einen Brute-Force-Ansatz verwenden, um die gesuchte Lösung zu eruieren. Modifizieren Sie anschließend Ihre Lösung Stück für Stück so, dass die vorhandenen Hinweise den Umfang an möglichen Lösungen reduzieren und das Programm zu einer kürzeren Rechenzeit gelangt.

2. Lösung

Quellcode: Siehe auch github.com/peterloos/Cpp_EinsteinsRiddle.git.

Wir starten mit einigen Vorbereitungen. Für die diversen Begriffe in den einzelnen Kategorien bieten sich Aufzählungstypen an:

enum Nationality { Norwegian, British, Swedish, Danish, German };
enum HouseColor { Red, Green, White, Yellow, Blue };
enum Cigarette { PallMall, Marlboro, DunHill, Winfield, Rothmans };
enum Drink { Tea, Coffee, Milk, Beer, Water };
enum Pet { Dog, Bird, Cat, Horse, Fish };

Auch der Entwurf einer Klasse House ist vergleichsweise überschaubar. Es genügt, einen Strukturtyp zu definieren, der ausschließlich die verschiedenen Eigenschaften eines Hauses zusammenbündelt (Listing 1). Zu Testzwecken überladen wir noch den Ausgabeoperator operator<<, um einzelne House-Objekte auf der Konsole ausgeben zu können (Listing 2):

01: struct House
02: {
03: private:
04:     Nationality m_Nationality;
05:     HouseColor  m_HouseColor;
06:     Cigarette   m_Cigarette;
07:     Drink       m_Drink;
08:     Pet         m_Pet;
09: 
10: public:
11:     // getter / setter
12:     void SetNationality (Nationality nationality) { m_Nationality = nationality; }
13:     Nationality GetNationality () const { return m_Nationality; }
14: 
15:     void SetHouseColor (HouseColor houseColor) { m_HouseColor = houseColor; }
16:     HouseColor GetHouseColor () const { return m_HouseColor; }
17: 
18:     void SetCigarette (Cigarette cigarette) { m_Cigarette = cigarette; }
19:     Cigarette GetCigarette () const { return m_Cigarette; }
20: 
21:     void SetDrink (Drink drink) { m_Drink = drink; }
22:     Drink GetDrink () const { return m_Drink; }
23: 
24:     void SetPet (Pet pet) { m_Pet = pet; }
25:     Pet GetPet () const { return m_Pet; }
26: 
27:     friend ostream& operator<< (ostream&, const House&);
28: };

Beispiel 1. Strukturtyp House: Schnittstelle.


01: #include <iostream>
02: using namespace std;
03: 
04: #include "House.h"
05: 
06: static char* g_Nationalities[] =
07:     { "Norwegian", "British", "Swedish", "Danish", "German" };
08: static char* g_HouseColors[] =
09:     { "Red", "Green", "White", "Yellow", "Blue" };
10: static char* g_Cigarettes[] =
11:     { "PallMall", "Marlboro", "DunHill", "Winfield", "Rothmans"  };
12: static char* g_Drinks[] =
13:     { "Tea", "Coffee", "Milk", "Beer", "Water" };
14: static char* g_Pets[] =
15:     { "Dog", "Bird", "Cat", "Horse", "Fish" };
16: 
17: ostream& operator<< (ostream& os, const House& house)
18: {
19:     os << "Nationality: " << g_Nationalities[house.GetNationality()] << endl;
20:     os << "    HouseColor: " << g_Nationalities[house.GetHouseColor()] << ", ";
21:     os << "Pet: " << g_Nationalities[house.GetPet()] << endl;
22:     os << "    Cigarette: " << g_Nationalities[house.GetCigarette()] << ", ";
23:     os << "Drink: " << g_Nationalities[house.GetDrink()] << endl;
24:     return os;
25: }

Beispiel 2. Strukturtyp House: Implementierung.


Die symbolische Ausgabe von Aufzählungskonstanten (enum-Konstanten) wird von der Sprache C++ nicht unterstützt. Zu diesem Zweck finden Sie in Listing 2, Zeilen 6 bis 15, mehrere Arrays mit Zeichenketten vor, um mit ihrer Hilfe ein House-Objekt ansprechend auf der Konsole darzustellen. Damit sind wir schon bei der Klasse EinsteinRiddleSolver angekommen. In ihren Instanzvariablen brauchen wir ein Feld vom Typ House, um darin fünf House-Strukturvariablen – sprich: fünf Objekte – abzulegen. Für das Auffüllen der House-Strukturvariablen mit unterschiedlichen Werten benötigen wir alle möglichen Anordnungen der jeweiligen Eigenschaftswerte. Hier spricht man in der Informatik von Permutationen. Für die drei Buchstaben a, b und c lauten diese beispielsweise

abc, acb, bac, bca, cab und cba.

Für das Lösen des Einsteinrätsels benötigen wir die Permutationen einer Menge von vier oder fünf Elementen. Da wir fünf Häuser haben, ist die Notwendigkeit der Permutationen einer 5-elementigen Menge offensichtlich. Auf die Permutationen einer Menge mit vier Elemente kommen wir später noch zu sprechen. In einem ersten Ansatz könnten wir darüber nachdenken, diese Permutationen zur Laufzeit des Programms zu berechnen. Da wir auf Grund des Brute-Force-Lösungsansatzes ohnehin schon mit der Laufzeit zu kämpfen haben werden, nehmen wir an dieser Stelle Einsparungen vor. Dies heißt in einfachen Worten, dass wir die Permutationen manuell im Quelltext ablegen. Zugegeben, eine nicht sehr elegante Vorgehensweise, aber dafür sehr effizient. Damit betrachten wir erste Ausschnitte der Klasse EinsteinRiddleSolver in Listing 3 und Listing 4:

01: class EinsteinRiddleSolver
02: {
03: private:
04:     static const int NumHouses = 5;
05:     static const int NumFourPermutations = 24;
06:     static const int NumFivePermutations = 120;
07: 
08: private:
09:     House m_houses[NumHouses];
10: 
11: private:
12:     // helper arrays with permutations
13:     static char m_four_permutations[NumFourPermutations][4];
14:     static int  m_five_permutations[NumFivePermutations][5];
15: 
16: public:
17:     // c'tor
18:     EinsteinRiddleSolver();
19: 
20:     // public interface
21:     void Solve();
22:     void PrintSolution();
23: 
24: private:
25:     // helper methods
26:     bool Tip_01_Verify();
27:     bool Tip_02_Verify();
28:     bool Tip_03_Verify();
29:     bool Tip_04_Verify();
30:     bool Tip_05_Verify();
31:     bool Tip_06_Verify();
32:     bool Tip_07_Verify();
33:     bool Tip_08_Verify();
34:     bool Tip_09_Verify();
35:     bool Tip_10_Verify();
36:     bool Tip_11_Verify();
37:     bool Tip_12_Verify();
38:     bool Tip_13_Verify();
39:     bool Tip_14_Verify();
40:     bool Tip_15_Verify();
41: };

Beispiel 3. Schnittstelle der Klasse EinsteinRiddleSolver: Ablage der Permutationen.


01: #include <iostream>
02: using namespace std;
03: 
04: #include "House.h"
05: #include "EinsteinRiddleSolver.h"
06: 
07: char EinsteinRiddleSolver::m_four_permutations[24][4]=
08: {
09:     { 'a','b','c','d' },
10:     { 'a','c','b','d' },
11:     { 'b','a','c','d' },
12:     .............
13:     { 'd','b','c','a' },
14:     { 'd','c','a','b' },
15:     { 'd','c','b','a' }
16: };
17: 
18: int EinsteinRiddleSolver::m_five_permutations[120][5] =
19: {
20:     { 0,1,2,3,4 },
21:     { 0,1,2,4,3 },
22:     { 0,1,3,2,4 },
23:     { 0,1,3,4,2 },
24:     { 0,1,4,2,3 },
25:     { 0,1,4,3,2 },
26:     { 0,2,1,3,4 },
27:     { 0,2,1,4,3 },
28:     { 0,2,3,1,4 },
29:     { 0,2,3,4,1 },
30:     .............
31:     { 4,2,1,0,3 },
32:     { 4,2,1,3,0 },
33:     { 4,2,3,0,1 },
34:     { 4,2,3,1,0 },
35:     { 4,3,0,1,2 },
36:     { 4,3,0,2,1 },
37:     { 4,3,1,0,2 },
38:     { 4,3,1,2,0 },
39:     { 4,3,2,0,1 },
40:     { 4,3,2,1,0 }
41: };
42: 
43: // c'tor
44: EinsteinRiddleSolver::EinsteinRiddleSolver()
45: {
46:     // Tipp 7: "Der Mann, der im mittleren Haus wohnt, trinkt gerne Milch"
47:     m_houses[2].SetDrink (Milk);
48: 
49:     // Tipp 9: "Der Norweger wohnt im ersten Haus"
50:     m_houses[0].SetNationality (Norwegian);
51: 
52:     // Tipp 13: "Neben dem blauen Haus wohnt der Norweger"
53:     m_houses[1].SetHouseColor (Blue);
54: }

Beispiel 4. Implementierung der Klasse EinsteinRiddleSolver: Ablage der Permutationen.


Ein Hinweis zu den Zeilen 13 und 14 von Listing 3. In C++ gibt es keine statische Initialisierung für Arrays, die im Instanzvariablenbereich eines Objekts liegen. Diese Lücke kann man auf zwei Weisen umgehen: Zum einen gibt es Konstruktoren, die zum Initialisieren beliebiger Array-Elemente herangezogen werden können. Da die Arrays im vorliegenden Fall unveränderbare Werte enthalten (Permutationen), kann man sie auch statisch anlegen – als Klassenvariable. Klassenvariablen wiederum lassen sich nicht in einem Konstruktor initialisieren, da sie sonst bei jeder Erzeugung eines Objekts wieder zurückgesetzt würden. Stattdessen werden diese wie eine globale Variable definiert, der der Klassenname vorangestellt wird. Damit lassen sich Klassenvariablen wie globale Variablen initialisieren, und wir können wieder eine Initialisierungsliste ins Spiel bringen, siehe die Zeilen 9 bis 40 von Listing 4.

Damit kommen wir zum Rätsel selbst. Drei Hinweise des Einsteinrätsels können bei unserem Vorgehen trivial berücksichtigt werden. Das machen wir uns natürlich zu eigen, in den Zeilen 47, 50 und 53 von Listing 4 werden die Hinweise 7, 9 und 13 direkt umgesetzt.

Möglicherweise fällt Ihnen eine Unstimmigkeit in Listing 4 auf. Für die Permutationen der Hausnummern 1 bis 5 verwenden wir die Zahlen 0 bis 4 (um die Werte direkt als Indizes für das Feld houses benutzen können), siehe die Zeilen 20 bis 40 (ausschnittsweise). Die Vierer-Permutationen hingegen sind mit Buchstaben niedergeschrieben (Zeilen 9 bis 15, ausschnittsweise), warum? Wir haben hier das kleine Problem zu Lösen, das beispielsweise im Falle des Getränks die Indizes 0, 1, 3 und 4 zu permutieren sind. Der Index 2 ist bereits festgelegt („Der Mann, der im mittleren Haus wohnt, trinkt gerne Milch“). Permutieren wir wiederum die Farben der Häuser, so benötigen wir unterschiedliche Anordnungen der Zahlen 0, 2, 3 und 4. Das zweite Haus ist Blau, seine Farbe wird niemals verändert. Aus diesem Grund beschreibt das Feld four_permutations die Vierer-Permutationen in einer allgemeineren Schreibweise. Wenn wir die Buchstaben in Zahlen umwandeln, müssen wir jeweils die Kategorie mit berücksichtigen und eine entsprechende Anpassung an die erforderlichen Indizes vornehmen.

Damit wären wir schon bei der Methode Solve in Listing 5 angekommen, die in einem Brute-Force-Ansatz (fast) alle Kombinationen der Eigenschaftswerte ermittelt und pro Kombination die 12 noch verbliebenen Hinweise überprüft:

001: void EinsteinRiddleSolver::Solve()
002: {
003:     // iterate cigarettes
004:     for (int i = 0; i < NumFivePermutations; i++)
005:     {
006:         int* perm1 = m_five_permutations[i];
007:         m_houses[perm1[0]].SetCigarette (PallMall);
008:         m_houses[perm1[1]].SetCigarette (Marlboro);
009:         m_houses[perm1[2]].SetCigarette (DunHill);
010:         m_houses[perm1[3]].SetCigarette (Winfield);
011:         m_houses[perm1[4]].SetCigarette (Rothmans);
012: 
013:         // iterate pets
014:         for (int j = 0; j < NumFivePermutations; j++)
015:         {
016:             int* perm2 = m_five_permutations[j];
017:             m_houses[perm2[0]].SetPet (Bird);
018:             m_houses[perm2[1]].SetPet (Cat);
019:             m_houses[perm2[2]].SetPet (Dog);
020:             m_houses[perm2[3]].SetPet (Fish);
021:             m_houses[perm2[4]].SetPet (Horse);
022: 
023:             // iterate drinks
024:             for (int k = 0; k < NumFourPermutations; k++)
025:             {
026:                 char* perm3 = m_four_permutations[k];
027: 
028:                 int k1 =
029:                     (perm3[0] == 'a') ? 0 : (perm3[0] == 'b') ? 1 :
030:                     (perm3[0] == 'c') ? 3 : 4;
031:                 int k2 =
032:                     (perm3[1] == 'a') ? 0 : (perm3[1] == 'b') ? 1 :
033:                     (perm3[1] == 'c') ? 3 : 4;
034:                 int k3 =
035:                     (perm3[2] == 'a') ? 0 : (perm3[2] == 'b') ? 1 :
036:                     (perm3[2] == 'c') ? 3 : 4;
037:                 int k4 =
038:                     (perm3[3] == 'a') ? 0 : (perm3[3] == 'b') ? 1 :
039:                     (perm3[3] == 'c') ? 3 : 4;
040: 
041:                 m_houses[k1].SetDrink (Beer);
042:                 m_houses[k2].SetDrink (Coffee);
043:                 m_houses[k3].SetDrink (Tea);
044:                 m_houses[k4].SetDrink (Water);
045: 
046:                 // iterate colors
047:                 for (int l = 0; l < NumFourPermutations; l++)
048:                 {
049:                     char* perm4 = m_four_permutations[l];
050: 
051:                     int l1 =
052:                         (perm4[0] == 'a') ? 0 : (perm4[0] == 'b') ? 2 :
053:                         (perm4[0] == 'c') ? 3 : 4;
054:                     int l2 =
055:                         (perm4[1] == 'a') ? 0 : (perm4[1] == 'b') ? 2 :
056:                         (perm4[1] == 'c') ? 3 : 4;
057:                     int l3 =
058:                         (perm4[2] == 'a') ? 0 : (perm4[2] == 'b') ? 2 :
059:                         (perm4[2] == 'c') ? 3 : 4;
060:                     int l4 =
061:                         (perm4[3] == 'a') ? 0 : (perm4[3] == 'b') ? 2 :
062:                         (perm4[3] == 'c') ? 3 : 4;
063: 
064:                     m_houses[l1].SetHouseColor (Green);
065:                     m_houses[l2].SetHouseColor (Red);
066:                     m_houses[l3].SetHouseColor (White);
067:                     m_houses[l4].SetHouseColor (Yellow);
068: 
069:                     // iterate nations
070:                     for (int m = 0; m < NumFourPermutations; m++)
071:                     {
072:                         char* perm5 = m_four_permutations[m];
073: 
074:                         int m1 =
075:                             (perm5[0] == 'a') ? 1 : (perm5[0] == 'b') ? 2 :
076:                             (perm5[0] == 'c') ? 3 : 4;
077:                         int m2 =
078:                             (perm5[1] == 'a') ? 1 : (perm5[1] == 'b') ? 2 :
079:                             (perm5[1] == 'c') ? 3 : 4;
080:                         int m3 =
081:                             (perm5[2] == 'a') ? 1 : (perm5[2] == 'b') ? 2 :
082:                             (perm5[2] == 'c') ? 3 : 4;
083:                         int m4 =
084:                             (perm5[3] == 'a') ? 1 : (perm5[3] == 'b') ? 2 :
085:                             (perm5[3] == 'c') ? 3 : 4;
086: 
087:                         m_houses[m1].SetNationality (British);
088:                         m_houses[m2].SetNationality (Swedish);
089:                         m_houses[m3].SetNationality (Danish);
090:                         m_houses[m4].SetNationality (German);
091: 
092:                         // Tipp 1: "Der Brite lebt im roten Haus"
093:                         if (!Tip_01_Verify())
094:                             continue;
095: 
096:                         // Tipp 2: "Der Schwede hält einen Hund"
097:                         if (!Tip_02_Verify())
098:                             continue;
099: 
100:                         // Tipp 3: "Der Däne trinkt gerne Tee"
101:                         if (!Tip_03_Verify())
102:                             continue;
103: 
104:                         // Tipp 4: "Das grüne Haus steht links vom weißen Haus"
105:                         if (!Tip_04_Verify())
106:                             continue;
107: 
108:                         // Tipp 5: "Der Besitzer des grünen Hauses trinkt Kaffee"
109:                         if (!Tip_05_Verify())
110:                             continue;
111: 
112:                         // Tipp 6: "Die Person, die Pall Mall raucht, hält einen Vogel"
113:                         if (!Tip_06_Verify())
114:                             continue;
115: 
116:                         // Tipp 7: "Der Mann, der im mittleren Haus wohnt, trinkt gerne Milch"
117:                         // See C'tor
118: 
119:                         // Tipp 8: "Der Besitzer des gelben Hauses raucht Dunhill"
120:                         if (!Tip_08_Verify())
121:                             continue;
122: 
123:                         // Tipp 9: "Der Norweger wohnt im ersten Haus"
124:                         // See C'tor
125: 
126:                         // Tipp 10: "Der Marlboro-Raucher wohnt neben dem, der eine Katze hält. "
127:                         if (!Tip_10_Verify())
128:                             continue;
129: 
130:                         // Tipp 11: "Der Mann, der ein Pferd hält, wohnt neben dem, der Dunhill raucht"
131:                         if (!Tip_11_Verify())
132:                             continue;
133: 
134:                         // Tipp 12: "Der Winfield-Raucher trinkt gerne Bier."
135:                         if (!Tip_12_Verify())
136:                             continue;
137: 
138:                         // Tipp 13: "Neben dem blauen Haus wohnt der Norweger"
139:                         // See C'tor
140: 
141:                         // Tipp 14: "Der Deutsche raucht Rothmanns"
142:                         if (!Tip_14_Verify())
143:                             continue;
144: 
145:                         // Tipp 15: "Der Marlboro-Raucher hat einen Nachbarn, der Wasser trinkt"
146:                         if (!Tip_15_Verify())
147:                             continue;
148: 
149:                         // reached a solution
150:                         PrintSolution();
151:                     }
152:                 }
153:             }
154:         }
155:     }
156: }
157: 
158: void EinsteinRiddleSolver::PrintSolution()
159: {
160:     for (int n = 0; n < 5; n++)
161:     {
162:         if (m_houses[n].GetPet() == Fish)
163:         {
164:             char* owner;
165:             switch (m_houses[n].GetNationality())
166:             {
167:             case Norwegian:
168:                 owner = "Norwegian";
169:                 break;
170:             case British:
171:                 owner = "British";
172:                 break;
173:             case Swedish:
174:                 owner = "Swedish";
175:                 break;
176:             case Danish:
177:                 owner = "Danish";
178:                 break;
179:             case German:
180:                 owner = "German";
181:                 break;
182:             default:
183:                 owner = "<Unknown>";
184:                 break;
185:             }
186:             cout << "The " << owner << " is the owner of the Fish." << endl;
187:         }
188:     }
189: }

Beispiel 5. Methode Solve_BruteForce aus der Klasse EinsteinRiddleSolver.


In den Zeilen 28 bis 39, 51 bis 62 und 74 bis 85 können Sie nachsehen, wie die Vierer-Permutationen entweder auf eine Permutation der Indizes 0, 1, 3, 4 oder 0, 2, 3, 4 oder 1, 2, 3, 4 umgesetzt wird. Die Verifizierungsmethoden der einzelnen Hinweise entnehmen Sie Listing 6:

001: // Tipp 1: "Der Brite lebt im roten Haus"
002: bool EinsteinRiddleSolver::Tip_01_Verify()
003: {
004:     bool tip = false;
005:     for (int i = 0; i < 5; i++)
006:     {
007:         if (m_houses[i].GetNationality() == British)
008:         {
009:             if (m_houses[i].GetHouseColor() == Red)
010:             {
011:                 tip = true;
012:             }
013:             break;
014:         }
015:     }
016:     return tip;
017: }
018: 
019: // Tipp 2: "Der Schwede hält einen Hund"
020: bool EinsteinRiddleSolver::Tip_02_Verify()
021: {
022:     bool tip = false;
023:     for (int i = 0; i < 5; i++)
024:     {
025:         if (m_houses[i].GetNationality() == Swedish)
026:         {
027:             if (m_houses[i].GetPet() == Dog)
028:             {
029:                 tip = true;
030:             } 
031:             break;
032:         }
033:     }
034:     return tip;
035: }
036: 
037: // Tipp 3: "Der Däne trinkt gerne Tee"
038: bool EinsteinRiddleSolver::Tip_03_Verify()
039: {
040:     bool tip = false;
041:     for (int i = 0; i < 5; i++)
042:     {
043:         if (m_houses[i].GetNationality() == Danish)
044:         {
045:             if (m_houses[i].GetDrink() == Tea)
046:             {
047:                 tip = true;
048:             }
049:             break;
050:         }
051:     }
052:     return tip;
053: }
054: 
055: // Tipp 4: "Das grüne Haus steht direkt links vom weißen Haus"
056: bool EinsteinRiddleSolver::Tip_04_Verify()
057: {
058:     if ((m_houses[2].GetHouseColor() == Green &&
059:             m_houses[3].GetHouseColor() == White) ||
060:         (m_houses[3].GetHouseColor() == Green &&
061:             m_houses[4].GetHouseColor() == White))
062:     {
063:         return true;
064:     }
065:     else
066:         return false;
067: }
068: 
069: // Tipp 5: "Der Besitzer des grünen Hauses trinkt gerne Kaffee"
070: bool EinsteinRiddleSolver::Tip_05_Verify()
071: {
072:     bool tip = false;
073:     for (int i = 0; i < 5; i++)
074:     {
075:         if (m_houses[i].GetHouseColor() == Green)
076:         {
077:             if (m_houses[i].GetDrink() == Coffee)
078:             {
079:                 tip = true;
080:             }
081:             break;
082:         }
083:     }
084:     return tip;
085: }
086: 
087: // Tipp 6: "Die Person, die Pall Mall raucht, hält einen Vogel"
088: bool EinsteinRiddleSolver::Tip_06_Verify()
089: {
090:     bool tip = false;
091:     for (int i = 0; i < 5; i++)
092:     {
093:         if (m_houses[i].GetCigarette() == PallMall)
094:         {
095:             if (m_houses[i].GetPet() == Bird)
096:             {
097:                 tip = true;
098:             }
099:             break;
100:         }
101:     }
102:     return tip;
103: }
104: 
105: // Tipp 7: "Der Mann, der im mittleren Haus wohnt, trinkt gerne Milch"
106: // See C'tor
107: 
108: // Tipp 8: "Der Besitzer des gelben Hauses raucht Dunhill"
109: bool EinsteinRiddleSolver::Tip_08_Verify()
110: {
111:     bool tip = false;
112:     for (int i = 0; i < 5; i++)
113:     {
114:         if (m_houses[i].GetHouseColor() == Yellow)
115:         {
116:             if (m_houses[i].GetCigarette() == DunHill)
117:             {
118:                 tip = true;
119:             }
120:             break;
121:         }
122:     }
123:     return tip;
124: }
125: 
126: // Tipp 9: "Der Norweger wohnt im ersten Haus"
127: // See C'tor
128: 
129: // Tipp 10: "Der Marlboro-Raucher wohnt neben dem, der eine Katze hält"
130: bool EinsteinRiddleSolver::Tip_10_Verify()
131: {
132:     bool tip = false;
133:     for (int i = 0; i < 5; i++)
134:     {
135:         if (m_houses[i].GetCigarette() == Marlboro)
136:         {
137:             if (i == 0)
138:             {
139:                 if (m_houses[1].GetPet() == Cat)
140:                     tip = true;
141:             }
142:             else if (i == 4)
143:             {
144:                 if (m_houses[3].GetPet() == Cat)
145:                     tip = true;
146:             }
147:             else if (m_houses[i - 1].GetPet() == Cat ||
148:                 m_houses[i + 1].GetPet() == Cat)
149:                 tip = true;
150: 
151:             break;
152:         }
153:     }
154: 
155:     return tip;
156: }
157: 
158: // Tipp 11: "Der Mann, der ein Pferd hält, wohnt neben dem, der Dunhill raucht"
159: bool EinsteinRiddleSolver::Tip_11_Verify()
160: {
161:     bool tip = false;
162:     for (int i = 0; i < 5; i++)
163:     {
164:         if (m_houses[i].GetPet() == Horse)
165:         {
166:             if (i == 0)
167:             {
168:                 if (m_houses[1].GetCigarette() == DunHill)
169:                     tip = true;
170:             }
171:             else if (i == 4)
172:             {
173:                 if (m_houses[3].GetCigarette() == DunHill)
174:                     tip = true;
175:             }
176:             else if (m_houses[i - 1].GetCigarette() == DunHill ||
177:                         m_houses[i + 1].GetCigarette() == DunHill)
178:                     tip = true;
179:             
180:             break;
181:         }
182:     }
183:     return tip;
184: }
185: 
186: // Tipp 12: "Der Winfield-Raucher trinkt gerne Bier"
187: bool EinsteinRiddleSolver::Tip_12_Verify()
188: {
189:     bool tip = false;
190:     for (int i = 0; i < 5; i++)
191:     {
192:         if (m_houses[i].GetCigarette() == Winfield)
193:         {
194:             if (m_houses[i].GetDrink() == Beer)
195:                 tip = true;
196: 
197:             break;
198:         }
199:     }
200:     return tip;
201: }
202: 
203: // Tipp 13: "Neben dem blauen Haus wohnt der Norweger"
204: // See C'tor
205: 
206: // Tipp 14: "Der Deutsche raucht Rothmanns"
207: bool EinsteinRiddleSolver::Tip_14_Verify()
208: {
209:     bool tip = false;
210:     for (int i = 0; i < 5; i++)
211:     {
212:         if (m_houses[i].GetNationality() == German)
213:         {
214:             if (m_houses[i].GetCigarette() == Rothmans)
215:                 tip = true;
216: 
217:             break;
218:         }
219:     }
220:     return tip;
221: }
222: 
223: // Tipp 15: "Der Marlboro-Raucher hat einen Nachbarn, der Wasser trinkt"
224: bool EinsteinRiddleSolver::Tip_15_Verify()
225: {
226:     bool tip = false;
227:     for (int i = 0; i < 5; i++)
228:     {
229:         if (m_houses[i].GetCigarette() == Marlboro)
230:         {
231:             if (i == 0)
232:             {
233:                 if (m_houses[1].GetDrink() == Water)
234:                     tip = true;
235:             }
236:             else if (i == 4)
237:             {
238:                 if (m_houses[3].GetDrink() == Water)
239:                     tip = true;
240:             }
241:             else if (m_houses[i - 1].GetDrink() == Water ||
242:                 m_houses[i + 1].GetDrink() == Water)
243:                     tip = true;
244: 
245:             break;
246:         }
247:     }
248:     return tip;
249: }

Beispiel 6. Verifizierungsmethoden der Klasse EinsteinRiddleSolver.


Die Laufzeit dieses Programms ist zwangsweise ernüchternd, auf meinem Rechner sind es ca. 30 Sekunden. Immerhin haben wir schon einmal die Lösung des Einstein-Rätsels gefunden:

The German is the owner of the Fish.
[30095 msecs]

Nun verbessern wir die Methode Solve aus Listing 5 an Hand folgender Überlegungen. Es gibt mehrere Hinweise, die wir nicht erst im Innersten der fünf for-Wiederholungsanweisungen testen müssen. Geht es beispielsweise nur um Zigaretten und Haustiere, können entsprechende Überprüfungen bereits innerhalb der äußersten beiden for-Schleifen ausgeführt werden. Ähnliches gilt auch für Zigaretten und Getränke oder auch für Hausfarben und Zigaretten. Sie werden überrascht sein, wie viel Zeit sich einsparen lässt, wenn wir die entsprechenden Abfragen nach außen ziehen. Das Redesign der Methode Solve entnehmen Sie Listing 7:

001: void EinsteinRiddleSolver::Solve()
002: {
003:     // iterate cigarettes
004:     for (int i = 0; i < NumFivePermutations; i++)
005:     {
006:         int* perm1 = m_five_permutations[i];
007:         m_houses[perm1[0]].SetCigarette (PallMall);
008:         m_houses[perm1[1]].SetCigarette (Marlboro);
009:         m_houses[perm1[2]].SetCigarette (DunHill);
010:         m_houses[perm1[3]].SetCigarette (Winfield);
011:         m_houses[perm1[4]].SetCigarette (Rothmans);
012: 
013:         // iterate pets
014:         for (int j = 0; j < NumFivePermutations; j++)
015:         {
016:             int* perm2 = m_five_permutations[j];
017:             m_houses[perm2[0]].SetPet (Bird);
018:             m_houses[perm2[1]].SetPet (Cat);
019:             m_houses[perm2[2]].SetPet (Dog);
020:             m_houses[perm2[3]].SetPet (Fish);
021:             m_houses[perm2[4]].SetPet (Horse);
022: 
023:             // Tipp 6: "Die Person, die Pall Mall raucht, hält einen Vogel"
024:             if (!Tip_06_Verify())
025:                 continue;
026: 
027:             // Tipp 10: "Der Marlboro-Raucher wohnt neben dem, der eine Katze hält. "
028:             if (!Tip_10_Verify())
029:                 continue;
030: 
031:             // Tipp 11: "Der Mann, der ein Pferd hält, wohnt neben dem, der Dunhill raucht"
032:             if (!Tip_11_Verify())
033:                 continue;
034: 
035:             // iterate drinks
036:             for (int k = 0; k < NumFourPermutations; k++)
037:             {
038:                 char* perm3 = m_four_permutations[k];
039: 
040:                 int k1 =
041:                     (perm3[0] == 'a') ? 0 : (perm3[0] == 'b') ? 1 :
042:                     (perm3[0] == 'c') ? 3 : 4;
043:                 int k2 =
044:                     (perm3[1] == 'a') ? 0 : (perm3[1] == 'b') ? 1 :
045:                     (perm3[1] == 'c') ? 3 : 4;
046:                 int k3 =
047:                     (perm3[2] == 'a') ? 0 : (perm3[2] == 'b') ? 1 :
048:                     (perm3[2] == 'c') ? 3 : 4;
049:                 int k4 =
050:                     (perm3[3] == 'a') ? 0 : (perm3[3] == 'b') ? 1 :
051:                     (perm3[3] == 'c') ? 3 : 4;
052: 
053:                 m_houses[k1].SetDrink (Beer);
054:                 m_houses[k2].SetDrink (Coffee);
055:                 m_houses[k3].SetDrink (Tea);
056:                 m_houses[k4].SetDrink (Water);
057: 
058:                 // Tipp 12: "Der Winfield-Raucher trinkt gerne Bier."
059:                 if (!Tip_12_Verify())
060:                     continue;
061: 
062:                 // Tipp 15: "Der Marlboro-Raucher hat einen Nachbarn, der Wasser trinkt"
063:                 if (!Tip_15_Verify())
064:                     continue;
065: 
066:                 // iterate colors
067:                 for (int l = 0; l < NumFourPermutations; l++)
068:                 {
069:                     char* perm4 = m_four_permutations[l];
070: 
071:                     int l1 =
072:                         (perm4[0] == 'a') ? 0 : (perm4[0] == 'b') ? 2 :
073:                         (perm4[0] == 'c') ? 3 : 4;
074:                     int l2 =
075:                         (perm4[1] == 'a') ? 0 : (perm4[1] == 'b') ? 2 :
076:                         (perm4[1] == 'c') ? 3 : 4;
077:                     int l3 =
078:                         (perm4[2] == 'a') ? 0 : (perm4[2] == 'b') ? 2 :
079:                         (perm4[2] == 'c') ? 3 : 4;
080:                     int l4 =
081:                         (perm4[3] == 'a') ? 0 : (perm4[3] == 'b') ? 2 :
082:                         (perm4[3] == 'c') ? 3 : 4;
083: 
084:                     m_houses[l1].SetHouseColor (Green);
085:                     m_houses[l2].SetHouseColor (Red);
086:                     m_houses[l3].SetHouseColor (White);
087:                     m_houses[l4].SetHouseColor (Yellow);
088: 
089:                     // Tipp 4: "Das grüne Haus steht links vom weißen Haus"
090:                     if (!Tip_04_Verify())
091:                         continue;
092: 
093:                     // Tipp 5: "Der Besitzer des grünen Hauses trinkt Kaffee"
094:                     if (!Tip_05_Verify())
095:                         continue;
096: 
097:                     // Tipp 8: "Der Besitzer des gelben Hauses raucht Dunhill"
098:                     if (!Tip_08_Verify())
099:                         continue;
100: 
101:                     // iterate nations
102:                     for (int m = 0; m < NumFourPermutations; m++)
103:                     {
104:                         char* perm5 = m_four_permutations[m];
105: 
106:                         int m1 =
107:                             (perm5[0] == 'a') ? 1 : (perm5[0] == 'b') ? 2 :
108:                             (perm5[0] == 'c') ? 3 : 4;
109:                         int m2 =
110:                             (perm5[1] == 'a') ? 1 : (perm5[1] == 'b') ? 2 :
111:                             (perm5[1] == 'c') ? 3 : 4;
112:                         int m3 =
113:                             (perm5[2] == 'a') ? 1 : (perm5[2] == 'b') ? 2 :
114:                             (perm5[2] == 'c') ? 3 : 4;
115:                         int m4 =
116:                             (perm5[3] == 'a') ? 1 : (perm5[3] == 'b') ? 2 :
117:                             (perm5[3] == 'c') ? 3 : 4;
118: 
119:                         m_houses[m1].SetNationality (British);
120:                         m_houses[m2].SetNationality (Swedish);
121:                         m_houses[m3].SetNationality (Danish);
122:                         m_houses[m4].SetNationality (German);
123: 
124:                         // Tipp 1: "Der Brite lebt im roten Haus"
125:                         if (!Tip_01_Verify())
126:                             continue;
127: 
128:                         // Tipp 2: "Der Schwede hält einen Hund"
129:                         if (!Tip_02_Verify())
130:                             continue;
131: 
132:                         // Tipp 3: "Der Däne trinkt gerne Tee"
133:                         if (!Tip_03_Verify())
134:                             continue;
135: 
136:                         // Tipp 14: "Der Deutsche raucht Rothmanns"
137:                         if (!Tip_14_Verify())
138:                             continue;
139: 
140:                         // reached a solution
141:                         PrintSolution();
142:                     }
143:                 }
144:             }
145:         }
146:     }
147: }

Beispiel 7. Redesign der Methode Solve-Methode aus Klasse EinsteinRiddleSolver.


Die erneute Ausführung liefert dasselbe Ergebnis zurück, mit 15 Millisekunden ist die Ausführungszeit ca. um den Faktor 2000 schneller geworden!