John Pledge was a 12 year-old Exeter,
England school student when he invented the maze-solving algorithm that bears
his name.
His algorithm collects local
information by adding turns to the left as positive numbers and turns to the
right as negative values to a variable called Total Turning.
Total Turning is initially set to zero. The robot then moves forward
until it strikes a barrier. It turns left, adding the angle measure of the turn
to Total Turning and then executes the rest of the algorithm until Total
Turning equals zero degrees (not 360º) that indicates the robot has navigated
around the barrier. The algorithm resets Total Turning to zero, and the robot
again moves forward until it strikes another barrier. And so on.
A
complete discussion of the Pledge algorithm can be found in the book Turtle Geometry, by Harold Abelson and Andrea A. diSessa published by the MIT Press
in 1980.
In
the book, I was amazed to learn that if a robot following the Pledge algorithm
can escape the interior of a capital letter G, then the robot can escape from
any of the mazes commonly seen in books.
Years
ago (1986) I implemented the Pledge algorithm in Terrapin Logo. Searching
Scratch for Pledge, I found a project ( http://scratch.mit.edu/projects/763827/) with all of the variable names written in a foreign
language. I remixed the project by decoding the variable names into English. I discovered
that my Logo algorithm and the remixed algorithm used the same technique of
‘holding the right hand on the wall of the maze’.
I have shared, on the Scratch website, three Pledge Algorithm projects. The
first is the Letter G-Maze Test project that tests the Scratch version of the
Pledge algorithm.
You
can view and download this project by clicking on the following link.
http://scratch.mit.edu/projects/2814655/
The
second Scratch project, Pledge Algorithm Maze, pays homage to John Pledge by
creating a maze made of the capital letters of his last name. The algorithm
from the Letter G project was simply copied into this project. It was drawing
the maze that took time.
You
can view and download this project by clicking on this link.
http://scratch.mit.edu/projects/2814737/
The
third project, The Pledge Algorithm - Large Maze project, adds a much more
complicated maze than the first two projects. But again, exactly the same
Pledge algorithm code was copied into this project. The little robot will now
navigate through the maze from any point within the maze.
You can also view and download this
project by clicking on this link.
http://scratch.mit.edu/projects/2823071/
I
have written a written a document that describes, in detail, the Pledge Algorithm.
You can obtain a copy of this document, free, by sending an email request to