Solution algorithms for mazes

from Wikipedia, the free encyclopedia

Solution algorithms for mazes describe methods with which a way out of a maze can be found automatically . There are algorithms that can help a person trapped in a maze out into the open without them knowing anything about the maze: the random route selection, the right-hand method, the pledge algorithm and the Trémaux algorithm . On the other hand, algorithms such as filling dead ends or finding the shortest way out require that the maze can be surveyed as a whole.

Mazes where you cannot go in circles are also called standard or perfect mazes . These are equivalent to a tree in graph theory . This becomes intuitively clear when one imagines that one is straightening the paths of a perfect maze. If you do this in the right way, the result looks very much like a tree. Therefore graph theory also plays a major role in the solution algorithms for mazes.

Heuristics

Random route

This trivial method can even be performed by a very simple robot . It simply consists of walking straight until you come to an intersection. There you randomly decide in which direction to go. Because this method may involve treading paths several times, it generally takes a long time to get to the exit. Nevertheless, one always reaches this.

Right-hand method

Solution with the right-hand rule
Maze with two solutions
Solutions to the above maze. It should be noted that the solutions correspond to the edge of the connected walls. For illustration purposes, the connected parts are marked with different colors.

The right-hand method is the best known rule of traversing a maze. You just put your right hand on a wall of the maze and keep in constant contact while walking through it (of course you can use your left hand instead of your right). If all the walls are contiguous or connected to the outside - that is, the maze is "simply contiguous" - the right-hand method guarantees that you either reach another exit or return to the entrance.

There is a simple topological reasoning why the right-hand method works as described: If the walls of the maze are connected, they can be deformed until they form a circle. In this case, the right-hand method leads to walking around the circle from start to finish. If you pursue this idea further and group the connected components of the maze, the boundaries between these components are exactly the solutions you are looking for (see adjacent picture).

However, the right-hand method can fail if the maze is not simply coherent. This is the case, for example, if you only put your hand on the wall inside the maze and this wall belongs to a pillar, for example. Then you walk in circles forever. In the worst (theoretical) case, the cross-section of the “column” could have a fractal shape. In this case one could not complete the circumference of the column because the circumference of this column would be infinitely large. So you would not even notice that you are involuntarily trying to circle the pillar - and of course you cannot leave the maze in this case either. (cf. among others Koch.Schneeflocke ). In practice, however, one cannot build fractal forms. Also, the right-hand method may be useless when trying to reach a specific goal within the maze.

The right-hand method can also be used in mazes with three or more dimensions . For this purpose, the intersections must be able to be projected into a two-dimensional plane in a well-defined manner . For example, in a three-dimensional maze, corridors leading “up” into “northwest” or corridors leading “down” into “southeast” can be applied using the right-hand rule. However - unlike in the two-dimensional case - the current orientation in the maze must always be known in order to be able to determine in which direction it is going "to the right" or "to the left".

Pledge algorithm

Robots in a little maze

If the entrance and exit are connected to the outer wall, you can use the right-hand rule to find your way through a maze that is not simply connected. However, if you start inside the maze, it can happen that with the right-hand rule you walk forever in a circle along a wall that is not connected to the exit. The Pledge algorithm (named after Jon Pledge from Exeter ) solves this problem (see "Turtle Geometry: the computer as a medium for exploring mathematics", Abelson & diSessa, 1980).

The pledge algorithm, designed to go around obstacles, requires a random target direction. If you hit an obstacle, you put one hand (for example always your right hand) on the obstacle and keep in contact on the way. You count the angles by which you turn away from the target direction when walking forward or towards the target direction. If you are aligned in the target direction again and the sum of the rotations made is zero, you release your hand from the obstacle and go straight ahead in the target direction.

Pledge algorithm when walking through a "G": counterclockwise turns are counted as positive, clockwise turns as negative. The numbers show the current status of the counted angles.

The hand is only removed from the wall of the maze if both conditions are met: “Sum of the rotations made equals zero” and “Current orientation equals target direction”. In this way, the algorithm avoids falling into traps that have the form of the capital letter "G". Assuming you enter the "G" from the right and turn left when you hit the left wall, you turn 360 degrees . If the algorithm provided for leaving the wall again, since the current direction again corresponds to the target direction from the beginning, one would be caught in an endless loop . Because if you leave the lower right side of the “G” and go to the left, you meet the curved left side of the “G” again and do a complete turn again. However, the pledge algorithm does not leave the lower right side of the “G”, since the “sum of the rotations made” is not zero, but 360 °. Instead, you continue to follow the wall, leave the inside of the “G” and take your hand off the wall when you are at the bottom of the “G” and look to the left again.

If it is a finite and fair two-dimensional maze, you can use the pledge algorithm and a compass to find the way to the open from any point in the maze. However, the algorithm does not work the other way around. So it is generally not possible with the pledge algorithm to find a target inside the maze from the entrance.

Trémaux algorithm

The Trémaux algorithm, invented by Charles Pierre Trémaux (1859–1882), uses markings, for example on the ground, and is an efficient method of finding the way out of a maze. The algorithm is guaranteed to work in all mazes that have well-defined passages.

A path is either unvisited, marked once or twice. In the beginning, any direction is chosen (if there is more than one). Then every walkway from intersection to intersection is marked with a line on the ground, for example. If you reach an intersection that you have never come to (recognizable by the fact that there are no markings on the ground), you choose any corridor to continue (and mark it as described). If, on the other hand, you reach a marked intersection and the corridor you are coming from is only marked once, you turn around and go back (and mark the corridor a second time). Otherwise you choose a course with as few markings as possible (and mark it as always). When you finally reach your destination, the direct route back to the start is marked with exactly one line.

If there is no exit, you will eventually reach the starting point again, and all the passages of the maze are marked with exactly two lines. In this case you have walked through each passage of the maze exactly twice, once in each direction. The path obtained is also referred to as "bidirectional double-tracing".

Gaston Tarry's algorithm

The French finance inspector Gaston Tarry (1843–1913) discovered the following algorithm for solving mazes in 1895:

  1. When you enter an aisle, mark the entrance with the word Stop . Never enter an aisle that is marked Stop .
  2. If you are entering an intersection for the first time (recognizable by the fact that there is no marking on any corridor), mark the corridor you just left with the word last .
  3. If there are corridors at an intersection that are not marked, choose any of them to continue. If there are no more unmarked corridors, enter the corridor marked last .

With this method the exit is guaranteed to be found. If the maze has no exit, every intersection is visited and every corridor is walked exactly twice (once in each direction). The algorithm then stops at the starting point. The Tarry method - unlike the pledge algorithm - is therefore also suitable for entering a maze from outside and finding a goal inside. The Trémaux algorithm is a special case of the Tarry algorithm.

Knowledge of the entire maze

Filling dead ends

If the maze can be surveyed as a whole, the solution can be found by filling dead ends. The algorithm can be used for mazes on paper or in a computer program , but not for people within an unknown maze. With this method, all dead ends are first sought and these are then “filled” up to the next intersection. The following videos illustrate this process:

Since each step preserves the topology of the maze, the destination cannot be accidentally cut off from the start. In addition, the algorithm does not stop “too early”, as the result cannot contain any dead ends. If, therefore, in a perfect maze - a maze in which one cannot go in circles - all the dead ends are filled, only the solution remains. In a maze, in which one can also go in circles, one receives all possible solutions.

Find the shortest way out

A maze with many solutions and no dead ends. The challenge here is to find the shortest possible route.

If there are several possible solutions, it is interesting to know the shortest start-finish route. This can be achieved, for example, with a breadth-first search . Using a queue , cells are sought at an ever greater distance from the starting point until the destination is reached. For each cell visited, it must be noted how far it is from the starting point (or from which neighboring cell the current cell was entered and therefore entered the queue). The shortest solution is obtained by following the visited cells from the target point back to the starting point.

Physical solutions

Analog circuit for a maze

If you pour water into the entrance of a horizontal maze, or if you blow air into the entrance of a maze with airtight corridor ceilings, then the strongest current indicates the shortest route to the exit. The exit must of course serve as an exit opening. There is no current in the dead ends. The currents of water or air can also be replaced by electrical currents in suitable analog circuits , as shown in the adjacent picture. Presumably, slime molds in mazes also work with an attractant gradient that works similar to a water current.

See also

Individual evidence

  1. ↑ Maze Transformed - Video on YouTube
  2. ^ Edouard Lucas: Récréations Mathématiques Volume I, 1882.
  3. ↑ A. Beutelsbacher: Castles in the air and fantasies.
  4. ↑ Maze Strategy: Dead End Filling - Video on YouTube
  5. ↑ Maze Solving algorithm - Video on YouTube
  6. ^ Maze Classification

Web links