Das Haus vom Nikolaus



Wer kennt es nicht? Das Haus vom Nikolaus - ein Spiel für Kinder, welches für mich selbst heute noch in so mancher monotonen Vorlesung das Mittel gegen Müdigkeit und Langeweile ist. So kam ich denn auch auf die Idee einer algorithmischen Umsetzung des Ganzen, woraus ein C-Programm und der folgende Artikel entstanden sind.
Ich möchte dabei zeigen, wie ein Algorithmus zum Finden aller Möglichkeiten zur Konstruktion des Hauses aussehen könnte und wie ich diesen Algorithmus schließlich auch umgesetzt habe.

Grundgedanken


Um mir ein wenig Schreibarbeit zu ersparen, werde ich "Das Haus des Nikolaus" fortwährend nur noch als "Nikohaus" bezeichnen. Für ganz Unwissende sei das Nikohaus-Spiel hier kurz noch einmal erklärt. Man baut dabei ein "Haus" auf, wie es nachfolgend gezeigt ist:


Voraussetzung ist, dass man das komplette Haus "ohne Absetzen des Stiftes" zeichnet, also in einer durchgehenden Linie von Ecke zu Ecke, was nicht immer zum Ziel führt, da man öfters in eine "Sackgasse" gerät als das komplette Haus gezeichnet zu haben. Die Assoziation zum Begriff "Haus des Nikolaus" haben wir dadurch, dass wir an jeder Ecke, die wir erreichen, ein Wort des Satzes "Das ist das Haus vom Nikolaus" aussprechen.

Nikohaus als Graph


Jede algorithmische Umsetzung eines gegebenen Problems fordert ein step-by-step-System.
Eine erste Überlegung ist z.B. die, dass man das Nikohaus als ungerichteten Graphen ansehen kann mit 5 Knoten (den Ecken des Hauses) und 8 Bögen/Kanten (die Verbindungen zwischen den Ecken). Ungerichtet bedeutet dabei "in beide Richtungen gerichtet", d.h. dass man einen Bogen sowohl in der einen als auch in der anderen Richtung ablaufen kann (Anm.: ein wenig Graphentheorie wäre zum Verständnis der folgenden Überlegungen sicher von Vorteil - Ziel dieses Artikels soll es nämlich nicht sein, auf diese doch sehr umfangreiche Materie tiefgründiger einzugehen). Unter diesem Aspekt könnte das Basismodell und eine mögliche Konstruktion des Nikohauses folgendermaßen aussehen (die Kantenbewertungen entsprechen der Reihenfolge des Ablaufens des Graphen):


D.h. beim Aufbau des Nikohauses "richtet" man den Graphen - fertig konstruiert ist das Haus, wenn alle Bögen gerichtet sind, also jeder der 8 Bögen genau einmal durchlaufen worden ist.

Algorithmische Umsetzung des Graphen


Natürlich könnte man für die programmiertechnische Realisierung eines Graphen eine universelle Klasse erzeugen/hinzunehmen und die benötigten Operationen auf einer Instanz dieser Klasse ausführen. Dies ist für solch ein kleines Problem allerdings etwas übertrieben und wäre nur in größeren Software-Projekten notwendig. Vielmehr will ich hier auf eine elegante wie einfache Lösung zurück greifen: eine Adjazenzmatrix.
"Adjazent" heißt "verbunden" und man kann sich leicht vorstellen, dass diese Matrix die Verbindungen zwischen den einzelnen Knoten des Nikohauses abspeichert. Vielmehr kann man mit einer Adjazenzmatrix jeden beliebigen Graphen beschreiben - bei größeren Graphen verliert man allerdings schnell die Übersicht, sodass hier meist ein objektorientierter Ansatz mit Klassen bevorzugt werden wird. Eine solche Matrix ist boolsch, d.h. in ihr müssen nur die Werte 0 und 1 gespeichert werden, um anzuzeigen, ob 2 Knoten miteinander verbunden sind.
Schauen wir uns einmal die Adjazenzmatrix des Nikohauses an:

Interpretation: eine Zeile gibt die Nummer des Knotens an, von welchem ein Bogen ausgeht; eine Spalte gibt die Nummer des Knotens an, zu dem ein Bogen führt. Steht in Zeile i und Spalte j der Matrix eine "1", so heißt das, dass von Knoten i nach Knoten j ein Bogen führt; andererseits sagt eine "0" aus, dass kein Bogen von i nach j existiert. Zu beachten ist, dass die Matrix symmetrisch ist. Dies ist der Fall, da unser Nikohaus-Graph ungerichtet ist - bei allen ungerichteten Graphen stellt die Adjazenzmatrix eine symmetrische n*n-Matrix dar. Meist wird auch bei gerichteten Graphen eine n*n-Matrix verwendet, wobei n die Anzahl der Knoten im Graphen ist.

Lösung des Problems durch Backtracking


Mit einem Programmiermodell des Graphen in Form der Adjazenzmatrix bewaffnet kann man sich an die eigentliche Problemlösung machen. Wir gehen zunächst einmal davon aus, dass das Nikohaus von jedem der 5 Startknoten aus komplett konstruiert werden kann, womit sich folgender grober Programmablaufplan erstellen lässt:


Wenn man an einem Knoten angelangt ist und von da aus keine Bögen mehr abgehen, die man nicht schon einmal betrachtet hätte, geht mal also zu dem Knoten zurück, von dem aus man zum aktuellen Knoten gekommen ist. Dieses System des Zurückgehens, wenn man nicht mehr weiter kann, wird in der Informatik als Backtracking bezeichnet und findet viele Anwendungsgebiete, darunter vor allem auch die Suche des Ausgangs aus einem Labyrinth. Programmiertechnisch realisieren lässt sich das Backtracking am elegantesten mit rekursiven Funktionsaufrufen und so stellt meine Lösung des Nikohaus-Problems auch eine rekursive dar.
Die notwendige rekursive Funktion könnte in C z.B. so aussehen: 

  void haus_rek(bool mtrx[5][5], const int kn, const int count){
    int i;
    for(i=0;i<5;i++)
	if(mtrx[kn][i]==1){
	  if(count==7) return;
	  mtrx[kn][i]=0; mtrx[i][kn]=0;
	  haus_rek(mtrx,i,count+1);
	  mtrx[kn][i]=1; mtrx[i][kn]=1;
	}
  }

Und der dazu gehörige Aufruf aus main() heraus: 

  int main(void){
    bool mtrx[5][5]={{0,1,1,1,0},
	 	     {1,0,1,1,0},
	 	     {1,1,0,1,1},
	 	     {1,1,1,0,1},
	 	     {0,0,1,1,0} };
    haus_rek(mtrx,0,0);
    return 0;
  }

Natürlich fehlt hier noch der Code zum Hochzaehlen der Möglichkeiten, wie das Nikohaus konstruiert werden kann sowie der Ausgaben. Dieses Sniplet soll erst einmal nur die Funktionsweise der rekursiven Funktion veranschaulichen.
Schauen wir uns haus_rek() einmal genauer an: der erste Parameter entspricht der 5*5-Adjazenzmatrix und muss variabel sein. Der zweite Parameter "const int kn" ist immer der aktuelle Knoten, von dem ausgegangen wird (also eine Matrixzeile). "const int count" schließlich zählt quasi die Rekursionsebene, in der man sich gerade befindet und stellt die Anzahl der Bögen dar, die man bei der aktuellen Konstruktion schon durchlaufen hat.
Zunächst werden in einer for-Schleife alle 5 Elemente der Matrixzeile kn betrachtet. Sollte ein Element dieser Zeile "0" sein, so wird zum nächsten Element verwiesen. Sollte ein Element "1" sein, so gibt es zwei Möglichkeiten: 1.) count==7, was bedeutet, dass wir, wenn wir zum nächsten Knoten gehen, das Haus fertig konstruiert haben. Da eine "1" in der Zeile vorhanden ist, wissen wir, dass es noch eine Verbindung zu einem anderen Knoten gibt und dass dieser Bogen das Haus komplettiert. Demnach kann man einen Erfolg beim Erstellen verzeichnen und einen Knoten zurück gehen (mit return die Funktion verlassen). 2.) ist count!=7, so wird zunächst der Bogen, den man jetzt beschreiten will, in der Matrix 0 gesetzt. Da es sich um einen ungerichteten Graphen handelt, muss man sowohl (kn,i) als auch (i,kn) auf 0 setzen. Dies ist notwendig, damit eine tiefere Rekursionsebene den Bogen nicht mehr als begehbar betrachtet und diesen ablaufen würde. Anschließend folgt der rekursive Funktionsaufruf mit der so veränderten Matrix, dem Knoten, auf den verwiesen wird und dem inkrementierten Zähler. Kehrt dieser Aufruf zurück, entweder weil das Haus korrekt errichtet wurde oder weil man in einer Sackgasse angekommen ist, so wird die Ursprungsmatrix hergestellt, indem (kn,i) und (i,kn) von 0 wieder auf 1 gesetzt werden. Notwendig ist dies, da die Matrix "call by value" übergeben wird und sich eine Änderung dieser auf alle Rekursionsebenen auswirkt. Da eine aufrufende Funktion die Bögen tieferer Rekursionsebenen jedoch nie begangen hat, muss garantiert werden, dass diese Bögen in der Matrix noch vorhanden sind.

So geht der Algorithmus sukzessive alle Möglichkeiten durch, wie das Nikohaus von einem Knoten start aus konstruiert werden kann. Natürlich will man noch eine Ausgabe auf den Bildschirm erhalten, um das Ergebnis auswerten zu können. Folgendes Programm ist eine komplette Implementation mit Ausgabe der Wege, mit denen man von Knoten 0 aus das Haus konstruieren kann und der Anzahl aller Möglichkeiten sowie Sackgassen, auf die der Algorithmus stößt: [ nikohaus.c ]

Ergebnis-Auswertung


Die Ausgabe des Programms liefert 44 Möglichkeiten, wie das Nikohaus jeweils von Knoten 0 und 1 ausgehend konstruiert werden kann. Von allen anderen Knoten aus kann das Haus nicht erbaut werden. Eine einfache Überlegung, warum dies so ist: Knoten 0 und 1 haben 3 mit ihnen verbundene Bögen. Beim Durchlauf eines Knotens durch den Nikohaus-Algorithmus werden 2 Bögen involviert: ein Eingangsbogen und ein Bogen, über den man den Knoten verlässt. Da 3 nun eine ungerade Zahl ist, bleibt nach einem Durchlauf des Knotens 1 Bogen übrig und dieser kann nur abgelaufen werden, wenn sich der jeweilige Bogen am Anfang oder am Ende der Konstruktion des Hauses befindet. Damit ist klar: wenn Knoten 0 Startknoten ist, so muss Knoten 1 am Ende der Konstruktionskette stehen, damit das Haus vollständig erbaut werden kann. Dies belegt auch die Ausgabe des Programms: bei allen 44 Möglichkeiten, die es von Knoten 0 aus gibt, ist 1 der Endknoten.

Schlussbemerkungen


Mit ein paar logischen Überlegungen, ein wenig Graphentheorie und vor allem der Adjazenzmatrix und Rekursion war es schlussendlich doch nicht allzu schwer, einen Algorithmus zum "Haus des Nikolaus"-Problem zu finden. Und weiterführend lässt sich jedes Problem dieser Art von Rundreise durch ein Ablaufen aller Knoten mit einem solchen Algorithmus modellieren. Für weitere Fragen und Anregungen bin ich über meine Mail-Adresse stets zu erreichen.

(c) 2003 by RTC, www.linux-related.de
Dieses Dokument unterliegt der GNU Free Documentation License