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}
Tout labyrinthe peut être parcouru en une seule course, en passant deux fois en sens contraire par chacune des allées, sans qu’il soit nécessaire d’en connaître le plan.
Pour résoudre ce problème, il suffit d’observer cette règle unique:
Ne reprendre l’allée initiale qui a conduit à un carrefour pour la première fois que lorsqu’on ne peut pas faire autrement.
Nous ferons d’abord quelques remarques.
A un moment quelconque, avant d’arriver a un car-{188}refour ou après l’avoir quitté, tout carrefour autre que celui du point de départ contient nécessairement un nombre pair d’allées parcourues une seule fois, et le nombre de ces allées suivies dans le sens de l’arrivée est égal au nombre de celles suivies dans le sens inverse de la sortie. Cela est évident, puisque le nombre des entrées est égal à celui des sorties, et qu’une allée peut être parcourue deux fois au plus en sens contraire. Par suite, au moment d’une arrivée dans ce carrefour, le nombre des allées parcourues une seule fois et dans le sens de l’arrivée surpasse sur l’unité le nombre des allées parcourues une seule fois et dans le sens de la sortie. S’il n’existe qu’une allée parcourue une seule fois, ce ne peut être que l’allée initiale, et nécessairement toutes les autres allées ont été parcourues deux fois en sens contraire. On ne peut donc être arrêté à ce carrefour, et l’on sera forcé de reprendre l’allée initiale dans le cas seulement où toutes les autres allées auront été parcourues deux fois.
Ainsi, en suivant la règle, on ne peut être arrêté qu’au point de départ, et l’on ne reprend l’allée initiale d’un carrefour qu’après avoir parcouru deux fois toutes les autres allées du carrefour.
Considérons maintenant le carrefour du point de départ. Au moment d’une arrivée à ce carrefour, le nombre des allées parcourues une seule fois et dans le sens de l’arrivée est égal au nombre des allées parcourues une seule fois et dans le sens de la sortie. Par conséquent, on ne peut être arrêté que s’il n’existe ni les allées inexplorées, ni allées parcourues une seule fois.
Donc, au moment de l’arrêt forcé au carrefour du départ, toutes les allées de ce carrefour ont été parcourues deux fois.
Cela posé, soient A, B, C, D, …, Z le carrefour du {189} départ et les autres carrefours, désignés dans l’ordre de leurs découvertes successives pendant l’exploration.
Si l’on a exécuté rigoureusement l’application de la règle unique, toutes les allées aboutissant au carrefours B, C, D, …, Z ont été parcourues nécessairement deux fois en sens contraires, comme les allées du carrefour de départ A.
En effet, l’allée initiale AB du carrefour B, qui aboutit au carrefour A, ayant été parcourue deux fois en sens contraires, toutes les allées du carrefour B ont été parcourues deux fois en sens contraires. De même, toutes les allées du carrefour C ont été parcourues deux fois, puisque son allée initiale BC (ou AC si AB est une impasse), qui aboutit au carrefour B (ou A) a été parcourue deux fois. Enfin, un carrefour quelconque T, dont l’allée initiale aboutit nécessairement à un carrefour précédent (ou A, ou B, …, ou S), a été entièrement exploré, puisque son allée initiale a été parcourue deux fois. C’est ce qu’il fallait démontrer.
Supposons qu’en prenant une allée pour la première fois on dépose a l’entrée deux marques et à la sortie une ou trois marques, suivant que cette allée débouche dans une carrefour déjà visité ou dans un carrefour nouveau, et qu’en prenant une allée où se trouve une marque à l’entrée, et la suivant par conséquent une seconde fois en sens contraire, on se contente d’ajouter une deuxième marque a l’entrée. A l’arrivée dans un carrefour on saura toujours distinguer les allées nouvelles qui n’ont aucune marque, l’allée initiale qui a trois marques et les autres allées parcourues une seule fois et dans le sens de l’arrivée qui ont une seule marque.
La règle unique s’énoncera alors sous cette forme:
En arrivant à un carrefour, prendre à volonté une {190} allée qui n’a pas de marque ou bien une allée qui a une seule marque, et s’il n’en existe pas prendre l’allée qui a trois marques.
En suivant cette marche pratique, un voyageur perdu dans un labyrinthe ou dans des catacombes, retrouvera forcément l’entrée avant d’avoir parcouru toutes les allées et sans passer plus de deux fois par la même allée.
Ce qui démontre qu’un labyrinthe n’est jamais inextricable, et que le meilleur fil d’Ariane est le fil de raisonnement.
Remarque. – La règle générale permet de toujours rétrograder en arrivant à un carrefour déjà exploré par une voie nouvelle. Si l’on s’impose cette obligation, quand on arrivera à un carrefour par une voie antérieurement suivie, on ne trouvera qu’une allée parcourue une seule fois, l’allée initiale, et il ne sera permis de prendre cette allée qu’à défaut de voie qui n’aurait pas été parcourue. Il est clair que, dans ce cas, il devient inutile de distinguer par une marque spéciale le débouché d’une allée initiale. Cette solution particulière a été trouvée par M. Trémaux (voir les Récréations mathématiques de E. Lucas).