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/CSharp_Einstein_Riddle.git.

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

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

Auch der Entwurf einer Klasse House ist trivial. Es genügt, einen Strukturtyp zu definieren, der ausschließlich die verschiedenen Eigenschaften eines Hauses zusammenbündelt:

struct House
{
    public Nationality Nationality { get; set; }
    public HouseColor HouseColor { get; set; }
    public Cigarette Cigarette { get; set; }
    public Drink Drink { get; set; }
    public Pet Pet { get; set; }
}

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 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 Permutationen von 4 oder 5 Elementen. 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 1:

01: class EinsteinRiddleSolver
02: {
03:     private House[] houses;
04:     private char[][] four_permutations;
05:     private int[][] five_permutations;
06: 
07:     // c'tor
08:     public EinsteinRiddleSolver()
09:     {
10:         this.InitPermutations();
11: 
12:         // create five houses
13:         this.houses = new House[5];
14:         for (int i = 0; i < this.houses.Length; i++)
15:             this.houses[i] = new House();
16: 
17:         // Tip 7: "Der Mann, der im mittleren Haus wohnt, trinkt gerne Milch"
18:         this.houses[2].Drink = Drink.Milk;
19: 
20:         // Tip 9: "Der Norweger wohnt im ersten Haus"
21:         this.houses[0].Nationality = Nationality.Norwegian;
22: 
23:         // Tip 13: "Neben dem blauen Haus wohnt der Norweger"
24:         this.houses[1].HouseColor = HouseColor.Blue;
25:     }
26: 
27:     private void InitPermutations()
28:     {
29:         this.four_permutations = new char[][]
30:         {
31:             new char[] {'a', 'b', 'c', 'd'}, new char[] {'a', 'c', 'b', 'd'},
32:             new char[] {'b', 'a', 'c', 'd'}, new char[] {'b', 'c', 'a', 'd'},
33:             new char[] {'c', 'a', 'b', 'd'}, new char[] {'c', 'b', 'a', 'd'},
34:             ... 
35:             new char[] {'d', 'c', 'a', 'b'}, new char[] {'d', 'c', 'b', 'a'}
36:         };
37: 
38:         this.five_permutations = new int[][]
39:         {
40:              new int[] { 0, 1, 2, 3, 4 }, new int[] { 0, 1, 2, 4, 3 },
41:              new int[] { 0, 1, 3, 2, 4 }, new int[] { 0, 1, 3, 4, 2 },
42:              new int[] { 0, 1, 4, 2, 3 }, new int[] { 0, 1, 4, 3, 2 },
43:              ...
44:              new int[] { 4, 3, 2, 0, 1 }, new int[] { 4, 3, 2, 1, 0 }
45:         };
46:     }
47:     ...
48: }

Beispiel 1. Klasse EinsteinRiddleSolver: Ablage der Permutationen.


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 18, 21 und 24 von Listing 1 werden die Hinweise 7, 9 und 13 direkt umgesetzt.

Möglicherweise fällt Ihnen eine Unstimmigkeit in Listing 1 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). Die Vierer-Permutationen hingegen sind mit Buchstaben niedergeschrieben, 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 allgemeinen Schreibweise. Wenn wir die Buchstaben in Zahlen umwandeln, müssen wir jeweils die Kategorie mit berücksichtigen und eine entsprechende Anpassung vornehmen.

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

001: public void Solve()
002: {
003:     // iterate cigarettes
004:     for (int i = 0; i < this.five_permutations.Length; i++)
005:     {
006:         int[] perm1 = this.five_permutations[i];
007:         this.houses[perm1[0]].Cigarette = Cigarette.PallMall;
008:         this.houses[perm1[1]].Cigarette = Cigarette.Marlboro;
009:         this.houses[perm1[2]].Cigarette = Cigarette.DunHill;
010:         this.houses[perm1[3]].Cigarette = Cigarette.Winfield;
011:         this.houses[perm1[4]].Cigarette = Cigarette.Rothmans;
012: 
013:         // iterate pets
014:         for (int j = 0; j < this.five_permutations.Length; j++)
015:         {
016:             int[] perm2 = this.five_permutations[j];
017:             this.houses[perm2[0]].Pet = Pet.Bird;
018:             this.houses[perm2[1]].Pet = Pet.Cat;
019:             this.houses[perm2[2]].Pet = Pet.Dog;
020:             this.houses[perm2[3]].Pet = Pet.Fish;
021:             this.houses[perm2[4]].Pet = Pet.Horse;
022: 
023:             // iterate drinks
024:             for (int k = 0; k < this.four_permutations.Length; k++)
025:             {
026:                 char[] perm3 = this.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:                 this.houses[k1].Drink = Drink.Beer;
042:                 this.houses[k2].Drink = Drink.Coffee;
043:                 this.houses[k3].Drink = Drink.Tea;
044:                 this.houses[k4].Drink = Drink.Water;
045: 
046:                 // iterate colors
047:                 for (int l = 0; l < this.four_permutations.Length; l++)
048:                 {
049:                     char[] perm4 = this.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:                     this.houses[l1].HouseColor = HouseColor.Green;
065:                     this.houses[l2].HouseColor = HouseColor.Red;
066:                     this.houses[l3].HouseColor = HouseColor.White;
067:                     this.houses[l4].HouseColor = HouseColor.Yellow;
068: 
069:                     // iterate nations
070:                     for (int m = 0; m < this.four_permutations.Length; m++)
071:                     {
072:                         char[] perm5 = this.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:                         this.houses[m1].Nationality = Nationality.British;
088:                         this.houses[m2].Nationality = Nationality.Swedish;
089:                         this.houses[m3].Nationality = Nationality.Danish;
090:                         this.houses[m4].Nationality = Nationality.German;
091: 
092:                         // Tipp 1: "Der Brite lebt im roten Haus"
093:                         if (!this.Tip_01_Verify())
094:                             continue;
095: 
096:                         // Tipp 2: "Der Schwede hält einen Hund"
097:                         if (!this.Tip_02_Verify())
098:                             continue;
099: 
100:                         // Tipp 3: "Der Däne trinkt gerne Tee"
101:                         if (!this.Tip_03_Verify())
102:                             continue;
103: 
104:                         // Tipp 4: "Das grüne Haus steht links vom weißen Haus"
105:                         if (!this.Tip_04_Verify())
106:                             continue;
107: 
108:                         // Tipp 5: "Der Besitzer des grünen Hauses trinkt Kaffee"
109:                         if (!this.Tip_05_Verify())
110:                             continue;
111: 
112:                         // Tipp 6: "Die Person, die Pall Mall raucht, hält einen Vogel"
113:                         if (!this.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 (!this.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 (!this.Tip_10_Verify())
128:                             continue;
129: 
130:                         // Tipp 11: "Der Mann, der ein Pferd hält, wohnt neben dem, der Dunhill raucht"
131:                         if (!this.Tip_11_Verify())
132:                             continue;
133: 
134:                         // Tipp 12: "Der Winfield-Raucher trinkt gerne Bier."
135:                         if (!this.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 (!this.Tip_14_Verify())
143:                             continue;
144: 
145:                         // Tipp 15: "Der Marlboro-Raucher hat einen Nachbarn, der Wasser trinkt"
146:                         if (!this.Tip_15_Verify())
147:                             continue;
148: 
149:                         // print solution
150:                         this.PrintSolution();
151:                     }
152:                 }
153:             }
154:         }
155:     }
156: }

Beispiel 2. Methode Solve 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 3:

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

Beispiel 3. 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 2 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 4:

001: public void Solve()
002: {
003:     // iterate cigarettes
004:     for (int i = 0; i < this.five_permutations.Length; i++)
005:     {
006:         int[] perm1 = this.five_permutations[i];
007:         this.houses[perm1[0]].Cigarette = Cigarette.PallMall;
008:         this.houses[perm1[1]].Cigarette = Cigarette.Marlboro;
009:         this.houses[perm1[2]].Cigarette = Cigarette.DunHill;
010:         this.houses[perm1[3]].Cigarette = Cigarette.Winfield;
011:         this.houses[perm1[4]].Cigarette = Cigarette.Rothmans;
012: 
013:         // iterate pets
014:         for (int j = 0; j < this.five_permutations.Length; j++)
015:         {
016:             int[] perm2 = this.five_permutations[j];
017:             this.houses[perm2[0]].Pet = Pet.Bird;
018:             this.houses[perm2[1]].Pet = Pet.Cat;
019:             this.houses[perm2[2]].Pet = Pet.Dog;
020:             this.houses[perm2[3]].Pet = Pet.Fish;
021:             this.houses[perm2[4]].Pet = Pet.Horse;
022: 
023:             // Tipp 6: "Die Person, die Pall Mall raucht, hält einen Vogel"
024:             if (!this.Tip_06_Verify())
025:                 continue;
026: 
027:             // Tipp 10: "Der Marlboro-Raucher wohnt neben dem, der eine Katze hält. "
028:             if (!this.Tip_10_Verify())
029:                 continue;
030: 
031:             // Tipp 11: "Der Mann, der ein Pferd hält, wohnt neben dem, der Dunhill raucht"
032:             if (!this.Tip_11_Verify())
033:                 continue;
034: 
035:             // iterate drinks
036:             for (int k = 0; k < this.four_permutations.Length; k++)
037:             {
038:                 char[] perm3 = this.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:                 this.houses[k1].Drink = Drink.Beer;
054:                 this.houses[k2].Drink = Drink.Coffee;
055:                 this.houses[k3].Drink = Drink.Tea;
056:                 this.houses[k4].Drink = Drink.Water;
057: 
058:                 // Tipp 12: "Der Winfield-Raucher trinkt gerne Bier."
059:                 if (!this.Tip_12_Verify())
060:                     continue;
061: 
062:                 // Tipp 15: "Der Marlboro-Raucher hat einen Nachbarn, der Wasser trinkt"
063:                 if (!this.Tip_15_Verify())
064:                     continue;
065: 
066:                 // iterate colors
067:                 for (int l = 0; l < this.four_permutations.Length; l++)
068:                 {
069:                     char[] perm4 = this.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:                     this.houses[l1].HouseColor = HouseColor.Green;
085:                     this.houses[l2].HouseColor = HouseColor.Red;
086:                     this.houses[l3].HouseColor = HouseColor.White;
087:                     this.houses[l4].HouseColor = HouseColor.Yellow;
088: 
089:                     // Tipp 4: "Das grüne Haus steht links vom weißen Haus"
090:                     if (!this.Tip_04_Verify())
091:                         continue;
092: 
093:                     // Tipp 5: "Der Besitzer des grünen Hauses trinkt Kaffee"
094:                     if (!this.Tip_05_Verify())
095:                         continue;
096: 
097:                     // Tipp 8: "Der Besitzer des gelben Hauses raucht Dunhill"
098:                     if (!this.Tip_08_Verify())
099:                         continue;
100: 
101:                     // iterate nations
102:                     for (int m = 0; m < this.four_permutations.Length; m++)
103:                     {
104:                         char[] perm5 = this.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:                         this.houses[m1].Nationality = Nationality.British;
120:                         this.houses[m2].Nationality = Nationality.Swedish;
121:                         this.houses[m3].Nationality = Nationality.Danish;
122:                         this.houses[m4].Nationality = Nationality.German;
123: 
124:                         // Tipp 1: "Der Brite lebt im roten Haus"
125:                         if (!this.Tip_01_Verify())
126:                             continue;
127: 
128:                         // Tipp 2: "Der Schwede hält einen Hund"
129:                         if (!this.Tip_02_Verify())
130:                             continue;
131: 
132:                         // Tipp 3: "Der Däne trinkt gerne Tee"
133:                         if (!this.Tip_03_Verify())
134:                             continue;
135: 
136:                         // Tipp 14: "Der Deutsche raucht Rothmanns"
137:                         if (!this.Tip_14_Verify())
138:                             continue;
139: 
140:                         // print solution
141:                         this.PrintSolution();
142:                     }
143:                 }
144:             }
145:         }
146:     }
147: }

Beispiel 4. Redesign der Methode Solve 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!