Content deleted Content added
→Trémaux's algorithm: clarify marks on paths vs marks on path-junction incidences |
move image up; doesn't seem specific to pledge algorithm, article needs a lead image, and its earlier placement was interfering with the Tremaux figure placement |
||
Line 1:
[[File:Cyclope robot.jpg|thumb|right|Robot in a wooden maze]]▼
There are a number of different '''maze solving [[algorithm]]s''', that is, automated methods for the solving of [[maze]]s. 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 [[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.
Line 20 ⟶ 21:
== Pledge algorithm ==
[[File:Pledge Algorithm.png|left|thumb| Left: Left-turn solver trapped <br /> Right: Pledge algorithm solution]]
▲[[File:Cyclope robot.jpg|thumb|right|Robot in a wooden maze]]
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 (named after [[Jon Pledge]] of [[Exeter]]) can solve this problem.<ref>{{citation|title=Turtle Geometry: the computer as a medium for exploring mathematics|last1=Abelson|last2=diSessa|year=1980}}</ref><ref>Seymour Papert, [ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-298.pdf "Uses of Technology to Enhance Education"], ''MIT Artificial Intelligence Memo No. 298'', June 1973</ref>
| |||