In this assignment, you will write a function that takes in a 2D char array representing an ASCII maze and returns a HashSet of all possible paths from a person's starting position in the maze to its exit.
Movement through these mazes is restricted to four directions: up, down, left, and right. All the mazes we pass to your backtracking function in this program are guaranteed to abide by the following restrictions:
There are no guarantees regarding the number of walls in the maze or the locations of those walls. It's possible that the border of the maze might not be made up entirely of walls (i.e., it might contain spaces), in which case, its up to you to make sure the person in the maze does not go outside the bounds of the 2D array. Note also that the initial positions of the ' @ and e characters may vary from maze to maze.
Consider, for example, the maze shown below (far left diagram). For the purposes of this assignment, there are exactly two valid paths from the '@' character to the exit: see image.
When creating a string to denote a path, we indicate each directional movement from the person's starting position using a single character: 'u (up), d (down), l (left), or r (right). The characters in each string must be separated with a single space. There should be no spaces at the beginning or end of the string. For example, the strings representing the two paths above are as follows (and should be placed into a HashSet to be returned by the wrapper method that calls your backtracking method):
“d l l d d r r r r”
“r r d d d”
Note that you should never produce a path that causes the person in the maze to step on the same square more than once. For example, in the maze shown above, it might be tempting to pass over the exit and journey around the loop in the bottom-right corner of the maze before landing on the exit again. That would get the person from the starting position to the exit, but that path would be invalid because it would cause the person in the maze to touch some position twice (namely, the position with the exit): once when passing over the exit the first time, and once when the person finishes the given path. This invalid path is denoted by the following red breadcrumb trail: see image.
Implement the following methods in a class named Pathfinder
public static HashSet< String> findPaths(char [][] maze)
This method receives a 2D char array representing an ASCII maze and returns a HashSet of strings representing all valid paths from the starting position ('@') to the exit (e) using the format described above. The maze array will be non-null and non-empty and is guaranteed to be well-formed according to the guarantees given in the problem statement above. If there are no solutions, you should return an empty HashSet (rather than returning null). Please note that when your method returns, the maze array must be in the same state that it was in when this method was called initially, without any changes.
public static double difficultyRating()
Return a double on the range 1.0 (ridiculously easy) to 5.0 (insanely difficult).
public static double hoursSpent()
Return a realistic estimate (greater than zero) of the number of hours you spent on this assignment.
You must directly modify the backtracking code I've distributed with this assignment. In doing so, you should not drastically re-factor the code (i.e., you should not change it to be more object-oriented or to take a radically different backtracking approach). One of the purposes of this assignment is to force you to delve into an existing solution and figure out how it works, and the code you submit should reflect that.
Constructing the output string for each path should be a linear operation. So, string concatenation is strictly forbidden in this assignment. Each time you add a direction to your running path, it must be an O(1) operation. When it comes time to add a string to your HashSet, generating that string must be an O(k) operation (where k is the length of the string).
The solution you submit must use a recursive backtracking algorithm. (You cannot submit a non-backtracking solution for this problem.) The algorithm you submit must backtrack when an obviously infeasible state is reached, rather than continuing down a path that is guaranteed to lead to an invalid path, such as the one denoted by the red breadcrumb trail above above.
Also, the algorithm you submit must be written in such a way that it generates any given path through the maze at most once. If it generates a particular path multiple times, the HashSet can certainly help get rid of those duplicates, but your runtime will necessarily suffer for having produced the same path repeatedly. Be sure to avoid this.