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.
The Input
: 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 prompt the user to choose a le and then read the
maze in from the le. The rst 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:
6 5
1 1 1 1 1
1 0 0 e 1
1 1 1 0 1
1 m 1 0 1
1 0 0 0 1
1 1 1 1 1
The maze will always have a wall around the outside, so you need not be concerned about the mouse falling
o the maze as it explores all directions.
The Backtracking Algorithm:
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 neighbouring positions (i.e., non-wall 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 o the
stack and pushes the untried neighbouring 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 overall goal is to nd the path to the exit from the starting position. Thus, we need to remember how
we got to the exit in the search process. The algorithm not only marks an unvisited neighbouring position
as visited, but it also stores what position we got to the neighbour from. For example, if we visit position
N
because it is a neighbour to position
C
that we are currently at, then we also record at
N
that we came
from
C
. These records will allow us to trace backwards through the path (i.e., from the exit to the mouse
starting point) after the backtracking completes (assuming we manage to nd the exit).
The backtracking algorithm works as follows:
initialize the stack;
goal = the position of the exit in the maze;
start = the initial position of the mouse in the maze;
push start onto the stack;
while we haven t found the goal and the stack isn t empty
f
curr = pop the top position off the stack;
currRow = the row number of position curr;
currCol = the column number of position curr;
check each of the four neighbouring positions of curr in turn:
if the neighbour is a valid position
f
check if it is the goal
if it s not the goal and it is open and has not been visited yet
f
visit it: mark it with . and set its previous position to curr;
push it on the stack;
g
g
g
// end while
Once the maze is processed, if we found the exit, we can mark the positions on the path with
P
(so we
can see it when we print out the maze). The path-marking works as follows:
curr = goal;
while ( curr != start )
f
if ( curr != goal )
set the maze element at position curr to P ;
curr = previous position stored with this maze element by the backtracking algorithm;
g
Stack:
Because the backtracking algorithm needs a stack, you must implement a stack class. Each item
in the stack is the position of a cell in the maze | that is, the row and column number of the cell. The marker
should be able to remove your stack implementation and replace with another stack implementation and
still have your program work. Thus, you must provide a standard stack implementation with the standard
methods (
push
,
pop
,
top
, and
isEmpty
). Use the linked-list implementation of a stack | you may use the
code from class.
The Output:
Your program must print out the maze after you read it in, and after you have processed
the maze to nd the path. For example,
Assignment 2 COMP 2140 Fall 2014
Finding a path through a maze
----------------------------
The input maze:
1 1 1 1 1
1 0 0 e 1
1 1 1 0 1
1 m 1 0 1
1 0 0 0 1
1 1 1 1 1
The path to the exit (marked with P ):
1 1 1 1 1
1 0 0 e 1
1 1 1 P 1
1 m 1 P 1
1 P P P 1
1 1 1 1 1
Path-finder program ends normally
Here's another example output:
Assignment 2 COMP 2140 Fall 2014
Finding a path through a maze
-----------------------------
The input maze:
1 1 1 1 1 1 1 1
1 m 0 0 0 1 e 1
1 0 1 0 0 1 1 1
1 0 1 0 0 1 0 1
1 0 1 1 0 1 0 1
1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1
Mouse is trapped --- exit not found (visited positions marked with . ):
1 1 1 1 1 1 1 1
1 m . . . 1 e 1
1 . 1 . . 1 1 1
1 . 1 . . 1 . 1
1 . 1 1 . 1 . 1
1 . . . . . . 1
1 1 1 1 1 1 1 1
Path-finder program ends normally
Suggestions
Here is a list of classes that your program might have, depending on how you implement things:
The class matching the le name, which probably contains only the main method.
Position
class: Each instance contains the row and column of a position in the maze. This class
probably only needs the standard accessors and mutators/action methods.
Node
class: Ordinary node class (you could use the code from class) for use by the stack. Each node
stores a
Position
Stack
class: Standard stack class (you could use the code from class).
A maze eleand the previous position on the path from the
mouse's starting position to the exit (in case this maze element turns out to be one of the positions on
the path from the starting position to the exit).
A maze class: Each instance contains the two-dimensional maze array, the number of rows and the
number of columns, the starting position of the mouse and the position of the exit. The constructor
for this class could be the method that prompts for the input le's name and reads in the maze. The
backtracking algorithm and the path-marking algorithm should be methods in this class.
The
String
methods
trim
and
split
can be used to read the characters of a row of the maze:
String inLine = inFile.readLine();
inLine = inLine.trim();
String[] tokens = inLine.split( "\\s+" );
for ( int i = 0; i < tokens.length; i++ )
System.out.println( "The next char in the row is "
+ tokens[i].charAt(0) );
Hand-in Instructions
Go to COMP2140 in Desire2learn, then click \Dropbox" under \Assessments" at the top. You will nd a
dropbox folder called \Assignment 2". Click the link and follow the instructions. Please note the following:
Submit ONE .java le. The .java le must contain all the source code. The .java le must be named
A2<your last name><your student id>.java
(e.g.,
A2Cameron1234567.java
).
Please do not submit anything else.
We only accept homework submissions via D2L. Please DO NOT try to email your homework to the
instructor or TAs.
We reserve the right to refuse to grade the homework or to deduct marks if these instructions are not
followed.
Honesty Declaration
NEW:
You can check if you have handed in an honesty declaration by looking at your COMP 2140 grades
on D2L. There's a grade column for \Honesty declaration" (or shortened to \HD"), which should contain
\Yes" | if it contains anything else, you have not given your instructor an honesty declaration.
Your Assignment 2 (and any other work in this course) will not be marked unless you have handed in
the blanket honesty declaration. (The honesty declaration is available on the course website in Desire2Learn
under \General Information (all sections)" in the Content Browser. You should have handed in the honesty
declaration to your instructor by September 18.)
You must hand in the honesty declaration exactly
ONCE this term and it will apply to all of your assignments and other work in this course.
