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.
I believe that the solution required is not to physically 'walk, through the maze as such.
I have found an algorithm which purports to develop a solution for a
'perfect maze'; the definition being that there is only one pathway -
one in you cannot get into an "open circuit".
The concept basically pulls down walls as you proceed to analyse the
structure. What tends to remain is a less complicated maze.
In a programmed situation, the walls destroyed are stored, but recreated after the 'simpler' path is found.
I'll leave it someone else to develop and simply describe a visual 'pencil and paper' algorithm (which I believe Gamer requires)
Posted by brianjn
on 2005-05-10 09:26:33