soon discover there are no legal moves since we are blocked by wall on three sides and cell comprising part of our path since we can go no further from this cellwe have no choice but to go back to our previous position in cell ( when hitting dead endwe don' simply turn around and go back over cell previously visited as if it were part of the path since this would cause circle insteadwe mark the cell with different token indicating dead end and move back to the previous position in our examplewe use lowercase to represent cell leading to dead end after moving back to cell ( )we examine the other directions and soon find the cell to the right is open and move in that directionplacing us in cell ( from this positionwe find the only legal move is to the right and thus move in that directionplacing us in cell ( nextwe move up one step since the cell above is open but this move will result in dead endrequiring us to once again back up to the previous position after backing up to our previous position at cell ( )we find the cell below is open and move to position ( repeating the process we soon find the exit at position ( and path from the starting cell to the exit no path to the exit the exit in this example was accessible but what happens if there is no path between the start and exit cellsconsider modified version of our sample maze in figure where wall has been placed in cell ( closing the path to the exit when reaching position ( )as described earlierwe will discover this is dead end and have to back up but there are no other legal moves from cell ( with the positions above and below blocked by wallthe position to the right leading to dead end and the position to the left currently part of our path from position ( )we have to back up and try another direction ultimatelywe will have to backtrack all the way to the starthaving found no legal move from that position figure modified version of the sample maze with the exit blocked the maze adt given the description of the maze problem and the backtracking algorithm for finding path through the mazewe now define the maze adt that can be used to construct and solve maze