Christian Wiener, “On a problem in the geometry of position”

Translated from “Ueber eine Aufgabe aus der Geometria situs”,
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.

On a problem in the geometry of position.

By Christian Wiener in Carlsruhe.

The problem which is to be solved below, and which I believe has not been treated until now, is to specify a procedure for finding one’s way out of a labyrinth.

A labyrinth is a connected winding path with uncrossable edges, running in an enclosed space from which it exits by one or several openings. Since the path always maintains a certain width, a path edge cannot have a double point, not even where two paths cross. A path edge can therefore, apart from the direction of travel, be traversed only in one fixed way; at none of its points is there any choice of the way to continue.

Now, when a path edge is traversed, it can either (1) lead back to a point already visited; it must then proceed along the route followed previously, for there is only ever one possible way of continuing; in this case it forms a closed line. Or (2) it does not close back on itself and, having a finite length, cannot then be restricted to the interior of the enclosure, but must rather lead to the outside. This will occur for each of the two ways in which it can be traversed, so that the edge meets the outside at two endpoints. If the labyrinth has only one exit, then the two sides of this form those two endpoints, and all path edges other than this one are closed. Hence the rule: on entering the labyrinth choose one of those two path edges that lead to the outside, and follow it inwards; the same edge must lead back out again.

In the event that you are inside the labyrinth without having followed a path edge from the outside, it is still possible find your way out, provided that you are able to memorize or record by markers the path already covered plus the direction of travel. For this purpose one follows the axis of the path instead of the path edge. This possibilty is based on the fact that, as long as the exit has not been reached, any piece of the path axis already covered must necessarily join up with parts not yet recorded, because otherwise that piece would be self-contained, and would not be connected with the entrance. Mark therefore the path you have covered, plus the direction in which this was done. As soon as you come across an already marked path, turn back and traverse the already recorded path in the reverse direction. Since, if you did not turn aside, you would in this way go over the latter again for its entire length, you must necessarily at some point come across a junction with a path that is not yet marked, which you then follow, until you again come across a marked path. Here turn back again and proceed as before. In this way new parts of the path are constantly being added to the ones already recorded, so that after a finite time you will have travelled through the whole labyrinth and thus found the exit in the end, if it has not already been reached before.