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 ]
 Kevin Saff Posts: 9 Registered: 2/4/05
Re: finite maze solving algorithm
Posted: Nov 30, 2004 1:22 PM

Michael Michalchik wrote:
&gt; I was wondering if anyone knows if all possible topologies of finite
&gt; 2d mazes can be solved by a finite algorithm. For example, we know
&gt; that all fully connected mazes can be solved by picking a wall and
&gt; exhaustively following it. Can a general solution work for all mazes
&gt; including the ones that are piecewise disconnected? If this is
&gt; possible, is the general solution a solved problem?

Interesting. How are you defining a maze, here? Usually, I think of a
maze as just a graph, which you can solve using something simple like
depth-first search, regardless of whether it is planar. It is probably
better to think in terms of connectedness of rooms than connectedness of
walls.

(I hope I am not being ignorant here, but you seem to be using
"topology" and "piecewise disconnected" in strange ways. Obviously if
the topological space is disconnected, there will be no path possible
between points in different components - in the discrete topology, if
you're not there, you can't get there.)

HTH
--
Kevin

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