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.

Use the always-turn-right rule but like Hansel & Gretel drop bread crumbs as you go.  Drop a bread crumb at the entrance to each "room" (a room is a square in the maze), and at the exit (next to the room where you're going next). 

When you find a dead end, turn around & start picking up bread crumbs, continuing to follow the turn-right rule.  When you enter a room if you find a bread crumb at that entrance, pick it up; otherwise drop one.  When you leave a room, if you find a bread crumb at that exit, pick it up; otherwise drop one there.

This will leave a trail of bread crumbs, two crumbs in each room, that defines the no-dead-ends route.  The advantage of this technique over the earlier posts, is that you don't have to back track.  You only travel through the maze once.

Edited on February 22, 2005, 4:46 am

Posted by Ken Haley on 2005-02-22 04:30:14