I recently had the chance to employ this one, but didn’t manage to: it turns out that four three-to-six-year-olds are not especially interested in putting down markers and following rules, they just want to run around the maize maze and say “maize maze” and make “amazing” jokes ((That last one might be more the parents. OK, the me.))

What is Tremaux’s algorithm?

Tremaux’s algorithm is a method for finding your way out of a maze by putting down markers to show where you’ve been. Assuming the maze has well-defined passages and junctions, here’s what you do:

  • Every time you enter or leave a passage, you put down a marker.
  • Every time you enter a junction:
    • If all of the passages are unmarked, take one of them (it doesn’t matter which)
    • Otherwise, if the passage you’ve just emerged from only has one mark, go back along it (putting a second marker with the one you’ve just put down).
    • If the path you’ve emerged from has two marks, go along whichever other path has the fewest marks on it (it doesn’t matter which).

This algorithm guarantees finding an exit if it exists; a path (not necessarily the shortest path) from the starting point to the exit can be found by following all of the passage entrances and exits with a single marker.

Why is it important?

It gets you out of mazes. Next!

Oh, all right. It’s a particular case of a depth-first search which has applications in graph theory - particularly in finding spanning trees of graphs, infinite or otherwise.

Who was Charles Pierre Tremaux?

Charles Pierre Tremaux (1859-1882) is another hard-to-track down character from the history of maths. He’s referred to as ‘an author’, possibly from Charrecey in Burgundy. Edouard Lucas refers to him as an ex-student of the Ecole Polytechnique and a telegraph engineer.

As always, if you know more or better, I’d love to hear about it!