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. 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.

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:

static const int MaxNodes = 5;
bool adjacent[MaxNodes][MaxNodes];  // adjacency matrix
bool painted[MaxNodes][MaxNodes];   // 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. Programmiertechnisch könnte diese Liste vereinfacht in einer maximal neunstelligen Zahlen hinterlegt werden, so wie wir es beim iterativen Vorgehen skizziert haben:

int paintedEdges;  // edges so far painted

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.

Entwerfen Sie geeignet ein oder mehrere C++-Klassen, um alles Lösungen des „Haus des Nikolaus“-Problems zu ermitteln.

2. Lösung

Quellcode: Siehe auch github.com/peterloos/Cpp_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. Diese abstrakte Basisklasse führen wir aus mehreren Gründen ein. Zum einen, um festzulegen, dass es eine abstrakte Methode Solve (pure virtuell) 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 Methoden zu implementieren, die von allen abgeleiteten Klassen einfach übernommen werden können (im Sinne der Vererbung) und damit deren Realisierung vereinfachen. Dazu zählt eine getter-Methode wie NumberOfSolutions, um die Anzahl der Lösungen zu ermitteln wie auch eine Überladung des <<-Operators, um die berechneten Lösungen komfortabel auf der Konsole auszugeben. Schnittstelle und Implementierung der abstrakten Basisklasse HouseOfSantaClaus finden Sie in Listing 1 und Listing 2 vor:

01: class HouseOfSantaClaus
02: {
03: private:
04:     int  m_count;
05:     int* m_solutions;
06: 
07: public:
08:     // c'tor / d'tor
09:     HouseOfSantaClaus();
10:     virtual ~HouseOfSantaClaus();
11: 
12:     // public interface
13:     virtual void Solve() = 0;
14:     int NumberOfSolutions() { return m_count; }
15: 
16: protected:
17:     void AddSolution (int number);
18: 
19: private:
20:     // private helper method
21:     void PrintSolution (ostream& os, int number) const;
22: 
23:     // output
24:     friend ostream& operator<< (ostream&, const HouseOfSantaClaus&);
25: };

Beispiel 1. Schnittstelle der abstrakten Basisklasse HouseOfSantaClaus.


01: #include <iostream>
02: using namespace std;
03: 
04: #include <stdio.h>
05: #include "HouseOfSantaClaus.h"
06: 
07: // c'tor
08: HouseOfSantaClaus::HouseOfSantaClaus()
09: {
10:     m_count = 0;
11:     m_solutions = (int*) 0;
12: }
13: 
14: // d'tor
15: HouseOfSantaClaus::~HouseOfSantaClaus()
16: {
17:     delete[] m_solutions;
18: }
19: 
20: // private helper methods
21: void HouseOfSantaClaus::AddSolution (int number)
22: {
23:     // allocate new array
24:     int* tmp = new int [m_count+1];
25: 
26:     // copy existing solutions
27:     for (int i = 0; i < m_count; i ++)
28:         tmp[i] = m_solutions[i];
29: 
30:     // add new solution
31:     tmp[m_count] = number;
32: 
33:     // switch buffers
34:     delete[] m_solutions;
35:     m_solutions = tmp;
36:     m_count ++;
37: }
38: 
39: // output
40: ostream& operator<< (ostream& os, const HouseOfSantaClaus& house)
41: {
42:     for (int i = 0; i < house.m_count; i += 2)
43:     {
44:         house.PrintSolution(os, house.m_solutions[i]);
45:         os << "   ";
46: 
47:         if (i+1 < house.m_count)
48:             house.PrintSolution(os, house.m_solutions[i+1]);
49: 
50:         os << endl;
51:     }
52: 
53:     return os;
54: }
55: 
56: // private helper method
57: void HouseOfSantaClaus::PrintSolution (ostream& os, int number) const
58: {
59:     if (number >= 10)
60:     {
61:         int rest = number % 10;
62:         PrintSolution (os, number / 10);
63:         os << "->" << rest;
64:     }
65:     else
66:         os << number;
67: }

Beispiel 2. Implementierung der abstrakten Basisklasse HouseOfSantaClaus.


Die Implementierung des <<-Operators in den Zeilen 40 bis 53 (inklusive der Hilfsmethode PrintSolution) von Listing 2 führt zu folgender Darstellungsform berechneter Lösungen:

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

Der Entwurf der Klasse HouseOfSantaClaus lässt es bereits erkennen: Abgeleitete Klassen müssen sich nur noch um die Berechnung der Lösungen kümmern, die Infrastruktur zur komfortablen Ablage 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: #include <iostream>
002: using namespace std;
003: 
004: #include <stdio.h>
005: #include "HouseOfSantaClaus.h"
006: 
007: // c'tor
008: HouseOfSantaClausIterative::HouseOfSantaClausIterative()
009: {
010:     for (int i = 0; i < 9; i ++)
011:         m_digits[i] = 0;
012: }
013: 
014: // public interface
015: void HouseOfSantaClausIterative::Solve()
016: {
017:     for (int n = Min; n <= Max; n++)
018:     {
019:         if (! IsSolution(n))
020:             continue;
021: 
022:         AddSolution (n);
023:     }
024: }
025: 
026: // private helper methods
027: bool HouseOfSantaClausIterative::IsSolution(int number)
028: {
029:     NumberToDigits (number);
030: 
031:     // verify range of numbers (1..5)
032:     if (!CheckValidRangeOfDigits())
033:         return false;
034: 
035:     // exclude consecutive identical digits
036:     if (!CheckValidSequenceOfDigits())
037:         return false;
038: 
039:     // exclude edges between 1 and 5 or 2 and 5
040:     if (!CheckValidEdges())
041:         return false;
042: 
043:     // exclude duplicate edges
044:     if (!CheckForDuplicateEdges())
045:         return false;
046: 
047:     return true;
048: }
049: 
050: bool HouseOfSantaClausIterative::CheckValidRangeOfDigits()
051: {
052:     for (int i = 0; i < 9; i++)
053:     {
054:         if (m_digits[i] == 0 || m_digits[i] > 5)
055:             return false;
056:     }
057:     return true;
058: }
059: 
060: bool HouseOfSantaClausIterative::CheckValidSequenceOfDigits()
061: {
062:     for (int i = 1; i < 9; i++)
063:     {
064:         if (m_digits[i-1] == m_digits[i])
065:             return false;
066:     }
067:     return true;
068: }
069: 
070: bool HouseOfSantaClausIterative::CheckValidEdges()
071: {
072:     for (int i = 1; i < 9; i ++)
073:     {
074:         int edge = m_digits[i-1] * 10 + m_digits[i];
075:         if (edge == 15 || edge == 51 || edge == 25 || edge == 52)
076:             return false;
077:     }
078: 
079:     return true;
080: }
081: 
082: bool HouseOfSantaClausIterative::CheckForDuplicateEdges()
083: {
084:     for (int i = 1; i < 9; i ++)
085:     {
086:         int edge1 = m_digits[i-1] * 10 + m_digits[i];
087:         int edge2 = m_digits[i] * 10 + m_digits[i-1];
088: 
089:         for (int j = i; j < 8; j ++)
090:         {
091:             int edge = m_digits[j] * 10 + m_digits[j+1];
092:             if(edge == edge1 || edge == edge2)
093:                 return false;
094:         }
095:     }
096: 
097:     return true;
098: }
099: 
100: void HouseOfSantaClausIterative::NumberToDigits (int number)
101: {
102:     for (int i = 8; i >= 0; i --)
103:     {
104:         m_digits[i] = number % 10;
105:         number /= 10;
106:     }
107: }

Beispiel 3. Konkrete Klasse HouseOfSantaClausIterative.


Die Klasse HouseOfSantaClausIterative besteht aus zahlreichen Methoden, die sich mit der Analyse von Zahlen beschäftigen, um einen zulässigen Pfad im Nikolaushaus 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 CheckValidRangeOfDigits durch (Zeilen 50 bis 58). Aufeinanderfolgende identische Ziffern in einer Zahl stellen keinen Pfad dar, hierzu gibt es eine Methode CheckValidSequenceOfDigits (Zeilen 60 bis 68), die derlei Zahlen ausschließt. Da nicht alle Knoten des Nikolaushauses miteinander verbunden sind, wenden wir uns als Nächstes den unzulässigen Kanten zu. Durch die Methode CheckValidEdges (Zeilen 70 bis 80) wird sicher gestellt, dass Kanten zwischen den Knoten 1 und 5 bzw. 2 und 5 ausgeschlossen werden. Damit kommen wir zur letzten Hilfsmethode CheckForDuplicateEdges, deren Implementierung nicht übermäßig schwer ist, dafür aber etwas trickreich erscheinen mag (Zeilen 82 bis 98). Alle zulässigen Kanten dürfen in einem korrekten Pfad durch das Nikolaushaus nur genau einmal vorkommen. Durch zwei geschickt aufeinander abgestimmte for-Wiederholungsanweisungen wird dies durch die CheckForDuplicateEdges-Methode überprüft.

All die zuvor geschilderten Hilfsmethoden CheckValidRangeOfDigits, CheckValidSequenceOfDigits, CheckValidEdges und CheckForDuplicateEdges benötigen die einzelnen Ziffern einer Zahl der Einfachheit halber in einem Array angeordnet. Diesem Zweck dient die Hilfsmethode NumberToDigits in den Zeilen 100 bis 107. Damit besitzt die IsSolution-Methode in den Zeilen 27 bis 48 alle Zutaten, um iterativ alle möglichen (Zahlen-)Kandidaten des Nikolaushauses zu überprüfen. Der Vorteil dieser Lösung ist, dass sie mit vergleichsweise einfachen programmiersprachlichen Hilfsmitteln implementierbar ist. Nachteilig wirkt sich der Lösungsansatz bei der Betrachtung der Laufzeit des Programms aus, auf meinem Rechner sind es erheblich mehr als 10 Sekunden. Dies sollte Motivation genug sein, um uns nun einem gänzlichen anderen Ansatz in der Problemlösung zuzuwenden, dem rekursiven Lösungsansatz. Er wird in der Klasse HouseOfSantaClausRecursive in Listing 4 umgesetzt:

01: #include <iostream>
02: using namespace std;
03: 
04: #include <stdio.h>
05: #include "HouseOfSantaClaus.h"
06: 
07: // initialization of adjacency matrix
08: bool HouseOfSantaClausRecursive::m_adjacent[MaxNodes][MaxNodes] =
09: {
10:     { false, true,  true,  true,  false },
11:     { true,  false, true,  true,  false },
12:     { true,  true,  false, true,  true  },
13:     { true,  true,  true,  false, true  },
14:     { false, false, true,  true,  false }
15: };
16: 
17: HouseOfSantaClausRecursive::HouseOfSantaClausRecursive()
18: {
19:     m_currentPath = 1;   // first node is always '1'      
20:     m_paintedEdges = 0;  // number of painted edges
21: 
22:     // empty trial matrix
23:     for (int i = 0; i < MaxNodes; i ++)
24:         for (int j = 0; j < MaxNodes; j ++)
25:             m_painted[i][j] = false;
26: }
27: 
28: // public interface
29: void HouseOfSantaClausRecursive::Solve()
30: {
31:     TryPaintingEdge(0);
32: }
33: 
34: // private helper methods
35: void HouseOfSantaClausRecursive::PaintEdge (int from, int to)
36: {
37:     m_painted[from][to] = true;
38:     m_painted[to][from] = true;
39: 
40:     m_currentPath = 10 * m_currentPath + (to + 1);
41:     m_paintedEdges ++;
42: }
43: 
44: void HouseOfSantaClausRecursive::ClearEdge (int from, int to)
45: {
46:     m_painted[from][to] = false;
47:     m_painted[to][from] = false;
48: 
49:     m_currentPath = m_currentPath / 10;
50:     m_paintedEdges --;
51: }
52: 
53: void HouseOfSantaClausRecursive::TryPaintingEdge(int from)
54: {
55:     for (int to = 0; to < MaxNodes; to++)
56:     {
57:         if (m_adjacent[from][to])
58:         {
59:             if (!m_painted[from][to])
60:             {
61:                 PaintEdge(from, to);
62: 
63:                 if (! (m_paintedEdges == MaxEdges))
64:                 {
65:                     TryPaintingEdge(to);
66:                 }
67:                 else
68:                 {
69:                     // found solution !!!
70:                     AddSolution (m_currentPath);
71:                 }
72: 
73:                 ClearEdge(from, to);
74:             }
75:         }
76:     }
77: }

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

Solutions: 44