CS 206 - Introduction to Data Structures

Assignment 6: Due 11:59AM Tuesday October 29


It's corn maze season. Walking a corn maze would be excellent preparation for this assignment. Actually, walking a corn maze is just generally excellent.

This assignment is to write a program that finds a path through a 2D maze making moves akin to a bishop in the game of chess. The program must use recursion to find a path through a maze. Note that mazes can have loops (unlike one of the mazes shown below), dead ends, multiple solutions, or no solution.

For this assignment, you are provided with several files to get you started /home/gtowell/Public206/a6

Copy these into an eclipse project using the usual procedure (see Lab 4). These files are intended to be a useful starting point. You are not required to use them. You may modify them as you see fit. However, your program must be able to read mazes from files that follow these requirements:
  1. The maze must be rectangular
  2. The following characters are used to define the maze:
  3. No other characters may appear in a maze file
For instance, below left is a fairly trivial maze (with its solution to the right):
Original MazeMaze with solution indicated by 'A'
**s***
* ****
** ***
* * **
**** *
***e**

**A***
*A****
**A***
* *A**
****A*
***A**

Below (left) is a slightly bigger maze with lots of possible solutions one of which is shown on the right.
Original MazeMaze with solution indicated by 'A'
**s*****
*      *
*      *
* *    *
*  *   *
***e****

**A*****
*A     *
* A    *
*A*    *
* A*   *
***A****
Also, to get you going, the following files contain solvable mazes that meet the above requirements.

Bishops' Moves

A bishop in the game of chess can only move diagonally. Hence, if a bishop is at position [5,5] then the possible moves are: [4,4], [4,6], [6,4], and [6,6]. (In chess, a bishop can move more then one space at a time. For this problem, we limit the bishop to moving one space at a time.) Bishops may not move to a position that is occupied by a wall. Nor may bishops move off the board.

Requirements

  1. The program must be able to accept the name of a maze file from the command line
  2. The program must print out a trace of each position that it tries. For example, the following is a trace for a solution to the first maze above: 
    Considering <0,2>
  Considering <-1,1>
  Considering <1,1>
    Considering <0,0>
    Considering <2,0>
    Considering <2,2>
      Considering <1,1>
      Considering <3,1>
        Considering <2,0>
        Considering <4,0>
        Considering <4,2>
        Considering <2,2>
      Considering <3,3>
        Considering <2,2>
        Considering <4,2>
        Considering <4,4>
          Considering <3,3>
          Considering <5,3>
             Solved
**A***
*A****
**A***
* *A**
****A*
***A**
  3. Indenting is the above position trace is significant and required. Indentation indicates the move number. So no indentation indicates the starting position. One more from the starting position is indented 2 spaces, 2 moves 4 spaces, etc. In the above trace, I print every move considered. Most of the moves are into walls and were immediately rejected. You need not print immediately rejected moves.
  4. If the program finds a path through the maze, it should print the maze with the path indicated as in the example above. (You can use a character other than A to indicate the solution path.)
  5. The program must use recursion.
  6. You must submit at least one maze file of your own design. The maze must be: at least 10x10, solvable, have at least one dead end, and have at least one loop. Bonus points may be awarded for artistry.
  7. Within the README file, include a brief (max 1 paragraph) reflection on what went well and/or poorly and why

Electronic Submissions

Your program will be graded based on how it runs on the department’s Linux server, not how it runs on your computer. The submission should include the following items: DO NOT INCLUDE:
Data files that are read from the class site.

The following steps for submission assume you are using Eclipse, and that you created a project named AssignmentN in the directory /home/YOU/cs206/

  1. For this assignment N=6
  2. Put the README file into the project directory and your maze (/home/YOU/cs206/AssignmentN)
  3. Go to the directory /home/YOU/cs206
  4. Enter submit -c 206 -p N -d AssignmentN

For more on using the submit script click here