In this question, you will test, using a backtracking algorithm, if a mouse can escape from a rectangular maze.
The backtracking algorithm helps the mouse by systematically trying all the routes through the maze until it either finds the exit or exhausts all possible routes (and concludes that the mouse is trapped in the maze). If the backtracking algorithm finds 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 from any position, and always in the same order.
The input to the algorithm is a maze with walls (represented by '1' characters) and open passage ways (represented by '0' characters). The starting position of the mouse is represented by 'm' and the exit from the maze by 'e'. Your program should read the maze in from a file, and the name of the file should be a command-line argument. The first line of the input will contain the number of rows and the number of columns in a maze. Thus, the input might look like the following:
The maze will always have a wall around the outside, so you need not be concerned about the mouse falling off the maze as it explores all directions.
The backtracking algorithm keeps a stack of positions that are the beginnings of paths it has yet to try. From the current position, the algorithm pushes onto the stack any untried open neighboring positions (if there are any), always looking forward, backward, left and right from the current position. At each step, the algorithm pops the top position off the stack and pushes the untried neighboring positions onto the stack. The algorithm must mark each visited position with a period to avoid revisiting positions --- so that it will not
loop forever trying the same routes.
The backtracking algorithm works as follows:
read in the maze;
initialize the stack;
goalCell = the position of the exit in the maze;
startCell = the initial position of the mouse in the maze;
currentCell = startCell;
while currentCell is not the goalCell
mark currentCell as visited;
push onto the stack the unvisited open neighbours of currentCell;
if the stack is empty
the mouse is trapped: we tried all routes and failed to find the exit;
else
pop a cell from the stack and make it currentCell;
end while;
the mouse can escape the maze: we reached the goal cell.
Because the backtracking algorithm needs a stack, you should implement a stack class (or you can use that from COSC 2006). Each item in the stack is the position of a cell in the maze --- that is, the row and column number of the cell.
Your program should print out the maze after each cell is visited, showing which cells have already been visited. Finally, your program must print out a message indicating whether the exit was found or that no route to the exit could be found (the mouse is trapped).
To develop your program, you can use the input file testMaze.txt, which contains the above maze.
- Hand in your complete Java source code; and a copy of the results produced
- Upload your source code to CMS
- Demonstrate your program to TA before/on the due day