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 ]
 Michael Michalchik Posts: 89 Registered: 12/13/04
Re: finite maze solving algorithm
Posted: Nov 30, 2004 9:49 PM

Kevin Saff &lt;news@kevin.saff.net&gt; wrote in message news:&lt;I808DL.GF2@news.boeing.com&gt;...
&gt; Michael Michalchik wrote:
&gt; &gt; I was wondering if anyone knows if all possible topologies of finite
&gt; &gt; 2d mazes can be solved by a finite algorithm. For example, we know
&gt; &gt; that all fully connected mazes can be solved by picking a wall and
&gt; &gt; exhaustively following it. Can a general solution work for all mazes
&gt; &gt; including the ones that are piecewise disconnected? If this is
&gt; &gt; possible, is the general solution a solved problem?
&gt;
&gt; Interesting. How are you defining a maze, here? Usually, I think of a
&gt; maze as just a graph, which you can solve using something simple like
&gt; depth-first search, regardless of whether it is planar. It is probably
&gt; better to think in terms of connectedness of rooms than connectedness of
&gt; walls.
&gt;
&gt; (I hope I am not being ignorant here, but you seem to be using
&gt; "topology" and "piecewise disconnected" in strange ways. Obviously if
&gt; the topological space is disconnected, there will be no path possible
&gt; between points in different components - in the discrete topology, if
&gt; you're not there, you can't get there.)
&gt;
&gt; HTH

I am probably using those terms in an unusual way, being entirely a
layman. When I refer to piecewise disconnnected I mean the walls not
the paths. I understand that an unconnected path can not be traversed.
To look at this problem interms of paths (which I guess is the graph
theory approach you refer to) you would need to posit a set of graphs
that included loops, dead ends, routes that deadend in loops, and
various structures of loops nested and sharing common branches. I wish
usenet was friendlier to hand drawn diagrams embedded in text. That
would make explaining this a lot easier.

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
12/2/04 Glenn C. Rhoads
11/30/04 Michael Michalchik
12/1/04 conesetter
12/3/04 Steven Fuerst