Given a two dimentional maze which only has one path from entrance to exit, develop an algorithm that discovers the no-dead-ends route from start to finish.

There are sites around the Net where you can find 2D mazes which have but one path. 

These may be printed out along with the solution path; certain of these are randomly generated.

I am thinking of 2D maze based upon an X-Y lattice structure. 

If I visually scan each horizontal path and find a deadend, then I would mark the deadend(s). 

At the 'beginning' of each such horizontal path (which would be the intersection of a vertical path), I would similarly mark.

Having done this for every horizontal row, I would then proceed to do the same vertically, but with an addition.

If I found that mark at an 'intersection', I would treat it as a deadend.

I envisage that I would have to repeat horizontal, vertical procedure several times, which I think would be governed by the number of rows and columns in the maze.

At the end of this process the way through would be where there are no blocks.

I am thinking that this process might be applied to an 'irregular' lattice (where the paths are not horizontal or vertical).

I haven't thought the process through fully, but might I suggest that Gamer is actually asking for a verbal description of such an algorithm.

Posted by brianjn on 2004-06-27 21:16:13