Subject: Re: solving a maze in scheme
From: (Rob Warnock)
Date: 1998/10/25
Newsgroups: comp.lang.scheme
Message-ID: <70vav3$>
Jeff Sandys  <> 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
Applied Networking
Silicon Graphics, Inc.		Phone: 650-933-1673
2011 N. Shoreline Blvd.		FAX: 650-964-0811
Mountain View, CA  94043	PP-ASEL-IA