Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Messages: [ Previous | Next ]
 conesetter Posts: 115 Registered: 12/8/04
Re: finite maze solving algorithm
Posted: Dec 1, 2004 1:59 PM

michalchik@aol.com (Michael Michalchik) wrote in message news:&lt;20f4bb84.0411301849.18c69d1b@posting.google.com&gt;...
&gt; Kevin Saff &lt;news@kevin.saff.net&gt; wrote in message news:&lt;I808DL.GF2@news.boeing.com&gt;...
&gt; &gt; Michael Michalchik wrote:
&gt; &gt; &gt; I was wondering if anyone knows if all possible topologies of finite
&gt; &gt; &gt; 2d mazes can be solved by a finite algorithm. For example, we know
&gt; &gt; &gt; that all fully connected mazes can be solved by picking a wall and
&gt; &gt; &gt; exhaustively following it. Can a general solution work for all mazes
&gt; &gt; &gt; including the ones that are piecewise disconnected? If this is
&gt; &gt; &gt; possible, is the general solution a solved problem?
&gt;
A maze with n walls is homeomorphic to the n-times punctured plane.
So the method of cuts used by Cauchy to derive a simply-connected
domain can be applied. The cuts in this instance become barriers
joining the walls in some sequence, the last one getting a final
barrier going off to infinity. Then any two points in the maze can be
joined by a path which is homotopically unique.
The method of Tremaux noted in the Wikipedia Maze article may amount
to the same thing but with the barriers introduced on the run rather

Date Subject Author
11/29/04 Michael Michalchik
11/30/04 Kevin Saff
11/30/04 Keith A. Lewis
11/30/04 Kevin Saff
11/30/04 Michael Michalchik
12/1/04 Kevin Saff