Jeff Sandys  <Jeffrey.MI.Sandys@airplane.com> wrote:
+---------------
| If you do have a map of the maze...  Find all the cells that have
| only one connection, and trim them from the tree, (don't trim the start
| and finish cell).  Repeat the process until there are no cells (except
| start and finish) that have one connection (Or until all cells have just
| 2 connections).  What remains is the solution path.
+---------------                   \?/

Or paths, plural. Then at that point you either do a breath-first search,
pruning when you run into yourself, or... is there another (better) way?

Consider a hypercube with the start & finish in diagonal corners, and *no*
barriers in the outer shell of the maze (or worse, a modest number of them
say, ~25% of the possible number, so the number of possible solution paths
is *extremely* high). Your algorithm (very cleverly) eliminates all the
"dead ends" (if any), but what then?


-Rob

[p.s. Apologies in advance: Back from sabbatical 11/2/98, but
until then email will still get a "vacation" bounce message...]

-----
Rob Warnock, 8L-855		rpw3@sgi.com
Applied Networking		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
2011 N. Shoreline Blvd.		FAX: 650-964-0811
Mountain View, CA  94043	PP-ASEL-IA