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.

Follow the righthand wall, leaving a trail alongside it.  When you reach the exit, retrace your path only where it does not contain a double trail.

X finish X

X      o  XXXXXXXXX

X      ooooooooooo X

X      ooooooooooo X

X      o  XXXXXXXXX

X start X

The o trail finds the direct path but contains a double trail down to the dead end.  Eliminating the double trail eliminates the dead end.

I can't think of a way for the simple maze described to foil this plan.

-Jer

Posted by Jer on 2004-06-21 13:55:08