Maze-solving algorithm: Difference between revisions

Revision as of 17:08, 24 June 2011

Revision as of 05:36, 6 July 2011

Line 1:

There are a number of different '''maze solving [[algorithm]]s''', that is, automated methods for the solving of [[maze]]s. A few important maze solving algorithms are explained below. The random mouse, wall follower, pledgePledge, and Trémaux [[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 "standard", or "perfect" mazes, and are equivalent to a [[Tree (graph theory)| ''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<ref>http://www.youtube.com/watch?v=k1tSK5V1pds</ref>.