Maze-solving algorithm: Difference between revisions

Revision as of 07:02, 17 March 2021

Revision as of 07:02, 17 March 2021

Line 1:

[[File:Cyclope robot.jpg|thumb|right|Robot in a wooden maze]]

There are a number of different '''maze -solving algorithms''', that is, automated methods for the solving of [[maze]]s. The random mouse, wall follower, Pledge, and Trémaux's [[algorithm]]s are designed to be used inside the maze by a traveler with no prior knowledge of the maze, whereas the [[Cul-de-sac|dead-end]] filling and [[shortest path algorithm]]s 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 (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>{{youtube|k1tSK5V1pds|Maze to Tree}}</ref>

== Random mouse algorithm ==

Line 140:

==External links==

* [http://www.astrolog.org/labyrnth/algrithm.htm#solve Think Labyrinth: Maze algorithms] (details on these and other maze -solving algorithms)

* [http://www.cb.uu.se/~cris/blog/index.php/archives/277 MazeBlog: Solving mazes using image analysis]

* [https://www.youtube.com/watch?v=jhL8uELbVIM Video: Maze solving simulation]