Labyrinth und Mathematik

Im heutigen Artikel geht es um Irrgärten und Mathematik. Wie entkommt man einem Labyrinth? Kann man raten und umherirren oder gibt es auch eine Strategie wie man garantiert entkommt? Wir wollen dies etwas genauer anschauen. Auch gibt es weiter unten die Möglichkeit dies spielerisch selbst zu versuchen.

Jeder kennt bestimmt das Spiel "Das verrückte Labyrinth". In diesem Gesellschaftsspiel geht es darum auf dem Spielfeld einen Weg inmitten des Labyrinths zu finden, um zu einem bestimmten Gegenstand zu kommen. Die Spielsteine legen ein Labyrinth mit Sackgassen, Kreuzungen und Geraden. Genauso sollen auch unsere Irrgärten im Folgenden aussehen.

Betritt man das Labyrinth, so gibt es maximal 4 Möglichkeiten sich zu bewegen.

• 1 Schritt nach links
• 1 Schritt nach oben
• 1 Schritt nach rechts
• 1 Schritt nach unten

Wie kann man nun den Weg durch ein solches Labyrinth finden? Gibt es eine Strategie mit der man immer raus kommt?
Wir müssen zwei Situationen unterscheiden. In der ersten Situation befinden wir uns an einem zufälligen Ort im Labyrinth und versuchen von hier aus einen Ausgang zu finden. Bei der anderen Situation befinden wir uns am Startpunkt des Labyrinthes. Ziel ist es nun, einen Weg durch das Labyrinth zu finden.

Situation zwei ist die deutlich angenehmere Sitution. Hier können wir mit der "rechten Hand Regel" den Weg aus dem Labyrinth finden.

Rechte-Hand-Regel: Wir betreten das Labyrinth und berühren die Wand zur rechten Seite mit unseren rechten Hand. Nun gehen wir durch das Labyrinth und behalten die ganze Zeit die Hand an der rechten Wand.

Bei einer Kreuzung würde man immer rechts abbiegen und bei einer Sackgasse würde man umkehren. In beiden Fällen sollte die Hand aber nicht die Wand verlassen. In unserem obigen Labyrinth würde man wie folgt durch das Labyrinth gehen. Der Weg ist in rot gekennzeichnet.

Bevor wir zur Erklärung kommen warum die rechte-Hand-Regel in diesem Fall immer funktioniert, wollen wir uns noch kurz den anderen Fall betrachten. Stell dir einen großen Raum vor, wo in der Mitte eine große Säule steht. Würden wir hier nun per Zufall unsere Hand anlegen, so würden wir ständig im Kreis gehen, da wir die Säule nicht verlassen würden. Die rechte-Hand-Regel bringt uns in diesem Fall nur bedingt weiter. Entweder wir finden den Ausgang, oder wir gehen die ganze Zeit in einem kleinen oder großen Kreis. Entkommen kann man zum Beispiel mit dem Algrotithmus von Tremaux. Eine schöne Beschreibung samt Beispiele findet sich im folgenden englischsprachigen Blog.

Kommen wir nun wieder zurück zu unserer Situation. Wieso entkommen wir immer mit der rechten-Hand-Regel? Dazu muss man sich die folgenden Punkte einmal in Ruhe klar machen.

• Ein Labyrinth hat nur endliche viele Wände! Die Anzahl sei $n < \infty$
• Folgst du immer der rechten-Hand-Regel, so kann man die einzelnen Wandteile durchnummerieren. 
• Das heißt dass jedes besuchte Wandstück einen eindeutigen Vorgänger und Nachfolger besitzt. Hierbei unterschseiden wir die Vorder- und Rückseite einer jeden Wand (im obigen Beispiel die Wandteile 7 und 8 beziehungsweise 11 und 12).

Was kann nun passieren? Entweder wir schaffen es durch das Labyrinth oder wir laufen im Kreis. Wir wollen nun annehmen, dass wir im Kreis laufen. Da wir nur $n$ Wandstücke besitzen und jedes Wandteil einen eindeutigen Nachfolger besitzt, sind wir spätestens nach $n$ Zügen wieder am Wandteil Nummer 1 angekommen. Hier kommen wir mit der rechten-Hand-Regel aber nur vom Startpunkt an. Das bedeutet dass wir vom Startpunkt - also von außen - kommen. Wir haben also irgendwann zuvor das Labyrinth verlassen. Demnach führt die rechte-Hand-Regel immer zum Erfolg.

Wir haben nun ein größeres Labyrinth für dich. Du kannst mit den obigen Pfeilen dich durch das Labyrinth bewegen, oder mittels der Tasten "awds" auf der Tastatur. Leider siehst du wie in einem echten Labyrinth nicht die ganze Karte des Labyrinths, sondern nur den kleinen Abschnitt in dem du dich befindest. Einfach auf Start klicken und versuchen das Labyrinth zu verlassen. Viel Glück und vor allem Spaß dabei ;)

Bemerkung : Sie können auch mittels der Tastatur sich durch das Labyrinth bewegen.

• a für 1 Schritt nach links
• w für 1 Schritt nach oben
• d für 1 Schritt nach rechts
• s für 1 Schritt nach unten