A fresco, Ariadne’s Thread, in the style of the ancient Greek myth of Theseus, who successfully traversed the labyrinth at Knossos and slew the Minotaur
A fresco, Ariadne’s Thread, in the style of the ancient Greek myth of Theseus, who successfully traversed the labyrinth at Knossos and slew the Minotaur · Source

In 1882, the French mathematician Édouard Lucas described a universal method for traversing mazes in Mathematical Recreations (Récréations mathématiques). Lucas himself, however, credited his compatriot Charles Pierre Trémaux with priority. This introduced the world to Trémaux’s algorithm, an elegant method for finding a path through any maze.

Lucas aptly called the method a “mathematical thread”, alluding to the legendary thread of Ariadne in Greek myth.

Lucas, É. Mathematical Recreations (1882), p. 42. Pages from Lucas’s Mathematical Recreations (1882). The complete book is available through the Source link.
Lucas, É. Mathematical Recreations (1882), p. 42. Pages from Lucas’s Mathematical Recreations (1882). The complete book is available through the Source link. · Source

With the development of computer science, Trémaux’s algorithm gained new life as a foundation of one of the basic graph-traversal methods, DFS (depth-first search), used in robotics, AI and navigation.

Maze-solving algorithms

Familiar methods include:

  • brute force, or exhaustive search;
  • Trémaux’s algorithm;
  • Random Mouse;
  • Wall-Follower, or the right-hand rule;
  • Dead-End Filling.

How does Trémaux’s method work?

Unlike the right-hand rule, which works only in simply connected, elementary mazes, Trémaux’s method applies to any layout, including loops, junctions and dead ends. Unlike random wandering, it always finds an exit if one exists.

Its core is systematic marking of every path traversed. Each corridor can be traversed no more than twice.

The algorithm’s rules:

  1. On entering a corridor, make one mark, such as a cross.
  2. At a junction:
    • If the path is unmarked, take it and make the first mark.
    • If it already has one mark, turn back and make a second: this is a dead end or a loop.
    • If every path is marked twice, return to the last point where you had a choice.
  3. The exit is found if you reach the goal, or traverse all paths completely and return to the start.
An animation demonstrating Trémaux’s algorithm
An animation demonstrating Trémaux’s algorithm · Source

Try it yourself

We invite you to study Trémaux’s algorithm and work through the maze below from entrance to exit, following the marking rules strictly.

Try traversing the maze using the procedure described above
Try traversing the maze using the procedure described above · Source

The myth of Ariadne’s thread

Marking paths recalls Ariadne’s thread in the Greek myth of Theseus, who successfully traversed the labyrinth at Knossos and slew the Minotaur. Let us briefly recall the story.

A fresco in the style of ancient Greek myths about Theseus and Ariadne’s thread
A fresco in the style of ancient Greek myths about Theseus and Ariadne’s thread · Source

The story of Ariadne’s thread still inspires us. According to the myth, King Minos of Crete imprisoned the Minotaur in a vast labyrinth. Every nine years, the Athenians had to send 14 young men and women to be devoured by the monster. Once, Theseus, son of the king of Athens, sailed with them. Minos’s daughter Ariadne fell in love with him and gave him a magical ball of thread she had received from Daedalus, the labyrinth’s architect.

Unwinding the thread, Theseus defeated the Minotaur and followed it back out, saving himself and all the others.

When Minos learned of Daedalus’s role in Theseus’s victory, he imprisoned the artist and his son Icarus in the labyrinth. Minos’s wife freed them. Making wings from feathers fastened with wax, Daedalus and Icarus flew away from the island. On the journey, Icarus climbed too high; the Sun melted the wax, and he fell into the sea, subsequently named the Icarian Sea.

Historical background

Charles Pierre Trémaux (1818–1895)
Charles Pierre Trémaux (1818–1895) · Source

Charles Pierre Trémaux (1818–1895) was a French engineer, architect, photographer and traveller, an author of scientific and ethnographic works, a graduate of the École Polytechnique and a specialist in navigation and geography.

The method bearing his name was later used by Claude Shannon, the founder of information theory, in his mechanical robot Theseus (1950), which could find its way out of any maze. The robot marked paths, avoided repetitions and ultimately selected the shortest route.

Trémaux’s algorithm is more than a problem-solving method: it bridges ancient mythology and modern computer science. It turned the chaos of a maze into a system and provided a foundation for artificial-intelligence algorithms. As Lucas remarked, “Trémaux’s genius was to turn chaotic wandering into a system.”