Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 Kevin Saff Posts: 9 Registered: 2/4/05
Re: finite maze solving algorithm
Posted: Dec 1, 2004 10:02 AM

Michael Michalchik wrote:
&gt; lewis@SPYDER.MITRE.ORG (Keith A. Lewis) wrote in message news:&lt;coihf4\$bod\$2@newslocal.mitre.org&gt;...
&gt;
&gt;&gt;Kevin Saff &lt;news@kevin.saff.net&gt; writes in article &lt;I808DL.GF2@news.boeing.com&gt; dated Tue, 30 Nov 2004 18:22:32 GMT:
&gt;&gt;
&gt;&gt;&gt;Michael Michalchik wrote:
&gt;&gt;&gt;
&gt;&gt;&gt;&gt;I was wondering if anyone knows if all possible topologies of finite
&gt;&gt;&gt;&gt;2d mazes can be solved by a finite algorithm. For example, we know
&gt;&gt;&gt;&gt;that all fully connected mazes can be solved by picking a wall and
&gt;&gt;&gt;&gt;exhaustively following it. Can a general solution work for all mazes
&gt;&gt;&gt;&gt;including the ones that are piecewise disconnected? If this is
&gt;&gt;&gt;&gt;possible, is the general solution a solved problem?
&gt;&gt;&gt;
&gt;&gt;&gt;Interesting. How are you defining a maze, here? Usually, I think of a
&gt;&gt;&gt;maze as just a graph, which you can solve using something simple like
&gt;&gt;&gt;depth-first search, regardless of whether it is planar. It is probably
&gt;&gt;&gt;better to think in terms of connectedness of rooms than connectedness of
&gt;&gt;&gt;walls.
&gt;&gt;
&gt;&gt;The basic problem with a depth-first search is the chance you'll get into a
&gt;&gt;loop going around and around a disconnected piece. The problem can be
&gt;&gt;avoided by making a rule to never cross your own path.
&gt;&gt;
&gt;&gt;Or is there something more that I'm missing?
&gt;&gt;
&gt;&gt;--Keith Lewis klewis {at} mitre.org
&gt;&gt;The above may not (yet) represent the opinions of my employer.
&gt;
&gt;
&gt; I don't think that rule would be sufficient, How would it handle the
&gt; case where a path deadended in a lopp. If you could never cross your
&gt; path again you'd be stuck. Certainly there are lots of graphs that can
&gt; not be traced if you don't allow, jumping, retracing or crossing?
&gt; 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,
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

Date Subject Author
11/29/04 Michael Michalchik
11/30/04 Kevin Saff
11/30/04 Keith A. Lewis
11/30/04 Kevin Saff
11/30/04 Michael Michalchik
12/1/04 Kevin Saff