Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: finite maze solving algorithm
Replies: 9   Last Post: Dec 3, 2004 7:09 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Steven Fuerst

Posts: 2
Registered: 12/13/04
Re: finite maze solving algorithm
Posted: Dec 3, 2004 7:09 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


michalchik@aol.com (Michael Michalchik) wrote in message news:<20f4bb84.0411291905.29b97a1b@posting.google.com>...
> I was wondering if anyone knows if all possible topologies of finite
> 2d mazes can be solved by a finite algorithm.

Yes, they can.

> For example, we know
> that all fully connected mazes can be solved by picking a wall and
> exhaustively following it. Can a general solution work for all mazes
> including the ones that are piecewise disconnected? If this is
> possible, is the general solution a solved problem?

Yes it is. Look for the "Pledge Algorithm". It is well-described in
the book "Turtle Geometry", including a proof for how it solves every
finite maze.

The algorithm works by keeping track of the total amount of turning
you do as you move throughout the maze. Using this purely local
information (you don't need breadcrumbs, or to mark walls etc.) it is
possible to escape.

It is rather simple:

1. Initialize a counter to zero, and define an arbitrary direction to
be 'north'.

2. Move straight north until an obstacle is met.

3. Turn left and follow the obstacle. Keep track of 'total turning'
and increment the counter by +1 for every full 360 degree turn
clockwise, and -1 for every full 360 turn anti-clockwise.

4. Leave the obstacle when it is possible to move straight north and
the counter reads zero. Goto step 2.


Steven




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.