Mathematische Annalen, 6 (1873), 29–30.
This short paper contains the first published algorithm for solving a maze. The author shows how to walk the maze so that every part of it is visited; the exit is then sure to be found.
{29}
Die Aufgabe, welche im Folgenden gelöst werden soll, und welche, wie ich glaube, bisher nicht behandelt ist, besteht darin, ein Verfahren anzugeben, wie man sich aus einem Labyrinthe heraus findet.
Ein Labyrinth ist ein zusammenhängender verschlungener Weg mit unübersteiglichen Rändern, der in einem geschlossenen Raume verläuft, aus dem er mit nur einer oder mit wenigen Mündungen herausführt. Da der Weg immer eine gewisse Breite behauptet, so kann ein Wegrand keinen Doppelpunkt besitzen, auch da nicht, wo sich zwei Wege kreuzen. Ein Wegrand kann daher, abgesehen vom Sinne, nur in einer bestimmten Weise durchlaufen werden; in keinem seiner Punkte findet eine mehrfache Möglichkeit des Weiterschreitens statt.
Ein Wegrand kann nun, wenn man ihn durchläuft, entweder zu einem schon eingenommenen Punkte zurückführen; dann muss er in die frühere Bahn übergehen, da stets nur eine Möglichkeit des Weiterschreitens vorhanden ist; er bildet in diesem Falle eine geschlossene Linie. Oder er führt nicht in sich selbst zurück und kann dann wegen seiner endlichen Länge nicht im Innern der Umgebung eingeschlossen sein, muss vielmehr nach aussen leiten. Dies wird bei jedem der beiden Sinne, in welchem man ihn durchlaufen kann, geschehen, so dass der Rand mit zwei Endigungen nach aussen trifft. Hat das Labyrinth nur einen Ausgang, so bilden die beiden Seiten desselben jene beiden Endigungen, und alle Randlinien ausser jener einen sind geschlossene. Daher die Regel: Man wähle beim Eintritt in das Labyrinth eine jener beiden nach aussen führenden Randlinien des Weges und verfolge sie nach innen; dieselbe muss auch wieder nach aussen führen.
In dem Falle, dass man sich im Innern des Labyrinthes befindet, ohne eine Randlinie von aussen verfolgt zu haben, kann man sich ebenfalls wieder herausfinden unter der Voraussetzung, dass man den Weg, den man zurücklegt nebst dem Sinne, in welchem man ihn beschreibt, im Gedächtniss zu behalten oder mit Marken zu bezeichnen vermag. Man verfolgt dabei zweckmässig die Axe des Weges statt seiner Randlinie. Jene Möglichkeit beruht auf der Wahrheit, dass so lange man den Ausgang noch nicht erreicht hat, ein bereits durchlaufenes Stück der Wegeaxe nothwendig von noch nicht beschriebenen Theilen derselben getroffen werden muss, weil sonst jenes Stück in sich abgeschlossen wäre und mit dem Eingangswege nicht zusammenhinge. Man markire sich daher den Weg, den man zurücklegt nebst dem Sinne, in welchem es geschieht. Sobald man auf einen schon markirten Weg stösst, kehre man um und durchschreite den schon beschriebenen Weg in umgekehrtem Sinne. Da man, wenn man nicht ablenkte, denselben hierbei in seiner ganzen Ausdehnung nochmals zurücklegen würde, so muss man nothwendig hierbei auf einen noch nicht markirten einmündenden Weg treffen, den man dann verfolge, bis man wieder auf einen markirten trifft. Hier kehre man wieder um und verfahre wie vorher. Es werden dadurch stets neue Wegtheile zu den beschriebenen zugefügt, so dass man nach einer endlichen Zeit das ganze Labyrinth durchwandern würde und so jedenfalls den Ausgang fände, wenn er nicht schon vorher erreicht worden wäre.
Carlsruhe, December 1871.