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:
Dec 1, 2004 10:02 AM


Michael Michalchik wrote: > 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.
OK, in layman's terms, assume you have a long rope and a loaf of bread. Tie one end of the rope to a hitch outside, and keep it reasonably taut. Whenever you enter a new room, drop a bread crumb. Now, determine which adjacent rooms have bread in them. If all adjacent rooms have bread, follow the rope back to the last room. If any of them have no bread, go in that room, drop a crumb, check the adjacent rooms for crumbs, and so on. You are then guaranteed to visit every room in the maze, assuming the rooms are all connected somehow.
HTH  Kevin



