There are a number of different maze solving algorithms, that is, automated
methods for the solving of mazes. The random mouse, wall follower, Pledge, and
Trémaux's algorithms are designed to be used inside the maze by a traveler with
no prior knowledge of the maze, whereas the dead-end filling and shortest path
algorithms are designed to be used by a person or computer program that can see
the whole maze at once. Mazes containing no loops are known as
"simply connected", or "perfect" mazes, and are equivalent to a tree in graph
theory. Thus many maze solving algorithms are closely related to graph
theory. Intuitively, if one pulled and stretched out the paths in the maze in
the proper way, the result could be made to resemble a tree.
Random mouse algorithm This is a trivial method that can be
implemented by a very unintelligent robot or perhaps a mouse. It is simply
to proceed following the current passage until a junction is reached, and then to
make a random decision about the next direction to follow. Although such a
method would always eventually find the right solution, this algorithm can be
extremely slow. Wall follower
The wall follower, the best-known rule for traversing mazes, is also known as
either the left-hand rule or the right-hand rule. If the maze is simply
connected, that is, all its walls are connected together or to the maze's
outer boundary, then by keeping one hand in contact with one wall of the maze the
solver is guaranteed not to get lost and will reach a different exit if there is
one; otherwise, he or she will return to the entrance having traversed every
corridor next to that connected section of walls at least once.
Another perspective into why wall following works is topological. If the
walls are connected, then they may be deformed into a loop or circle. Then
wall following reduces to walking around a circle from start to finish. To
further this idea, notice that by grouping together connected components
of the maze walls, the boundaries between these are precisely the
solutions, even if there is more than one solution.
If the maze is not simply connected, this method will not reach the goal.
Wall-following can be done in 3D or higher-dimensional mazes if its
higher-dimensional passages can be projected onto the 2D plane in a
deterministic manner. For example, if in a 3D maze "up" passages can be assumed
to lead northwest, and "down" passages can be assumed to lead southeast, then
standard wall following rules can apply. However, unlike in 2D, this requires
that the current orientation be known, to determine which direction is the
first on the left or right. Pledge algorithm
Disjoint mazes can still be solved with the wall follower method, if the
entrance and exit to the maze are on the outer walls of the maze. If however, the
solver starts inside the maze, it might be on a section disjoint from the exit,
and wall followers will continually go around their ring. The Pledge algorithm
can solve this problem. The Pledge algorithm, designed to
circumvent obstacles, requires an arbitrarily chosen direction to go
toward. When an obstacle is met, one hand is kept along the obstacle while
the angles turned are counted. When the solver is facing the original direction
again, and the angular sum of the turns made is 0, the solver leaves the
obstacle and continues moving in its original direction.
The hand is removed from the wall only when both "sum of turns made" and
"current heading" are at zero. This allows the algorithm to avoid traps
shaped like an upper case letter "G". Assuming the algorithm turns left at the
first wall, one gets turned around a full 360 degrees by the walls. An
algorithm that only keeps track of "current heading" leads into an infinite
loop as it leaves the lower rightmost wall heading left and runs into the
curved section on the left hand side again. The Pledge algorithm does not
leave the rightmost wall due to the "sum of turns made" not being zero at that
point. It follows the wall all the way around, finally leaving it heading left
outside and just underneath the letter shape.
This algorithm allows a person with a compass to find their way from any point
inside to an outer exit of any finite two-dimensional maze, regardless of the
initial position of the solver. However, this algorithm will not work in doing
the reverse, namely finding the way from an entrance on the outside of a maze to
some end goal within it. Trémaux's algorithm
Trémaux's algorithm, invented by Charles Pierre Trémaux, is an efficient method
to find the way out of a maze that requires drawing lines on the floor to
mark a path, and is guaranteed to work for all mazes that have well-defined
passages. A path is either unvisited, marked once or marked twice. Every time
a direction is chosen it is marked by drawing a line on the floor. In the
beginning a random direction is chosen. On arriving at a junction that has not
been visited before, pick a random direction that is not marked. When
arriving at a marked junction and if your current path is marked only once
then turn around and walk back. If this is not the case, pick the direction with
the fewest marks. When you finally reach the solution, paths marked exactly once
will indicate a direct way back to the start. If there is no exit, this method
will take you back to the start where all paths are marked twice. In this case
each path is walked down exactly twice, once in each direction. The resulting
walk is called a bidirectional double-tracing.
Essentially, this algorithm, which was discovered in the 19th century, has been
used about a hundred years later as depth-first search.
Dead-end filling Dead-end filling is an algorithm for
solving mazes that fills all dead ends, leaving only the correct ways unfilled.
It can be used for solving mazes on paper or with a computer program, but it
is not useful to a person inside an unknown maze since this method looks at
the entire maze at once. The method is to 1) find all of the dead-ends in the
maze, and then 2) "fill in" the path from each dead-end until the first
junction is met. Note that some passages won't become parts of dead end passages
until other dead ends are removed first. A video of dead-end filling in action
can be seen here: [1][2]. Dead-end filling cannot accidentally
"cut off" the start from the finish since each step of the process preserves
the topology of the maze. Furthermore, the process won't stop "too soon" since
the end result cannot contain any dead-ends. Thus if dead-end filling is
done on a perfect maze, then only the solution will remain. If it is done on a
partially braid maze, then every possible solution will remain but
nothing more. [3] Recursive algorithm
If given an omniscient view of the maze, a simple recursive algorithm can tell
one how to get to the end. The algorithm will be given a starting X and Y value.
If the X and Y values are not on a wall, the method will call itself with all
adjacent X and Y values, making sure that it did not already use those X and
Y values before. If the X and Y values are those of the end location, it will
save all the previous instances of the method as the correct path. Here is a
sample code in Java: Maze-Routing algorithm
The Maze-Routing algorithm is a low overhead method to find the way between
any two locations of the maze. The algorithm is initially proposed for Chip
Multiprocessors domain and guarantees to work for any grid-based maze. In
addition to finding paths between two location of the grid, the algorithm can
detect it when there is no path between the source and destination. Also, the
algorithm is to be used by an inside traveler with no prior knowledge of the
maze with fixed memory complexity regardless of the maze size; requiring 4
variables in total for finding the path and detecting the unreachable locations.
Nevertheless, the algorithm is not to find the shortest-path.
Maze-routing algorithm uses the notion of Manhattan Distance and relies on the
property of grids that the MD increments/decrements exactly by 1 when
moving from one location to any 4 neighboring locations. Here is the
pseudocode, without the capability to detect unreachable locations.
Shortest path algorithm When a maze has multiple solutions, the
solver may want to find the shortest path from start to finish. There are
several algorithms to find shortest paths, most of them coming from graph
theory. One possible algorithm finds the shortest path by implementing a
breadth-first search, while another, the A* algorithm, uses a heuristic
technique. The breadth-first search algorithm uses a queue to visit cells in
increasing distance order from the start until the finish is reached. Each
visited cell needs to keep track of its distance from the start or which
adjacent cell nearer to the start caused it to be added to the queue. When the
finish location is found, follow the path of cells backwards to the start,
which is the shortest path. The breadth-first search in its simplest
form has its limitations, like finding the shortest path in weighted graphs.
See also Mazes
Maze generation algorithm "Stop or My Dog Will Shoot", an episode
of The Simpsons in which Lisa uses Tremaux's algorithm
References External links
Think Labyrinth: Maze algorithms MazeBlog: Solving mazes using image
analysis Maze generation and solving Java applet
Video: Maze solving simulation