Labyrinthe und Irrgärten

Wenige Meter vor Alice hockte die Grinsekatze auf einem Baum. „Grinsepussi!“ redete sie die Katze an, ziemlich unsicher, weil sie nicht wußte, ob ihr der Name behagte. Indessen grinste die Katze noch breiter. „Na, das scheint ihr zu gefallen“, dachte Alice und fuhr fort: „Würdest du mir bitte sagen, welchen Weg ich einschlagen muß?“
„Das hängt in beträchtlichem Maße davon ab, wohin du gehen willst“, antwortete die Katze.
„Oh, das ist mir ziemlich gleichgültig“, sagte Alice.
„Dann ist es auch einerlei, welchen Weg du einschlägst“, meinte die Katze.
„Hauptsache, ich komme irgendwo hin“, ergänzte sich Alice.
„Das wirst du sicher, wenn du lange genug gehst“, sagte die Katze.

(Lewis Carroll, Alice im Wunderland)

1. Einleitung
2. Die Theseus-Methode: Am seidenen Faden
3. Die Linke-Hand-Methode: Immer an der Wand lang
4. Die Pledge-Methode: Dreh dich, kleiner Kreisel
5. Die Trémauxsche Methode: Mehr Kreide!
   1. Die Regeln nach Trémaux
   2. Die Regeln nach Tarry
6. Simulationsmethoden
   1. Die Methode nach Bellman: Wellenreiter
   2. Die Methode der Sackgassenfüllung: Alles gesperrt
   3. Die Shortest-Path-Methode: Mach es kurz!
7. Fazit
8. Implementierungen
   1. LabGen
   2. Der Linke-Hand-Bot
   3. LabConv
9. Literatur

Einleitung

Labyrinthe sind so alt wie die Mensch­heit: Man findet Ab­bil­dungen in der Bronze­zeit, bei den Hopi-Indianern, bei den Kretern (s.a. Geschichte des Minotauros), den Grie­chen, Römern u. a. Völkern. Auch als ritu­elle Tanz­form blieben sie er­halten. In der Frühzeit finden sich Laby­rinthe als Spiralen, vielleicht archa­ische Aus­drucks­formen der Gebär­mutter. Daher wird häufig kultur­geschicht­lich argumentiert, daß das, was wir heute unter einem Laby­rinth verstehen, in Wirk­lich­keit ein sog. Irrgarten sei. Ein Laby­rinth hingegen sei ein ein­zelner Weg, welcher mit einem großen Umweg und vielen Schleifen zur Mitte (dem Ziel) führe.

Auch die Kirche eignete sich die Ausdrucks­form des Labyrinthes an: So finden sich in einigen Kirchen als Einlege­arbeiten Labyrinthe. Ein sehr anschau­liches Beispiel dafür bietet die Kathedrale von Chartres aus dem 13. Jahrhundert, deren ein­ge­legtes Labyrinth dem des Mino­tauros ähnelt. Die Wege dieses rund 13 m im Durch­messer großen Umgangs­labyrinthes (elf konzen­trische Kreise) sind jeweils 34 cm breit, grau wie der umliegende Steinboden und voneinander durch schwarz-blaue Marmor­streifen getrennt; die Gesamt­länge des Weges beträgt 294 m. Sakrale Labyrinth-Intarsien finden sich zumeist zwischen Querschiff und Chor. Lt. den Über­lieferungen liefen die Pilger diese Laby­rinthe ab, bevor sie den Chor betraten. Die Laby­rinthe sind theologisch als Symbol für die Nicht-Gerad­linig­keit des Lebens, seine Stolpersteine und Umwege, die es bietet, zu verstehen. Wenn man das Labyrinth = Leben aber durchschritten hat, kommt man zum Chor = Heiligtum, zur Läuterung, zum Ziel.

Wohl jede Zeit hat sich des Laby­rinthes als Aus­drucks­form angenommen. Im Manie­rismus und im Barock wurde es aber eine richtige Mode, spe­ziell in der Garten­archi­tektur. Der Barock ist die Zeit der ver­winkel­ten Irrg­ärten. Die Neigung des Barocks zum Ver­spielten und zum Geo­me­tri­sieren der Gärten kam dieser Mode sehr entgegen. Die Wände solcher Gärten bestanden entweder aus über­manns­hohen, blick­dichten Hecken, die manch diplomatische Aktivität oder Vergnügung erleichterte, oder der Garten war zwei­dimensional lediglich auf dem Boden angedeutet mit ent­sprechenden Kies­wegen oder Gras­bepflanz­ungen.

Louis XIV ließ 1672-1677 in Versailles einen solchen Irrgarten erbauen. Die Wege waren von fünf Meter hohen Hecken begrenzt; über den Park verstreut fanden sich 333 bunt angemalte, gruppierte Skulpturen. Jede Gruppe erzählte eine Fabel von Äsop, und der jeweils vorge­stellte »Redefluß« einzelner Tiere wurde durch eine in die Figur eingebaute Fontäne symboli­siert. Insgesamt gab es 39 solcher Wasser­spiele.

Den Eingang des Parks bewachten zwei Statuen, Amor (C) und Äsop (B). Amor zeigt Äsop ein Garn­knäuel (Faden der Ariadne) als Hilfe beim Transit des Labyrinths. Äsop hebt mahnend den rechten Zeige­finger und hält mit der linken Hand Amor eine Schrift­rolle ent­gegen, wohl um zu warnen, daß man sich nicht nur auf einen Faden verlassen, sondern auch den Verstand einsetzen solle. Besucher regte es an, kurz inne­zuhalten und meta­phorisch über des eigenen Lebens Weg zu sinnieren.

Der Park lockte nach Fertig­stellung so viele Besucher an, auch ausländische, daß der Schriftsteller Perrault 1675 sogar einen Garten­führer schrieb, der Wasser­spiele und Fabeln erläu­terte. Nach über 100 Jahren war jedoch Schluß: Wegen der hohen Wartungs­kosten ließ Louis XVI den Garten 1778 durch ein Arboretum im englischen Stil ersetzen.

In der Neuzeit gibt es eine Renaissance der Irrgärten als künstlich angelegte Irrwege in den Maisfeldern – sehr zur Freude der Kinder und jung­gebliebener Erwachsener. Oft finden auch Hanf o.a. blickdichte Pflanzen Verwendung. Obgleich den Sommer­monaten vorbehalten, sind viele dieser Irrgärten durchaus anspruchsvoll: Einige Wege sind über einen Kilometer lang und benötigen eine Stunde, sofern man nicht mogelt.

Mit dem Aufkommen von Computerspielen und Labyrinth-Generatoren ergänzten computergenerierte Irrgärten bald auch Papier und Bleistift. Ebenfalls entwickelten sich computerbasierte Methoden zur Lösung eines Irrgartens. Im folgenden Abschnitt werden ohne Anspruch auf Vollständigkeit einige Methoden vorgestellt, um ein Ziel im Irrgarten zu finden, wobei das Ziel entweder einen Ort innerhalb des Gartens darstellt (z.B. ein Schatz), den Eingang oder einen separaten Ausgang. Zur Ill­ustration wird der Ausschnitt eines Irrgartens verwendet (s. Legende).

Die Methode nach Theseus: Am seidenen Faden

Die in der Sage vom Minotaurus beschriebene Methode ist einfach: Wickele ab Betreten des Irrgartens ein Garnknäuel ab. Folge dem Garnknäuel, um wieder zum Eingang zurückzufinden.

Die Methode ähnelt dem Versuch von Hänsel und Gretel im gleich­namigen Märchen der Gebr. Grimm, die auf dem Weg in den Wald ausgestreuten Brotkrumen wieder zu finden. Praktisch ist die Garnknäuel-Methode allerdings kaum zu verwenden, sei es, weil der Irrgarten zu komplex oder kein Garnknäuel zur Hand ist.

Die Linke-Hand-Methode: Immer an der Wand lang

Die Methode ist leicht zu merken, da sie nur aus einer Regel besteht: Durch­laufe ab Betre­ten den Irr­garten so, daß immer die linke Hand an einer Wand bleibt. Kommt man zu einer Abzwei­gung links, folgt man ihr also. Wenn man sich bereits bei Betre­ten des Irr­gartens an diese Regel hält, kommt man garan­tiert wieder heraus, wenn auch zumeist nicht auf dem kürzesten Weg, da u.U. der Irr­garten komplett abge­laufen wird. Oft durchläuft man viele Gänge zweimal, in jede Rich­tung einmal. Die Regel läßt sich spiegel­bild­lich auch für die rechte Hand verwenden (Rechte-Hand-Regel). Die Weg­längen beider Varian­ten können erheb­lich dif­ferieren. Entscheidet man sich für eine Hand, darf sie im Irr­garten nicht mehr gewech­selt werden.

Eine Einschränkung gilt es bei Irrgärten mit Inseln (autarke Zentral­strukturen, die nicht mit der Außenwand verbunden sind) zu beachten: Folgt man erst nach dem Verirren der Regel, kann man Glück haben (Abb. 1) oder Pech, falls sich die Hand gerade an einer solchen Insel befindet, denn dann läuft man nur im Kreis und erreicht nie den Ausgang (Abb. 2). Liegt hingegen das Ziel selbst in einer Insel, erreicht man es trotz konsequenter Anwendung der Regel ab Eingang des Irrgartens nicht, sondern findet nur zurück zum Ein- oder Ausgang.

Das Problem mit Inseln zu lösen versprechen nun die Methoden von Trémaux und Pledge:

Die Pledge-Methode: Dreh dich kleiner Kreisel

Benannt nach John Pledge aus Exeter in England, der im Alter von zwölf diese Strategie erfunden haben soll [Abelson und diSessa], erweitert die Pledge-Methode die Linke-Hand-Methode um die Fähigkeit, Inseln zu verlassen, statt sie als Trabant ewig zu umkreisen. Dazu bedarf es einer zweiten Regel, die den Absprung von einer Insel definiert.

Ein naiver Ansatz wäre, immer geradeaus zu laufen, bis man auf eine Wand trifft und ihr solange zu folgen, bis man die ursprüngliche Richtung erreicht hat; dann geht man wieder geradeaus bis zur nächsten Wand. Dies kann funktio­nieren (Abb. 3), muß es aber nicht, da man auch hier in eine Schleife gefangen werden kann (Abb. 4). Die Methode besteht abwechselnd aus geraden Strecken (in der Abb. als gestrichelte Linie dargestellt) und Wanderungen entlang der Wand (als durchgezogene Linie dargestellt).

Ein besserer Ansatz zählt die Drehungen, die man an Ecken vollführt und hält sie in einem Drehzähler fest. Eine Möglichkeit ist z.B., beginnend bei Null für jede rechtwinklige linke Drehung den Drehzähler um 1 zu erhöhen, für jede rechtwinklige rechte Drehung entsprechend um 1 zu erniedrigen. Erst wenn der Drehzähler wieder den Wert Null besitzt, geht man wieder geradeaus (Abb. 5). Für Wegesysteme, die auch spitze oder stumpfe Winkel aufweisen, empfiehlt sich eine genauere Drehungs­messung, z.B. mit einem Kompaß.

Methode von Trémaux: Mehr Kreide!

Die Ende des 19. Jh. vom frz. Fernmelde-Ingenieur Trémaux entwickelte Methode zielt wie die Pledge-Methode darauf ab, die Probleme der Linke-Hand-Methode mit Inseln zu beseitigen. Bei dieser durch Lucas 1882 beschriebenen Methode [Lucas] ist es wichtig, Anfangs- und Endpunkt eines jeden Weges zu markieren, um zu wissen, aus welchem Gang man gekommen ist und ob man schon einmal hier gewesen ist. Ein Sack Steine oder Kreide wird interessierten Probanden empfohlen. Diese Methode führt in jedem endlichen Irrgarten ans Ziel bzw. zum Ausgang, wenn auch nicht immer auf dem kürzesten Weg. Gibt es keinen Ausgang, werden alle Wege zweimal beschritten, bevor wieder der Eingang erreicht wird. Analog zum Königs­berger Brücken­problem läßt sich diese Methode auch graphen­theoretisch lösen. Das Verfahren von Trémaux funktioniert nur, wenn man an jedem Platz (Wegmündung, Kreuzung, Wegstern) weiß, welche der einmündenden Wege bereits wie oft durchlaufen wurden. Es bestehen mehrere Abwandelungen (Tarry 1895, Fraenkel 1971, Gal und Anderson 1990) der Trémauxschen Methode.

Regeln nach Trémaux:

1. Markiere jeden Weg bei Betreten und Verlassen mit einem Strich!
2. Geh neue Wege oder, falls es keine mehr gibt, die mit einem Strich!
3. Führt Dich jedoch ein neuer Weg zu einem bekannten Platz, kehr um!

Ein Weg mit zwei Markierungen am Eingang sollte gemäß Regel 2 also nicht mehr betreten werden: Zwei Markierungen sperren den Weg. Regel 2 verhindert somit, daß Wege mehr als zweimal durchlaufen werden. Eine Sackgasse ist nach ihrem Verlassen ebf. zweimal am Eingang markiert und somit gesperrt.

Regel 3 merzt die konzeptuelle Schwäche der Linke-Hand-Regel (wieder­holtes Im-Kreis-Laufen) aus. Sie erschließt durch Back­tracking weitere Wege im bisher besuchten Gebiet, bevor Wege zu neuen Arealen be­schritten werden. Somit wird sicher­gestellt, daß kein Weg ausgelassen wird.

In der oben abgebildeten Schrittfolge in Abb. 6 bis 8, die sich zwecks Ver­gleich­bar­keit an den Abbild­ungen vorgen. Methoden orientiert, liegt der Start inmitten des abgebildeten Areals, wobei bei gleich­wertigen Aus­gängen linke Wege bevorzugt werden. Das Areal ist nach Verlassen im Schritt 3 noch nicht gesperrt (der Eingang ist nur einmal markiert). Falls man später zum Areal zurück­kommen sollte, kann man es also noch ein­mal betre­ten. In der unten­stehenden Abb., in der der Start­punkt außer­halb des Areals liegt, ist jedoch das Areal nach seinem Ver­lassen gesperrt.

Abb. 9: Start von außen

Regeln nach Tarry:

1. Markiere jeden Weg beim Betreten mit einem Strich!
2. Geh einen neuen Weg oder, falls es keinen mehr gibt, den mit den wenigsten Strichen! Wege mit zwei Strichen lasse jedoch aus!
3. Markiere jeden Weg beim Verlassen mit drei Strichen, falls der erreichte Platz neu ist, anderenfalls mit zwei!

Tarrys Regeln [Tarry] ähnelt graphen­theoretisch somit der Tiefensuche.

Simulationsmethoden

Die folgenden Methoden jüngeren Datums sind nur am Modell oder in einer Simulation am Computer sinnvoll anwendbar.

Die Methode nach Bellman: Wellenreiter

Die 1957 publizierte Methode [Bellman] ist einfach, jedoch nur in einer Simulation verwendbar. Stark vereinfacht ausgedrückt lautet sie: Fülle den Irrgarten mit Wasser und folge der Flutwelle (das Wasser fließt am Ausgang ab). Leider ist sie, befindet man sich selbst in einem Irrgarten, nicht prakti­kabel.

Die Methode der Sackgassenfüllung: Alles gesperrt

Die Sackgassenfüllung [Fraenkel] ist nur in einem Computer­programm sinnvoll anwendbar. Hierzu werden alle Sackgassen gesucht und dann bis zur ersten anschließenden Kreuzung „gefüllt“ (gesperrt). Der verblei­bende, nicht gefüllte Weg stellt die Lösung dar.

Die Shortest-Path-Methode: Mach es kurz!

Auch die Shortest-Path-Methode [Moore] ist nur in einem Computer­programm sinnvoll anwendbar. Hierzu werden alle mit dem aktuellen Standort verbundenen Plätze in aufsteigender Entfernung gesucht, bis das Ziel gefunden ist. Die Distanz zwischen Start und jeweiligem Platz muß dazu gemerkt werden. Die Shortest-Path-Methode stellt graphen­theoretisch somit eine Breitensuche dar und garantiert, wie der Name schon impliziert, bei mehreren möglichen Strecken­verläufen zwischen Start und Ziel den kürzesten Weg.

Fazit

Etliche Suchstrategien sind nur in einem Computer­programm oder in einer Modellsicht sinnvoll nutzbar. Als praktisch nutzbar und sicher zur Orien­tierung in einem echten Irr­garten bzw. Höhlen­system sind die Linke-Hand-Methode, die Pledge-Methode und die Methode nach Trémaux nebst Varia­tionen zu nennen. Letztere versagt jedoch in Situationen, in denen man keine Markie­rungs­mög­lich­keiten hat oder es stock­dunkel ist, z.B. in Höhlen ohne Licht­quellen. Hier hilft einem noch die Methode nach Pledge weiter. In einer dunklen Höhle, die unmerk­liche Krüm­mungen oder nicht-orthogonale Ecken aufweist, wird ohne jegliches Licht und ohne Hilfs­mittel selbst dies schwierig und die Linke-Hand-Methode verbleibt als einzige Möglich­keit – mit der bekannten Ein­schrän­kung, daß sie einen nur dann wieder sicher heraus­bringt, sofern man sie bereits ab Betreten des Irr­gartens konsequent angewandt hat. Ist auch dies nicht der Fall, ist guter Rat teuer und muß man ver­suchen, andere Umgebungs­aspekte zu Rate ziehen (in Höhlen­systemen Luftzug und -feuchtig­keit, Geräusche, Steigung etc.). Auch Beten kann helfen, für Höhlen empfiehlt sich Ps. 130: De profundis clamavi ad te Domine.

Implementierungen

LabGen

LabGen ist ein OpenGL-Programm für Windows / Linux, das Irrgärten graphisch visualisiert oder ggf. auch generiert. Hier muß der Benutzer selbst seinen Weg finden! Am Ziel wird die benötigte Zeit ausgegeben. Eigene Irrgärten, Texturen und Klänge sind möglich.

Der Linke-Hand-Bot

Der LabBot ist ein noch aus der DOS-Ära stammendes Programm, das Irrgärten textbasiert visualisiert. Unter Windows ist es unter der Kommandozeile aufzurufen. Mit jedem Tastendruck des Benutzers wandert der Bot einen Schritt weiter.

LabConv

Wer mag, kann die von den Programmen benötigten Text-Labyrinth-Landkarten in ein Bildformat konvertieren.

Literatur

1. Wikipedia: The Labyrinth of Versailles, 2024
2. Abelson H, diSessa A: Turtle Geometry. MIT Press, Cambridge 1980, S. 191-198
3. Bellman R: Dynamic Programming, Princeton, 1957
4. Fraenkel AS: Economic Traversal of Labyrinths, in: Math. Magazine 43, 1973, S. 125-130
5. Lucas É, Récréations mathématiques, 2. éd., Gauthier-Villars, Paris, 1882-1883
6. Moore EF: The Shortest Path through a Maze, in: Proc. Int. Symp. Theory Switching II, Cambridge, 1959, S. 285-292
7. Tarry G: Le problème des labyrinthes, in: Nouv. Ann. Math. 14, 1895