Date: Dec 2, 2004 11:41 PM Author: Glenn C. Rhoads Subject: Re: finite maze solving algorithm

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

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

If you keep going in circles, then you are not doing a depth-first

search. Depth-first search will systematically explore *any* maze

in its entirety.

In depth-first-search, 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.