COMP 2140 Assignment 2: A Run-time Stack and Merge Sorting a Linked List
Helen Cameron and Stephane Durocher
Due: Wednesday October 22 at noon
Programming Standards
When writing code for this course, follow the programming standards, available on this course's website on
Desire2Learn. Failure to do so will result in the loss of marks.
Objective
To test, using a backtracking algorithm, if a mouse can escape from a rectangular maze.
Your Program
General Overview:
Your program must implement a backtracking algorithm that helps the mouse by
systematically trying all the routes through the maze until it either nds the exit or exhausts all possible
routes (and concludes that the mouse is trapped in the maze). If the backtracking algorithm nds a dead
end, it retraces its path until it reaches a position from which there is an untried path. The backtracking
algorithm always tries all directions (forward, backward, left, and right | no diagonal moves allowed) from
any position it reaches.