The Math Forum

Search All of the Math Forum:

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

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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 ]
Michael Michalchik

Posts: 89
Registered: 12/13/04
Re: finite maze solving algorithm
Posted: Nov 30, 2004 9:51 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

lewis@SPYDER.MITRE.ORG (Keith A. Lewis) wrote in message news:<coihf4$bod$>...
> Kevin Saff <> writes in article <> 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}
> 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.

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

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.