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:51 PM


lewis@SPYDER.MITRE.ORG (Keith A. Lewis) wrote in message news:<coihf4$bod$2@newslocal.mitre.org>... > 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 don't think that rule would be sufficient, How would it handle the case where a path deadended in a lopp. If you could never cross your path again you'd be stuck. Certainly there are lots of graphs that can not be traced if you don't allow, jumping, retracing or crossing? Maybe I am misunderstanding your suggestion.



