Content deleted Content added
Line 25:
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, which will be preferential. When an obstacle is met, one hand (say the right hand) is kept along the obstacle while the angles turned are counted (
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 [[degree (angle)|degree]]s 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 (note 360 [[degree (angle)|degree]]s is not equal to 0 [[degree (angle)|degree]]s). It follows the wall all the way around, finally leaving it heading left outside and just underneath the letter shape.
| |||