Showing posts with label maze solving. Show all posts
Showing posts with label maze solving. 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.