Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: finite maze solving algorithm
Posted:
Nov 30, 2004 9:49 PM


Kevin Saff <news@kevin.saff.net> wrote in message news:<I808DL.GF2@news.boeing.com>... > Michael Michalchik wrote: > > I was wondering if anyone knows if all possible topologies of finite > > 2d mazes can be solved by a finite algorithm. 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? > > 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 > depthfirst 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
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.



