Data Structures

Project 3 - Recursive Maze Solver

Objectives

• Use recursion

Description

For this project, you get to write a maze solver. For this project, the mazes are two dimensional arrays of chars. Walls are represented as '#'s and ' ' are empty squares. There will be zero or more exits along the outside perimeter. To be considered an exit, it must be reachable from the starting position.
Here are some example mazes:
Maze a

7 9
###### ##
# # #   #
# # ###
# #     #
# ##### #
#       #
#########

Maze b

7 12
############
# # #      #
# # # #### #
# #        #
# ##### ## #
#       #  #
############

Maze c

3 5
# # #

## ##

Maze l

4 7
#######
#     #
# ### #
### ###

Requirements

Write a MazeSolver class in Java. This program needs to prompt the user for a maze filename, a starting row and a starting column and then explore the maze. If the initial position is invalid, then display an error message (see example for required text). Otherwise, display how many exits were found and the positions (not indices) of the valid exits. Your program can display the valid exits found in any order. See the examples below for exact output requirements. Also, record a brief 5-8 minute video explaining the major portions of your code, including how you designed the recursion to explore the entire maze. Identify the base case. Include in the recording your program running. Also include any shortcomings or future work. Submit either the video or a link to the video (youtube.com, Google Drive, etc.). You can show your code in the video. Furthermore, create a file named rubric-mazeSolver.txt that is a completed rubric (including the number of hours spent on the assignment).

Examples

Note, user input is in bold face blue and underlined text is required for test cases.

Maze a

Please enter the maze filename: a.txt
You entered a.txt

Please enter the starting row (1..7): 4
You entered 4
Please enter the starting column (1..9): 5
You entered 5

###### ##
# # #   #
  # # ###
# #     #
# ##### #
#       #
#########

Starting from 4, 5
Found 2 exits at the following positions:
3, 1
1, 7

Maze b

Please enter the maze filename: b.txt
You entered b.txt

Please enter the starting row (1..7): 5
You entered 5
Please enter the starting column (1..12): 10
You entered 10

############
# # #      #
# # # #### #
# #        #
# ##### ## #
#       #  #
############

Unable to start at invalid location 5, 10

Maze c

Please enter the maze filename: c.txt
You entered c.txt

Please enter the starting row (1..3): 2
You entered 2
Please enter the starting column (1..5): 2
You entered 2

# # #
     
## ##

Starting from 2, 2
Found 5 exits at the following positions:
2, 5
1, 4
3, 3
1, 2
2, 1

Notice that multiple valid exits were found. Remember, you can present the valid exits in any order.

Maze l

Please enter the maze filename: l.txt
You entered l.txt

Please enter the starting row (1..4): 2
You entered 2
Please enter the starting column (1..7): 3
You entered 3

#######
#     #
# ### #
### ###

Starting from 2, 3
Unsolvable!

Notice that the term "Unsolvable" is required if there are no valid exits. In Maze l, there are no valid exits because the only gap in the perimeter is unreachable.

Maze d

Please enter the maze filename: d.txt
You entered d.txt

Please enter the starting row (1..41): 40
You entered 40
Please enter the starting column (1..41): 40
You entered 40

#########################################
#                                       #
# ##################################### #
# #  ### # ## #  # ###  #       ## #  ###
# #    #   ## ##### ##  ##  # ###    #  #
# #  #   #  # #   # ########### #   # ###
# ##  # #       # # # #        #   #    #
# ##          ##  #       # ## #    # ###
# ##  #  # ###    # # #####    #        #
# ## # #   # # # ##  ## ## #   # ##  #  #
# #        # ##    #    ##  #  ####     #
# #  # ##   ## ###       #  #      #    #
# ##   #####   ##   ## ## #  #   ## # # #
# ##  #    #    ## #  #     ## ####     #
# #   ## ## #   #######  ## #    #     ##
# ## # ## #   ##  #  #       ##   ##    #
# #  #   # ######  ## # # ## #          #
# ##      #   #  ###   # #  ##   ### ## #
# #   ##   # # #  ###  #   #  #      # ##
# # # #   # #  #  #   ##  ###     # #  ##
# ##   #### #    #   ### # #  #      # ##
# ### # # #       #        ## ###  # #  #
# #   #### ## ## ####    #### ###  #    #
# # ##  #   ## #    #    ####           #
# ##  # # #     #  # ## #   # #  ### #  #
# ###  #   #    ##  ##  #   # ###  #    #
# #          #      #  ### #  ##       ##
# ###  # #      #      #   ###   #      #
# #   ####     # #  ###   # #  # #      #
# ### #  #  # # # #     ####  #   # #   #
# ##    ##   ### #  #     ## ### #  ## ##
# #    ####   # ### #   # #   ## #  #   #
# #### # #   ####  #    ##     ## # #  ##
# # #   ### #   # #       # # #  #  ##  #
# # # ##  #  ##  # #     #    ### # ### #
# # #  ##  #  ## ###   #   ## # ##  # # #
# #   # #   #    ## ## ###     # # # ## #
# ### ####        # # ##  #  ## #   #   #
# ##################################### #
#                                       #
#########################################

Starting from 40, 40
Unsolvable!

Other Mazes

• A simple maze to start with
• Maze e
• Maze f
• Maze g
• Maze h
• Maze i
• Maze j
• Maze k

Rubric:

	Points      Item
	----------  --------------------------------------------------------------
	_____ / 10  Style
        + Code is indented correctly
        + Methods should be no longer than 1 page
        + Documentation: (written for another software developer)
        * All source code files include Javadoc header block with description, @author, @version, etc.
        * Javadoc (with block tags, for example @param, @return) before each method
        * All non-trivial variables are commented
        * Comments included before major portions of code
	_____ /     Compiles (max of 50% if it doesn't compile)
	_____ / 66  Successfully passes codePost unit tests (using a recursive solver)
	_____ / 22  Video
	_____ /  2  Completed rubric (estimates for each line including hours spent)

	_____ /100  Total


	_____  Approximate number of hours spent

	I, (REPLACE WITH YOUR FULL NAME), affirm that the code that I submitted is my own work and that I did not receive help that was not authorized by the instructor.

Copy and paste this rubric into a rubric-mazeSolver.txt file (not a .docx, .doc nor .rtf file). Think of this as a checklist to ensure that you receive the maximum points possible. For each grade item, fill in your estimate for the grade you deserve. Additionally, include your estimate of how many hours your spent. Lastly, replace, "(REPLACE WITH YOUR FULL NAME)" with your full name to indicate that what you are submitting is entirely your own work.

Submission

Submit your MazeSolver.java (and any other necessary .java files) to codePost.io. Submit the following items to the appropriate Assignment folder in CougarVIEW:

• MazeSolver.java (and any other necessary .java files)
• Recorded video or link to your video
• rubric-mazeSolver.txt

If you resubmit one or more files, use the same file names. This will effectively replace those files. If you need to change the filenames, then please submit the new file(s) and email me.

Hints

• Start small. First, plan your strategy for exploring the maze. This is more intellectually challenging than previous assignments. Write down a general plan then execute it by hand before starting to code! Once your algorithm works, then create an object with an empty solver() method and a toString() method that displays the current maze and make sure it compiles. Then, create an object by passing it the filename for a maze and make sure it can display the maze. Then, add the body of your solver to the class.
• Change the character in the maze from a space to something else when the solver has started to explore that position. Also, use a debugger and/or temporariliy display the entire maze at the top of recursive solver to see how the exploration is going.
• The tutoring lab has has several hours to answer questions.

Challenges

Looking for a challenge, consider doing one or more of the following:

• Use an enum to store the directions.
• Store the maze in a one-dimensional array (translating row and column indices to a single number).
• Make an animated gif or a movie of the exploration of a maze.

Notes

Input Files Not Found
Your input files (for example, a.txt) need to be in the same directory where the JVM is executing your code. When you're using an IDE, it can be confusing where this is. To determine what that directory is, execute the following code:

System.out.println("Put your input (maze) files in this directory: " + System.getProperty("user.dir"));