Trémaux 'method

from Wikipedia, the free encyclopedia

Trémaux's method is an algorithm thatenablesany maze or, more generally, labyrinthine path system to be passed without knowing a plan. The method works with markings and is suitable for practical application.

history

The algorithm was developed by Charles Pierre Trémaux (1859–1882), who trained as a telegraph engineer at the École polytechnique . After his untimely death, both the mathematician Gaston Tarry (1843–1913) and the author and mathematician Édouard Lucas (1842–1891) took up the idea. While Tarry tried to formulate a single "fundamental rule", Lucas reproduced Trémaux ' original, previously unpublished rules in a popular collection of mathematical games in an understandable form.

idea

While path systems that branch exclusively into dead ends can be solved easily with the help of the "right hand rule" ( wall follower method , "follow-the-wall method"), a system with a network-like structure was considered "inescapable" considered because it harbored the danger of endless "going in circles". Already Leonhard Euler had with the Seven Bridges of Königsberg dedicated to a related question. Trémaux succeeded in developing the only always applicable method which, in the worst case, managed to walk twice along the system of paths and excluded continual erring.

Working method

Possible branching situations
Example of Trémaux's method - animation (45 s)

requirements

The unknown route system is understood as a graph . This consists of edges and nodes (paths and squares; “squares” are simple junctions, crossings, but also any star stars). A path is marked when entering and exiting, for example by a line on the floor. Paths with two markings may no longer be used.

regulate

  • Always go a chosen path to the end.
    • If the path ends in a dead end, go back to the beginning. (You will then mark the entrance to the dead end with a second line and therefore not enter it again.)
    • If the path leads to a place, analyze the place.
      • If the place has never been entered, choose any route.
      • If the place is already known, analyze the path that led to the place.
        • If this is the first time you have walked this path, turn back! (You have discovered a loop and mark the last section you walked on with a second line at both ends to prevent you from walking in circles here in the future.)
        • However, if the path has already been taken, look at the entrances to the other paths. (You leave an area that you have searched completely and close it with a second line.)
          • If there is a path that has not yet been taken, choose this one. (Explore a new area of ​​the maze.)
          • Otherwise, choose a path that has only been trodden once . (There will only be one such path. This is your way back from an area that you have searched completely but in vain.)

When entering a square, it must not be forgotten to examine it for markings at the other junctions in order to decide whether it is an "unknown" branch.

literature

  • Gaston Tarry : The problem of the labyrinth . In: Nouvelles annales de mathématiques , Vol. 14, 1895, pp. 187-190.
  • Édouard Lucas : Récréations mathématiques [Volume 1]. 2nd Edition. Paris 1891, pp. 47-49 (in the 3rd section).