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 4:02 PM


Keith A. Lewis wrote: > Kevin Saff <news@kevin.saff.net> writes in article <I808DL.GF2@news.boeing.com> dated Tue, 30 Nov 2004 18:22:32 GMT: > >>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. > > > The basic problem with a depthfirst search is the chance you'll get into a > loop going around and around a disconnected piece. The problem can be > avoided by making a rule to never cross your own path. > > Or is there something more that I'm missing? > > Keith Lewis klewis {at} mitre.org > The above may not (yet) represent the opinions of my employer.
I was under the impression that rule was part of DFS on arbitrary graphs, though it isn't needed for trees. Otherwise cycles are a problem.



