Re: finite maze solving algorithm

From: Michael Michalchik (michalchik_at_aol.com)
Date: 12/01/04 

Date: 30 Nov 2004 18:49:16 -0800

Kevin Saff <news@kevin.saff.net> wrote in message news:<I808DL.GF2@news.boeing.com>...
> 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.
>
> (I hope I am not being ignorant here, but you seem to be using
> "topology" and "piecewise disconnected" in strange ways. Obviously if
> the topological space is disconnected, there will be no path possible
> between points in different components - in the discrete topology, if
> you're not there, you can't get there.)
>
> HTH

I am probably using those terms in an unusual way, being entirely a
layman. When I refer to piecewise disconnnected I mean the walls not
the paths. I understand that an unconnected path can not be traversed.
To look at this problem interms of paths (which I guess is the graph
theory approach you refer to) you would need to posit a set of graphs
that included loops, dead ends, routes that deadend in loops, and
various structures of loops nested and sharing common branches. I wish
usenet was friendlier to hand drawn diagrams embedded in text. That
would make explaining this a lot easier.

Relevant Pages

  • Re: finite maze solving algorithm
    ... > 2d mazes can be solved by a finite algorithm. ... better to think in terms of connectedness of rooms than connectedness of ... "topology" and "piecewise disconnected" in strange ways. ...
    (sci.math)
  • Re: finite maze solving algorithm
    ... >> 2d mazes can be solved by a finite algorithm. ... >depth-first search, regardless of whether it is planar. ... >better to think in terms of connectedness of rooms than connectedness of ...
    (sci.math)
  • finite maze solving algorithm
    ... I was wondering if anyone knows if all possible topologies of finite ... 2d mazes can be solved by a finite algorithm. ... Can a general solution work for all mazes ...
    (sci.math)