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?
[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 firstname.lastname@example.org
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