Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: finite maze solving algorithm
Replies: 9   Last Post: Dec 3, 2004 7:09 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Kevin Saff

Posts: 9
Registered: 2/4/05
Re: finite maze solving algorithm
Posted: Dec 1, 2004 10:02 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


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
>>>depth-first 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 depth-first 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




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.