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.independent

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: Nov 30, 2004 4:02 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


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
>>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 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.




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.