Translated from “Le problème des labyrinthes”,
Nouvelles Annales de Mathématiques, ser. 3, 14 (1895), 187–190.
The author gives his algorithm for solving a maze, i.e. walking it so that every part is visited. Tarry’s algorithm finds all the walks that Tremaux’s algorithm finds, and is also somewhat simpler.
{187}
Any labyrinth can be traversed in a single movement, passing twice in opposite directions over each of its alleys, without any need to know the plan of it.
To solve this problem, it is enough to observe this single rule:
Do not turn back along the initial alley which led to a junction for the first time unless you cannot do otherwise.
We will begin with a few remarks.
At any time, before arriving at a junc-{188}tion or after leaving it it, any junction other than the starting point contains necessarily an even number of alleys traversed only once, and the number of those alleys followed in the entry direction is equal to the number of those followed in the exit direction. This is obvious, since the number of entries is equal to the number of exits, and an alley can be traversed at most twice and then in opposite directions. Consequently, at the time of an arrival at this junction, the number of the alleys traversed only once and in the entry direction is one more than the number of alleys traversed only once and in the exit direction. If there exists only one alley traversed only once, this must be the initial alley, and necessarily all the other alleys have been traversed twice in opposite directions. Thus you cannot be stopped at this junction, and you will only be forced to turn back along the initial alley in the event that all the other alleys have been traversed twice.
Thus, while following the rule, you can only be stopped only at the starting point; and you take the initial alley of a junction for the second time only after traversing all the other alleys of the junction.
Let us now consider the junction where the whole journey started. At the time of an arrival at this junction, the number of alleys traversed only once and in the entry direction is equal to the number of alleys traversed only once and in the exit direction. Consequently, one can only be stopped if there exist neither unexplored alleys, nor alleys traversed only once.
Therefore, at the time of the forced halt at the starting junction, all the alleys of this junction have been traversed twice.
To proceed: let A, B, C, D, …, Z be the starting junction {189} and the other junctions, labelled in the order in which they were discovered during the course of exploration.
If you have faithfully applied the one and only rule, all the alleys leading to the junctions B, C, D, …, Z have necessarily been traversed twice in opposite directions, like the the alleys of the starting junction A.
Indeed, since the initial alley AB of junction B, which ends at junction A, has been traversed twice in opposite directions, all the alleys of junction B have been traversed twice in opposite directions. In the same way, all the alleys of the junction C have been traversed twice, since its initial alley BC (or AC if AB is a dead end), which leads to the junction B (or A) has been traversed twice. Finally, any junction T, whose initial alley necessarily ends in a preceding junction (be it A, B, …, or S), has been fully explored, since its initial alley has been traversed twice. This is what had to be proved.
Let us suppose that on taking an alley for the first time you deposit at the entry two marks and the exit one or three marks, according as this alley emerges in a junction already visited or a new junction; and that on taking an alley where there is one mark at the entry, so that you are now following a second time and in the opposite direction, you are content to add a second mark to the entry. On arriving at a junction you will always be able to distinguish the new alleys which do not have any mark, the initial alley which has three marks, and the other alleys traversed only once and in the entry direction which have a single mark.
The one and only rule can then be stated in the following way:
On arriving at a junction, take as you please either an {190} alley which has no mark or an alley which has a single mark, and if neither of these exists take the alley which has three marks.
By following this practical rule, a traveller lost in a labyrinth or in the catacombs will inevitably find the entry before traversing all the alleys and without passing more than twice through the same alley.
Which shows that a labyrinth is never inextricable, and that the best Ariadne’s thread is the thread of reason.
Remark. – The general rule allows you always to turn back on arriving at an already explored junction by a new path. If this is made obligatory, then on arriving at a junction by a path followed before you will find a single alley that has been traversed only once, namely the initial alley, and you will not be allowed to take this alley unless there is no path that has not been traversed. It is clear that in this case it becomes pointless to distinguish by a special mark the exit point from an initial alley. This particular solution was found by M. Trémaux (see Récréations Mathématiques by E. Lucas).