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 2:25 PM


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.



