Showing posts with label algorithm Scratch. Show all posts
Showing posts with label algorithm Scratch. Show all posts

## Monday, October 14, 2013

### The Pledge Maze-solving Algorithm

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