Das Haus des Nikolaus

1. Aufgabe

Das Haus des Nikolaus ist ein altes Zeichenspiel und vermutlich jedem Leser unter Ihnen bekannt, der Kinder sein eigen nennen darf. Ziel des Spiels ist es, ein Haus (wie in Abbildung 1 dargestellt) ohne Absetzen des Stiftes zu zeichnen, also in einem Zug mit acht Strecken. Sie werden die Beobachtung machen, dass dies nicht immer zum Ziel führt, da man öfters in die Situation gelangt, eine Strecke mehrmals zeichnen zu müssen, was nicht erlaubt ist. Kinder erfreuen sich an diesem Spiel zusätzlich daran, ihre Eltern lautstark am Spielen zu beteiligen, indem sie an jeder Ecke, die sie erreichen, ein Wort des Satzes Das ist das Haus vom Ni-ko-laus aussprechen – zu jeder Strecke gehört ein Wort bzw. eine Silbe. Wie viele verschiedene Möglichkeiten gibt es, das Haus zu zeichnen? Schreiben Sie ein Programm, das alle Möglichkeiten berechnet und in ansprechender Form auf der Konsole ausgibt.

Das Haus des Nikolaus – als Spiel betrachtet.

Abbildung 1. Das Haus des Nikolaus – als Spiel betrachtet.


Die Umsetzung der Fragestellung erfordert zunächst eine Analyse des geschilderten Problems mit der Zielsetzung, ein mathematisches Modell zu finden, auf das das Haus des Nikolaus abbildbar ist. Einfache Überlegungen zeigen, dass das Haus des Nikolaus als ein ungerichteter Graph angesehen werden kann mit fünf Knoten (die Ecken des Hauses) und acht Kanten (die Verbindungen zwischen den Knoten), siehe die linke Seite in Abbildung 2. Unter einem ungerichteten Graphen versteht man einen Graphen, für dessen Kanten keine Regelung besteht, in welcher Richtung sie durchlaufen werden müssen.

Das Haus des Nikolaus – von einem Mathematiker betrachtet.

Abbildung 2. Das Haus des Nikolaus – von einem Mathematiker betrachtet.


Damit haben wir die Aufgabenstellung auf die Frage reduziert, wieviele Wege es in einem bestimmten ungerichteten Graphen gibt, der jede Kante genau einmal traversiert. Eine Lösung des Problems finden Sie in Abbildung 2 auf der rechten Seite vor: Eine zu zeichnende Kante wird als Paar der zugehörigen Knoten repräsentiert: (1,2) für die erste gezeichnete Kante, (2,4) für die zweite usw. Wir erkennen am Beispiel von (1,5) auch, dass nicht jedes Knotenpaar eine gültige Kante beschreibt!

1.1. Iterativer Lösungsansatz

Wir betrachten in dieser Fallstudie zwei Ansätze zur programmiersprachlichen Lösung der Aufgabe. Ein rekursiver Lösungsansatz setzt etwas mehr Kenntnisse aus der Graphentheorie voraus und wird im Anschluss betrachtet. Ein einfacherer Ansatz assoziiert eine Lösung mit einer Folge von Ziffern, also mit einer natürlichen Zahl. Dazu nummerieren wir die Ecken des Hauses durch, unten links liegt die Ecke 1, die Ziffern 2, 3 und 4 folgen entgegen dem Uhrzeigersinn für die weiteren Ecken des Rechtecks. Fehlt noch die Spitze, sie erhält die Ziffer 5. Dem in Abbildung 2 gezeichneten Haus ordnen wir folglich beim Malen die Ziffernfolge 1, 2, 4, 1, 3, 4, 5, 3, 2 zu, oder etwas kompakter die neunstellige Zahl 124134532.

Nicht alle neunstelligen Zahlen eignen sich zur Darstellung einer korrekten Zeichnung. Zahlen, die die Ziffern 6 bis 9 oder die Null enthalten, scheiden von vorne herein aus. Also kommen nur Zahlen zwischen 111111111 und 155555552 in Betracht. Von diesen Zahlen sind solche, die zweimal dieselbe Ziffer unmittelbar aufeinanderfolgend enthalten, wiederum nicht geeignet, da eine Kante prinzipiell nur zwischen zwei Knoten (mit unterschiedlicher Knotennummer) verlaufen kann. In dem zuvor beschriebenen Wertebereich scheiden also weitere Zahlen aus.

Nun sind wir fast schon am Ziel angekommen. Die Kanten des vorliegenden Graphen lauten gemäß der Knotennummerierung aus Abbildung 2 (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (3, 5) und (4, 5). Eine neunstellige Zahl mit den Ziffern z1, z2, ... , z9 beschreibt ebenfalls 8 Kanten (z1, z2), (z2, z3) bis (z8, z9). Finden wir jede Kante des Nikolaushauses genau einmal in der Menge der Kanten (zi, zi+1), i = 1,2,...,8 vor, so haben wir mit der neunstelligen Zahl einen zulässigen Weg zum Zeichnen gefunden.

Ein Mathematiker wiederum würde zu der Formulierung neigen, dass zwischen den beiden zuvor beschriebenen Kantenmengen genau dann eine bijektive Abbildung existiert, wenn ein zulässiger Pfad zum Zeichnen vorliegt. Da Sie aber definitiv kein Mathematikbuch erworben haben, vermutlich auch keines erwerben wollten, habe ich es bei der etwas anschaulicheren Darstellung belassen – Ihr ausdrückliches Einverständnis natürlich vorausgesetzt :). Nicht anders wollen wir es bei der nun folgenden Assoziation des Nikolaushauses mit einem ungerichteten Graphen handhaben.

1.2. Rekursiver Lösungsansatz

Der rekursive Ansatz geht in der mathematischen Betrachtung ein kleines Stück weiter und betrachtet die so genannte Adjazenzmatrix des Nikolaushaus-Graphen. Adjazent heißt verbunden. Durch eine Adjazenzmatrix wird beschrieben, welche Knoten eines Graphen miteinander verbunden sind und welche nicht. Konkret ist jeder Zeile der Adjazenzmatrix ein Knoten zugeordnet, von dem mindestens eine Kante ausgeht. Die Spalte wiederum spezifiziert die Nummer des Knotens, zu dem eine Kante führt. Steht in Zeile i und Spalte j der Matrix eine 1, so heißt das, dass von Knoten i nach Knoten j eine Kante führt. Andererseits sagt eine 0 aus, dass keine Kante zwischen i und j existiert. In einer Adjazenzmatrix kommen nur die Wert 0 und 1 vor, man spricht von einer booleschen Matrix. Wir tragen diesem Umstand der Gestalt Rechnung, dass wir in der nachfolgenden Umsetzung in C#-Quellcode nur Matrizen des Typs bool einsetzen.

Darüber hinaus machen wir am vorliegenden Beispiel die Beobachtung, dass die Adjazenzmatrix symmetrisch ist. Dies lässt sich recht einfach erklären: Da dem Nikolaushaus ein ungerichteter Graph entspricht, ist sowohl der Knoten i mit dem Knoten j verbunden als auch umgekehrt. Bei allen ungerichteten Graphen ist die Adjazenzmatrix symmetrisch. In Abbildung 3 finden Sie die Adjazenzmatrix des Hauses vom Nikolaus vor, die Einträge in der Matrix beziehen sich wieder auf die Nummern der Knoten aus Abbildung 2:

Adjazenzmatrix des Hauses vom Nikolaus.

Abbildung 3. Adjazenzmatrix des Hauses vom Nikolaus.


Mit Hilfe der Adjazenzmatrix des Nikolaushauses aus Abbildung 3 gehen wir algorithmisch nun wie folgt vor: Zunächst legen wir zum versuchsweisen Zeichnen eine zweite Matrix an, die genauso groß wie die Adjazenzmatrix des Nikolaushauses ist:

private bool[,] adjacent;  // adjacency matrix
private bool[,] painted;   // painted edges

In der Hilfsmatrix painted tragen wir jedes Mal, wenn wir eine Strecke zeichnen, an die entsprechende Stelle den Wert true ein. Löschen wir die Strecke wieder, müssen wir den Wert zurück auf false setzen. Zu Beginn ist das Zeichenblatt leer, alle Einträge in der Hilfsmatrix painted sind auf den Wert false gesetzt. Zusätzlich verwalten wir noch eine Liste mit den bislang gezeichneten Teilstrecken:

private List<Edge> current; // so far painted edges

Das Zusammenspiel der Adjazenzmatrix (Welche Kanten gibt es an welcher Stelle im Nikolaushaus) und der Hilfsmatrix (Welche Kanten habe ich versuchsweise schon gezeichnet!) funktioniert so:

  • Beginnend mit dem ersten Knoten versuchen wir, eine Strecke zu zeichnen. In der Adjazenzmatrix können wir nachschauen, zu welchen benachbarten Knoten überhaupt Kanten gezeichnet werden dürfen. Wollen wir die Kante zeichnen, muss in der Hilfsmatrix an der entsprechenden Stelle der Wert false eingetragen sein, denn andernfalls gibt es diese Strecke schon, was aber nicht der Fall sein darf, da das wiederholte Zeichnen derselben Strecke unzulässig ist. Wir tragen an der entsprechenden Stelle in der Hilfsmatrix den Wert true ein und halten damit fest, dass die Strecke soeben gezeichnet wurde. Zusätzlich tragen wir die gezeichnete Kante in die Liste der bislang gezeichneten Teilstrecken ein, danach beginnen wir das Verfahren (rekursiv) von Neuem. Als Startknoten zum Zeichnen einer Kante fungiert dieses Mal der Endknoten der zuletzt gezeichneten Kante.

  • Ist es beim erneuten Einstieg in das Verfahren möglich, eine Strecke zu zeichnen, haben wir das Problem um eine (von acht) Stufen vereinfacht.

  • Können wir beim aktuellen Startknoten keine Strecke zeichnen (in der Adjazenzmatrix finden wir an der entsprechende Stelle keine verfügbare Strecke vor – Wert false), müssen wir die zuletzt gezeichnete Strecke bildlich gesprochen wieder Löschen. Softwaretechnisch heißt das, dass sie in der Hilfsmatrix wieder auszutragen ist: Wert von true auf false setzen; in der Liste der bislang gezeichneten Teilstrecken ist die letzte Eintragung rückgängig zu machen. Wir verlassen diesen Abschnitt des Verfahrens damit ohne Erfolg.

  • Gelingt es auf diese Weise, insgesamt 8 Kanten zu zeichnen, haben wir eine Lösung gefunden. Wir löschen allerdings auch in diesem Fall die zuletzt gezeichnete Kante, um anschließend noch nach weiteren Lösungen zu suchen.

2. Lösung

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

Im Folgenden stellen wir Implementierungen sowohl für einen iterativen als auch einen rekursiven Lösungsansatz vor. Beide Lösungen besitzen natürlich gemeinsame Codeanteile. Diese lassen sich, ganz im Sinne des objektorientierten Paradigmas, elegant in einer (abstrakten) Basisklasse HouseOfSantaClaus zusammenfassen. Vorbereitend betrachten wir in Listing 1 eine Klasse Edge, mit ihrer Hilfe beschreiben wir die Kanten des Nikolaushauses:

01: class Edge
02: {
03:     private int x;
04:     private int y;
05: 
06:     public Edge(int x, int y)
07:     {
08:         this.x = x;
09:         this.y = y;
10:     }
11: 
12:     // properties
13:     public int X
14:     {
15:         get
16:         {
17:             return this.x;
18:         }
19:     }
20: 
21:     public int Y
22:     {
23:         get
24:         {
25:             return this.y;
26:         }
27:     }
28: 
29:     // class helper method
30:     public static List<Edge> ToEdges(int number)
31:     {
32:         List<Edge> result = new List<Edge>();
33:         for (int i = 0; i < 8; i++)
34:         {
35:             int rem1 = number % 10;
36:             number /= 10;
37:             int rem2 = number % 10;
38: 
39:             // Note:
40:             // 'number' is traversed from right to left, therefore
41:             // a) we change the order of digits when constructing an edge object
42:             // b) we insert edge objects at begin of list
43:             Edge e = new Edge(rem2, rem1);
44:             result.Insert(0, e);
45:         }
46:         return result;
47:     }
48: 
49:     // overrides
50:     public override bool Equals(Object obj)
51:     {
52:         Edge tmp = (Edge)obj;
53:         return
54:             ((this.x == tmp.x && this.y == tmp.y) ||
55:              (this.x == tmp.y && this.y == tmp.x)) ? true : false;
56:     }
57: 
58:     public override String ToString()
59:     {
60:         return String.Format("[{0},{1}]", this.x, this.y);
61:     }
62: 
63:     // just to prevent compiler warning
64:     public override int GetHashCode()
65:     {
66:         return base.GetHashCode();
67:     }
68: }

Beispiel 1. Hilfsklasse Edge.


Die abstrakte Basisklasse HouseOfSantaClaus führen wir aus mehreren Gründen ein. Zum einen, um festzulegen, dass es eine abstrakte Methode Solve gibt, die dazu da ist, die Menge aller Lösungen des Problems zu berechnen. Damit ist klar, welche Erwartungen an eine Spezialisierung der Klasse HouseOfSantaClaus gestellt werden. Zum anderen, um eine Reihe von Methoden zu implementieren, die von allen abgeleiteten Klassen einfach übernommen werden können (im Sinne der Vererbung) und damit deren Realisierung vereinfachen. Dazu zählen Eigenschaften wie Count und Solutions, um die Lösungen und deren Anzahl zu beschreiben, wie auch eine Methode PrintSolutions, um die Lösungen komfortabel auf der Konsole auszugeben. Eine Implementierung der Aufzählungsschnittstelle IEnumerator, die die Lösungen der Reihe nach traversiert, ist ebenfalls Bestandteil der Basisklasse, siehe Listing 2:

001: abstract class HouseOfSantaClaus : IEnumerator, IFormattable
002: {
003:     protected List<List<Edge>> solutions;  // list of all solutions
004:     private int index;                     // enumerator index
005: 
006:     // c'tor
007:     public HouseOfSantaClaus()
008:     {
009:         this.solutions = new List<List<Edge>>();
010:         this.index = -1;
011:     }
012: 
013:     // properties
014:     public int Count
015:     {
016:         get
017:         {
018:             return this.solutions.Count;
019:         }
020:     }
021: 
022:     public List<List<Edge>> Solutions
023:     {
024:         get
025:         {
026:             // return a copy to the caller
027:             List<List<Edge>> copy = new List<List<Edge>>();
028:             for (int i = 0; i < this.solutions.Count; i++)
029:                 copy.Add(solutions[i]);
030:             return copy;
031:         }
032:     }
033: 
034:     // public interface
035:     public void PrintSolutions()
036:     {
037:         for (int i = 0; i < this.solutions.Count; i++)
038:             Console.WriteLine("{0,2}: {1}", i + 1, this.solutions[i]);
039:     }
040: 
041:     // abstract member
042:     public abstract void Solve();
043: 
044:     // implementation of interface 'IEnumerator'
045:     public Object Current
046:     {
047:         get
048:         {
049:             return this.solutions[this.index];
050:         }
051:     }
052: 
053:     public bool MoveNext()
054:     {
055:         this.index ++;
056:         return (this.index < this.solutions.Count) ? true : false;
057:     }
058: 
059:     public void Reset()
060:     {
061:         this.index = -1;
062:     }
063: 
064:     // contract with base class
065:     public override String ToString()
066:     {
067:         String s = "";
068:         for (int i = 0; i < this.solutions.Count; i++)
069:         {
070:             List<Edge> egdes = this.solutions[i];
071: 
072:             for (int j = 0; j < egdes.Count; j++)
073:             {
074:                 s += egdes[j].ToString();
075:                 if (j < egdes.Count - 1)
076:                     s += ", ";
077:             }
078:             s += Environment.NewLine;
079:         }
080:         return s;
081:     }
082: 
083:     public String ToString(String format, IFormatProvider formatProvider)
084:     {
085:         if (format == null)
086:             return this.ToString();
087: 
088:         if (format.Equals ("Edges"))
089:         {
090:             return this.ToString();
091:         }
092:         else if (format.Equals("Path"))
093:         {
094:             String s = "";
095:             for (int i = 0; i < this.solutions.Count; i++)
096:             {
097:                 List<Edge> egdes = this.solutions[i];
098: 
099:                 Edge e = egdes[0];
100:                 s += String.Format("{0}->{1}", e.X, e.Y);
101: 
102:                 for (int j = 1; j < egdes.Count; j++)
103:                 {
104:                     Edge e1 = egdes[j];
105:                     s += String.Format ("->{0}", e1.Y);
106:                 }
107: 
108:                 s += "    ";
109:                 if (i % 2 == 1)
110:                     s += Environment.NewLine;
111:             }
112:             return s;
113:         }
114:         else
115:             return this.ToString();
116:     }
117: }

Beispiel 2. Abstrakte Basisklasse HouseOfSantaClaus.


Die Implementierung der ToString-Methode in Listing 2, Zeile 65 ff., ist etwas umfangreicher ausgefallen. Es werden – mit Hilfe der Standardschnittstelle IFormattable zwei Ausgabeformate unterstützt. Zum einen kann man die gefundenen Kantenobjekte so ausgeben:

[1,2], [2,3], [3,1], [1,4], [4,3], [3,5], [5,4], [4,2]
[1,2], [2,3], [3,1], [1,4], [4,5], [5,3], [3,4], [4,2]
[1,2], [2,3], [3,4], [4,1], [1,3], [3,5], [5,4], [4,2]
...

Alternativ gibt es auch eine zweite Darstellungsvariante, sie sieht so aus:

1 -> 2 -> 3 -> 1 -> 4 -> 3 -> 5 -> 4 -> 2
1 -> 2 -> 3 -> 1 -> 4 -> 5 -> 3 -> 4 -> 2
1 -> 2 -> 3 -> 4 -> 1 -> 3 -> 5 -> 4 -> 2
...

Der Entwurf der Klasse HouseOfSantaClaus ließ es bereits erkennen: Abgeleitete Klassen müssen sich nur noch um die Berechnung der Lösungen kümmern, die Infrastruktur zur komfortablen Verwaltung der Lösungen wird ihnen von der Basisklasse bereit gestellt. In Listing 3 finden Sie die Klasse HouseOfSantaClausIterative mit einer iterativen Lösungsstrategie vor:

001: class HouseOfSantaClausIterative : HouseOfSantaClaus
002: {
003:     private const int Min = 111111111;
004:     private const int Max = 155555552;
005: 
006:     private int[] digits;
007: 
008:     public HouseOfSantaClausIterative()
009:     {
010:         this.digits = new int[9];
011:     }
012: 
013:     // contract with base class
014:     public override void Solve()
015:     {
016:         for (int i = Min; i <= Max; i++)
017:         {
018:             if (!this.IsSolution(i))
019:                 continue;
020: 
021:             List<Edge> edges = Edge.ToEdges(i);
022:             this.solutions.Add(edges);
023:         }
024:     }
025: 
026:     // private helper methods
027:     private bool IsSolution(int number)
028:     {
029:         this.NumberToDigits(number);
030: 
031:         // verify range of numbers (1..5)
032:         if (!this.CheckValidRangeOfDigits())
033:             return false;
034: 
035:         // exclude consecutive identical digits
036:         if (!this.CheckValidSequenceOfDigits())
037:             return false;
038: 
039:         // exclude edges between 1 and 5 or 2 and 5
040:         if (!this.CheckValidEdges())
041:             return false;
042: 
043:         // exclude duplicate edges
044:         if (!this.CheckForDuplicateEdges())
045:             return false;
046: 
047:         return true;
048:     }
049: 
050:     private bool CheckValidRangeOfDigits()
051:     {
052:         for (int i = 0; i < 9; i++)
053:         {
054:             if (digits[i] == 0 || digits[i] > 5)
055:                 return false;
056:         }
057:         return true;
058:     }
059: 
060:     private bool CheckValidSequenceOfDigits()
061:     {
062:         for (int i = 1; i < 9; i++)
063:         {
064:             if (digits[i-1] == digits[i])
065:                 return false;
066:         }
067:         return true;
068:     }
069: 
070:     private bool CheckValidEdges ()
071:     {
072:         for (int i = 1; i < 9; i ++)
073:         {
074:             int edge = digits[i-1] * 10 + digits[i];
075:             if (edge == 15 || edge == 51 || edge == 25 || edge == 52)
076:                 return false;
077:         }
078: 
079:         return true;
080:     }
081: 
082:     private bool CheckForDuplicateEdges ()
083:     {
084:         for (int i = 1; i < 9; i ++)
085:         {
086:             int edge1 = digits[i-1] * 10 + digits[i];
087:             int edge2 = digits[i] * 10 + digits[i-1];
088: 
089:             for (int j = i; j < 8; j ++)
090:             {
091:                 int edge = digits[j] * 10 + digits[j+1];
092:                 if(edge == edge1 || edge == edge2)
093:                     return false;
094:             }
095:         }
096: 
097:         return true;
098:     }
099: 
100:     private void NumberToDigits (int number)
101:     {
102:         for (int i = 8; i >= 0; i --)
103:         {
104:             digits[i] = number % 10;
105:             number /= 10;
106:         }
107:     }
108: }

Beispiel 3. Konkrete Klasse HouseOfSantaClausIterative.


Die Klasse HouseOfSantaClausIterative besteht, wie allgemein schon erläutert, aus zahlreichen Methoden, die sich mit der Analyse von Zahlen beschäftigen, um einen zulässigen Pfad des Nikolaushauses zu beschreiben. Im iterativen Ansatz spielen Zahlen eine Rolle, die ausschließlich aus den Ziffern 1 bis 5 bestehen, diese Überprüfung führt die Methode IsValidRangeOfDigits durch. Aufeinanderfolgende identische Ziffern in einer Zahl stellen keinen Pfad dar, hierzu gibt es eine Methode IsValidSequenceOfDigits, die derlei Zahlen ausschließt. Für gefundene Zahlen gibt es in der Klasse Edge eine Hilfsmethode, um eine Folge von Edge-Objekten zu erzeugen, sie lautet ToEdges (siehe Zeile 30 von Listing 1). Diese Darstellung wird von der zentralen Methode IsValidPath erwartet. Sie besitzt als Eingangsparameter einen möglichen Kandidaten in Form einer ganzen Zahl. Durch geschicktes Traversieren und Vergleichen aller Kanten des Eingangsparameters mit den Kanten des Nikolaushauses eruiert sie, ob der Eingangsparameter einen möglichen Pfad beschreibt oder nicht.

Einen gänzlichen anderen Ansatz der Problemlösung stellt das rekursive Verfahren in Listing 4 dar:

01: class HouseOfSantaClausRecursive : HouseOfSantaClaus
02: {
03:     private const int MaxNodes = 5;
04:     private const int MaxEdges = 8;
05: 
06:     private bool[,] adjacent;            // adjacency matrix
07:     private bool[,] painted;             // painted edges
08: 
09:     // constructing a single path
10:     private List<Edge> current;          // current solution
11:     private int paintedEdges = 0;        // edges so far painted
12: 
13:     public HouseOfSantaClausRecursive()
14:     {
15:         // adjacency matrix
16:         this.adjacent = new bool[,]
17:         {
18:             { false, true,  true,  true,  false },
19:             { true,  false, true,  true,  false },
20:             { true,  true,  false, true,  true  },
21:             { true,  true,  true,  false, true  },
22:             { false, false, true,  true,  false }
23:         };
24: 
25:         // empty trial matrix
26:         this.painted = new bool[MaxNodes, MaxNodes];
27: 
28:         this.current = new List<Edge>();
29:     }
30: 
31:     // contract with base class
32:     public override void Solve()
33:     {
34:         this.TryPaintingEdge(0);
35:     }
36: 
37:     // private helper methods
38:     private void PaintEdge(int from, int to)
39:     {
40:         this.painted[from, to] = true;
41:         this.painted[to, from] = true;
42: 
43:         Edge e = new Edge(from + 1, to + 1);
44:         this.current.Add(e);
45: 
46:         this.paintedEdges++;
47:     }
48: 
49:     private void ClearEdge(int from, int to)
50:     {
51:         this.painted[from, to] = false;
52:         this.painted[to, from] = false;
53: 
54:         int last = this.current.Count;
55:         this.current.RemoveAt(last - 1);
56: 
57:         this.paintedEdges--;
58:     }
59: 
60:     private void TryPaintingEdge(int from)
61:     {
62:         for (int to = 0; to < MaxNodes; to++)
63:         {
64:             if (this.adjacent[from, to])
65:             {
66:                 if (!this.painted[from, to])
67:                 {
68:                     this.PaintEdge(from, to);
69: 
70:                     if (!(this.paintedEdges == MaxEdges))
71:                     {
72:                         this.TryPaintingEdge(to);
73:                     }
74:                     else
75:                     {
76:                         // found solution !!!
77:                         List<Edge> path = new List<Edge>();
78:                         for (int i = 0; i < this.current.Count; i++)
79:                             path.Add(current[i]);
80:                         this.solutions.Add(path);
81:                     }
82: 
83:                     this.ClearEdge(from, to);
84:                 }
85:             }
86:         }
87:     }
88: }

Beispiel 4. Konkrete Klasse HouseOfSantaClausRecursive.


Kernstück der Klasse HouseOfSantaClausRecursive ist die Methode TryPaintingEdge. Sie startet beim Knoten 1 (Parameter vom Wert 0), traversiert alle prinzipiell in Frage kommenden Nachbarknoten in einer for-Wiederholungsschleife und versucht, mit Hilfe der Methode PaintEdge in einer Hilfsmatrix einen Pfad aufzubauen. Pro Aufruf von PaintEdge wird eine Kante gemalt, das Malen der nachfolgenden Kante erfolgt durch einen rekursiven Aufruf von TryPaintingEdge.

Nicht jeder Malvorgang ist von Erfolg gekrönt. Mit Hilfe der ClearEdge-Methode werden irrtümlich gemalte Kanten wieder gelöscht, es wird im Rekursionsbaum eine Ebene zurückgesprungen. Vom Erfolg des Algorithmus können Sie sich an Hand der Ausgabe erzeugen, sie ist in beiden Fällen (iterativ / rekursiv) identisch:

1->2->3->1->4->3->5->4->2    1->2->3->1->4->5->3->4->2
1->2->3->4->1->3->5->4->2    1->2->3->4->5->3->1->4->2
1->2->3->5->4->1->3->4->2    1->2->3->5->4->3->1->4->2
1->2->4->1->3->4->5->3->2    1->2->4->1->3->5->4->3->2
1->2->4->3->1->4->5->3->2    1->2->4->3->5->4->1->3->2
1->2->4->5->3->1->4->3->2    1->2->4->5->3->4->1->3->2
1->3->2->1->4->3->5->4->2    1->3->2->1->4->5->3->4->2
1->3->2->4->3->5->4->1->2    1->3->2->4->5->3->4->1->2
1->3->4->1->2->3->5->4->2    1->3->4->1->2->4->5->3->2
1->3->4->2->1->4->5->3->2    1->3->4->2->3->5->4->1->2
1->3->4->5->3->2->1->4->2    1->3->4->5->3->2->4->1->2
1->3->5->4->1->2->3->4->2    1->3->5->4->1->2->4->3->2
1->3->5->4->2->1->4->3->2    1->3->5->4->2->3->4->1->2
1->3->5->4->3->2->1->4->2    1->3->5->4->3->2->4->1->2
1->4->2->1->3->4->5->3->2    1->4->2->1->3->5->4->3->2
1->4->2->3->4->5->3->1->2    1->4->2->3->5->4->3->1->2
1->4->3->1->2->3->5->4->2    1->4->3->1->2->4->5->3->2
1->4->3->2->1->3->5->4->2    1->4->3->2->4->5->3->1->2
1->4->3->5->4->2->1->3->2    1->4->3->5->4->2->3->1->2
1->4->5->3->1->2->3->4->2    1->4->5->3->1->2->4->3->2
1->4->5->3->2->1->3->4->2    1->4->5->3->2->4->3->1->2
1->4->5->3->4->2->1->3->2    1->4->5->3->4->2->3->1->2