Maze-solving algorithm: Difference between revisions

Revision as of 16:52, 7 March 2017

Revision as of 18:53, 7 March 2017

Line 21:

== Pledge algorithm ==

[[File:Pledge Algorithm.png|left|thumb| Left: Left-turn solver trapped <br /> Right: Pledge algorithm solution]]

Disjoint{{huh?|date=March 2017}} mazes can be solved with the wall follower method, so long as 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>

The Pledge algorithm, designed to circumvent obstacles, requires an arbitrarily chosen direction to go toward. When an obstacle is met, one hand (say the right 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.