Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: finite maze solving algorithm
Posted:
Dec 2, 2004 11:41 PM


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 >>depthfirst 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 depthfirst 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?
If you keep going in circles, then you are not doing a depthfirst search. Depthfirst search will systematically explore *any* maze in its entirety.
In depthfirstsearch, you keep traversing down previously untraversed paths until either you reach a place where all possible paths have already been traversed or you reach a dead end. In these situations, you "backtrack" along the path you've just traversed until reach a place where there is an unexplored corridor, and then you head down that corridor.
To find your way through an actual maze (i.e. not one written on paper), you need some way of marking passages. A 19'th century algorithm for traversing a maze is as follows. Bring along a pile of pennies to mark passages as you enter and leave junctions. During the algorithm, passages without pennies haven't been traversed yet, those with one penny have been traversed exactly once, and those with two pennies have been traversed and then backtracked along in the opposite direction.
Enter the maze. When you encounter a junction that you haven't seen before (no passageways with pennies), then choose a passage at random (remember to drop a penny in the passage you just left and in the passage you just entered). If you hit a dead end, turn around and go back. If you are walking down a passage for the first time and you encounter a junction you've seen before, then turn around and head back (remember to drop two pennies, one for entering the junction and one for leaving). If you are walking down a passage for the second time and encounter a junction, then take a new passage if there is one, otherwise take an old passage (marked with one penny). When you reach the solution, passages marked exactly once will indicate a direct path back to the start. If there is no solution, then you will end up back at the start with all passages marked twice.



