Assignment 4: Backtracking through a maze

Assignment4: Backtrackingthroughamaze
Objectives
Upon completion of this assignment, you need to be able to: • Implement a Double-ended Queue ADT using a doubly-linked list. • Implement a backtracking maze-solver using backtracking. • Make use of Java’s command line argument list. • Continue accumulating good programming skills. References: • CSC115 Java coding conventions. • Textbook Chapter 6 (Recursion ), reference to 6.1: Backtracking • Textbook chapter 8 (Queue), reference to Deque. Introduction
A maze may be represented as a two-dimensional array of characters, each array item occupyingacell.Wewillletthe‘*’characterrepresentawallandthespace‘ ’character represent an open spot in the maze. One open cell in the first row or the first column will represent the entry point of the maze and another open cell in the last row or last column will represent the exit point. Finding a path through the maze means finding a path of connected cells that contain space characters, cells being connected only horizontally or vertically. The path itself is a list of (r,c) pairs where r is the row number from 0...numRows−1 and c isthecolumnnumberfrom 0...numCols−1.Thepathlistincludesboththestarting cell and the finishing cell.
A maze file is a plain text file containing all the details of the maze itself, minus the actual path. The following is an example of what a maze file would contain:
9 11 0 1 8 9 * ********* * * * *** * *** * * * * * ******* * * * * * * ******* * * * ********* * The first three lines indicate that the maze described in the file is 9 rows by 11 columns, the starting cell is (0,1) and the finishing cell is (8,9). The rest of the lines represent the placements of the wall (“*”) squares and the empty (“ ”) cells.
QuickStart
(1) Create a fresh directory to contain this assignment: CSC115/assn4 is a recommended name. Download this pdf file and the .java files to this directory. (2) Download and extract the docs.zip, javafiles.zip, and testMazes.zip in the same directory. A docs directory will be created to store the specifications for the public classes. All the document links in this document are accessible if they are stored in the docs directory local to this pdf file. (3) The following files are complete: • Cell.java • CellNode.java • DequeEmptyException.java • RunSolver.java (4) You will create and complete the following two classes: • CellDeque.java • Maze.java
DetailedInstructions
The following java classes are completed already: • Cell defines a cell in a 2-dimensional grid or matrix by its row and column numbers. We follow the common programming convention that row∈{0,..., numRows−1}and col∈{0,..., numCols−1}. • CellNode is a Node for a doubly-linked list that holds Cell items. • DequeEmptyException for throwing when a call to remove an item from an empty Deque object. This is a standard home-made exception, that should be familiar. • RunSolver isanexternaltesterthatwillbedescribedindetailafterthe Deque and Maze sections.
You must create and implement the following two classes.
CellDeque
As part of the process of finding a successful path through the maze, we require a list to contain Cell objects: we add a cell when it is potentially part of the solution or remove it during the backtracking if it leads to a dead-end. We could use a general List ADT, but we only need to insert and remove from the beginning or the end of the list as we wander through the maze. Adding a cell to the list is easy, but when we backtrack, that cell needs to be removed, a process that a regular Queue will not allow. A Stack ADT allows us to remove the last try, but when we are finished, the Stack ADT will serve the solution cells in reverse order.
Hence, our choice is the Double-Ended Queue, or Deque (pronounced “deck”), which is described briefly in the textbook’s chapter on the Queue ADT. It behaves as if it were a combinationofbothaStackandQueue.Youaretoimplementthisclass,usingthedoublylinked CellNode.
See the CellDeque specifications for the required public methods for this class Be sure to do the necessary internal testing. Add whatever private or public methods help make the programeasytotestanddebug.Amethodthatprintsoutthecontentsismosthelpful.
Maze
You can use whatever data type you wish inside the Maze class to represent the maze object. We recommend a 2-dimensional array of characters, with specific characters representingafreecell,orablockedcell,oracellthathasalreadybeenvisited.Avisited cell lets you know which cells are currently part of the part of the solution, much like leaving a stone in a maze to let you know that you’ve already tried that direction. Note that the constructor takes, as input, an array of Strings to represent the maze. Using what you know about String objects, you can extract whatever you need from this to store the maze object as the data type of your choice. Although it is worth thinking about loops or multiple solutions during the algorithm design,themazesthatwillbeusedtotestyourcodewillhaveasinglesolutionornosolution. You may create whatever data fields and extra methods that you need to make this work. However there are specific methods you must implement: See the Maze specifications for the required public methods for this class. In Java, a public method should not use recursion; we leave that to a private method. The public method simply initiates the recursion by calling the recursive method with its initial values. In this assignment, solve must call the following private recursive method: • private boolean findPath(Cell src, Cell dest) Thismethodanswersthequestion:“Isthereapathfromagivensourcecelltothedestination cell?” The following recursive definition of a path may help: A path from point A to point B exists if A is equivalent to B, or if C is adjacent to A and there is a shorter path from C to B. In the implementation of this method, the base cases must be clearly identified and dealt with before the recursive statements. If no path exists in any direction between the source and destination, then backtracking is necessary. Backtracking may include removing the current cell from the solution list and/or flagging the current cell as not part of the path and then returning false. Since the internal testing involves creating test mazes (lots of typing), we supply a set of testmazesinfiles.Soforthe Maze class,youarenotrequiredtocreateinternaltestcases. An external tester RunSolver is supplied, with a single main method that extracts the informationfromamazetextfileandcallstheMazeconstructorandsolvemethods.
RunSolver
This class was written primarily to extract information from tester files to check the correctness of the Maze class. You are expected to understand this class well enough to have writtenityourself.Youmayaddsome println statementstohelpyou,butdonotchange the statements that interact with the Maze class.
Examples
The following screen shots demonstrate the expected results, using the mazes in files maze00.txt and maze01.txt
Intheexamplebelow,weaddedastatement: System.out.println(this); neartheend ofthe solver methodinthe Maze classtotestwhetherthemazelookedthewayitshould. You can use whatever structure you find meaningful; in our case, we let ‘P’ represent the current path.
Submission
Submit the following completed file to the Assignment folder on conneX. • CellDeque.java • Maze.java Pleasemakesureyouhavesubmittedtherequiredfile(s)andconneXhassentyouaconfirmationemail.Donotsend[.class](thebytecode)files.Also,makesureyousubmityour assignment, not just save a draft. Draft copies are not made available to the instructors, so they are not collected with the other submissions. We can find your draft submission, but only if we know that it’s there.

Grading
Marks are allocated for the following: • Proper programming style is demonstrated, as per the coding conventions on CSC115 conneX Resources. • TheDequeclassmustbeimplementedusingadoubly-linkedlist,withnodatastructures from the java.util package. • The Maze findPath method must be – recursive and – organized to clearly determine the base case(s) and the recursive statement(s). • Use of private helper methods where applicable. • Internal testing in the Deque main method. You will receive no marks for any Java files that do not compile.