Newsgroups: comp.ai
Path: cantaloupe.srv.cs.cmu.edu!bb3.andrew.cmu.edu!newsfeed.pitt.edu!portc02.blue.aol.com!howland.erols.net!newsfeed.internetmci.com!btnet!netcom.net.uk!netcom.com!xie
From: xie@netcom.com (Elf)
Subject: Maze solving algorithms?
Message-ID: <xieE1EAxB.1pJ@netcom.com>
Organization: NETCOM On-line Communication Services (408 261-4700 guest)
X-Newsreader: TIN [version 1.2 PL1]
Date: Sun, 24 Nov 1996 22:10:23 GMT
Lines: 115
Sender: xie@netcom9.netcom.com

Many of the programs I have seen attempt to solve mazes by using
the following methodology:

a:
   if have reached the exit
      quit
   If can move left and have not been there before 
      move left then goto a:
   if can move forward and have not been there before
      move forward then goto a:
   if can move right and have not been there before
      more right then goto a:
   otherwise
      retreat to a branch that has not been checked yet then goto a:

There are three assumptions about the searcher being made here:

1 - it is so blind that has to all the way to the end of a straight,
    deadend corridor before it can tell that is it in fact a deadend.
2 - it has some intrinsic ability to tell whether it has explored
    a particular section of corridor before.
3 - it is not otherwise equiped to be a maze explorer

---

Now consider the following scenario:

You (alone) are planning to go explore a manmade maze this weekend.
Let the maze have the following properties.

- there are two external openings into the maze, either may
  be chosen as a starting point to find the other
- the corridors are made of 8 foot high sewage pipe
- there is no internal lighting
- there is an operational ventillation system
- the corridors do not necessarilly run right next to eachother
- the corridors run in straight lines

Your basic, boring maze.

Now, most likely you are not planning to wander around in the dark, 
following the left wall and hoping that there are not circular 
corridors.  What would you take with you?

- a flash light or lantern?
- chalk to mark the corridors?
- global positioning system with laptop computer?
- sonar?
- lunch?
- ?

How would you plan to solve this maze?

Now your algorithm for solving the maze might be:

next_branch:

   if can see a branch down the left corridor and have not been there before
      go left and to the next_branch
   if can see a branch straight ahead and have not been there before
      go straight and to the next_branch
   if can see a branch down the right corridor and have not been there 
         before
      go right and to the next_branch
   otherwise
      retreat to the last branch containing unexplored corridors with
   visible branches and go to next_branch:

Ah, now you should be able to complete the maze much quicker because you 
did not have to travel every last foot of every deadend.

Speed is the issue, what is the fastest way to "crack the maze"?

---

Next scenario:

You (and 20 friends) are planning to go see how quickly you can solve
a maze.  The characteristics of the maze are the same as before.

What do you take with you?

- flashlights?
- walkie talkies?
- multiple colors of chalk for marking corridors?

How would you solve this maze?  What would your algorithm be?
Would you send people in both entrances?  What would their
individual instructions be?

---

Next scenario:

Given any number of friends and whatever (non-destructive) equipment you
can carry... to help you find the _fastest method_ to solve this maze, what
would your method be? 

---

I am looking for the methods that a thoughtful person would use to to 
acomplish this task...

Debate might be interesting too.

Thanks,
-Michael <xie@netcom.com>








