Hey everyone,
I have been assigned to create a recursive maze program and I am having trouble to figure out how to start it. I am pretty much lost and confused and don't know what to do. I do not want anyone to complete it for me but giving me a boost to get me on the right track would be appreciated.
Program Description:
Based upon problems 18.20 – 18.22 in the text, your task is to create a recursive method that given a maze will determine if the maze is solvable, display a possible path, as well as how many steps that path requires. Your method must be able to handle mazes of any size and the option to generate mazes randomly must be included.A total of three classes are required.
Maze – Used to define what a maze is
MazeSolver – Holds a Maze (as well as any other required data members) and the recursive method to solve the maze (as well as any other required methods).
MazeDriver – Creates an instance of MazeSolver and provides the user interface
Discussion for MazeA maze is defined by a 2 Dimensional character array. Walls in the maze are denoted by the ‘#’ character. Places that can be traversed are denoted by the ‘.’ character. Each Maze has one entrance on the left and one exit on the right.
An Example Maze:
Notice the Maze itself is surrounded by walls except for the entrance and exit.
The Maze class will also contain the starting and end points of the Maze.
Methods
Maze needs two constructors. One that accepts a char[][] and values for the entrance and exit. The second will accept no parameters, notify the user it is generating a random maze and then generate a random maze.The random Maze will have random dimensions between and including 6 – 12. They do not have to be square, each dimension is determined independently. A random start and end point will be found, but the start point MUST be on the left and end point MUST be on the right. As for the interior of the maze, it should be implemented so that there is a 1/3 chance any square is a wall and a 2/3 chance that any square is a path.
The Maze must also be able to output the Maze it contains as shown above.
Other methods you may want to consider:
Change the value of an element of the array
Retrieve the value of an element of the array
Retrieve the values of the start and end points
…anything else that will help you solve the problemDiscussion on MazeSolver
The MazeSolver will hold a single Maze as well as any other data members that may be helpful. This I will repeat, THE MAZE TO BE SOLVED IS A MEMBER OF THE MAZESOLVER CLASS.
Methods
The most important method in MazeSolver is a RECURSIVEbooleanmethod that will be used to solve the Maze it holds.
The Recursive method should accept two ints representing the current location in the maze. For the first call upon the method the entrance of the Maze will be passed as the current location. This method attempts to locate the exit marking an ‘x’ in each square that has been reached.Basic Algorithm
If there is no exit, you will arrive back at the entrance. From the current location, attempt to move in any of four directions. If a move is possible make a recursive call upon the method passing the new location. If it is not possible to move, backtrack to a previous location and attempt to move in a different direction.If the Maze is solvable, the state of the Maze itself should display ONLY the actual path taken to solve with ‘x’s. You must also keep track of how many steps your found solution is.
Since the MazeDriver is not going to have direct access to the Maze (and therefore its starting point) you may consider having a method in MazeSolver that accepts no parameters and calls upon the Recursive method with the starting point.
Discussion on MazeDriver
MazeDriver creates a MazeSolver object. The Maze that is passed to the MazeSolver is determined by the user. A menu should be provided that asks which Maze to use, one of three predefined Mazes or to generate a random maze. After a Maze is chosen the original Maze should be output, and then attempt to solve it. If the Maze is solvable, output that it was solved as well as the final path taken and the number of steps taken to solve. If the Maze is not solvable simply output that it was not solved.
Here are the predetermined Mazes:
char[][] m1 = {{'#','#','#','#','#','#','#','#','#','#','#','#'},
{'#','.','.','.','#','.','.','.','.','.','.','#'},
{'.','.','#','.','#','.','#','#','#','#','.','#'},
{'#','#','#','.','#','.','.','.','.','#','.','#'},
{'#','.','.','.','.','#','#','#','.','#','.','.'},
{'#','#','#','#','.','#','.','#','.','#','.','#'},
{'#','.','.','#','.','#','.','#','.','#','.','#'},
{'#','#','.','#','.','#','.','#','.','#','.','#'},
{'#','.','.','.','.','.','.','.','.','#','.','#'},
{'#','#','#','#','#','#','.','#','#','#','.','#'},
{'#','.','.','.','.','.','.','#','.','.','.','#'},
{'#','#','#','#','#','#','#','#','#','#','#','#'}};
char[][] m2 = {{'#','#','#','#','#','#','#','#','#','#','#','#'},
{'#','.','.','.','#','.','.','.','#','#','.','.'},
{'#','.','#','.','.','.','#','.','.','.','.','#'},
{'#','.','#','#','#','#','.','#','.','#','.','#'},
{'#','.','.','.','#','#','.','.','.','.','.','#'},
{'#','#','#','.','#','#','#','#','.','#','.','#'},
{'.','.','.','.','.','.','.','.','.','.','#','#'},
{'#','#','#','#','#','#','#','#','#','#','#','#'}};char[][] m3 = {{'#','#','#','#','#','#','#','#','#'},
{'#','.','#','.','#','.','.','.','#'},
{'#','.','.','.','#','.','#','#','#'},
{'#','#','#','.','#','.','#','.','.'},
{'.','.','.','.','.','.','#','.','#'},
{'#','#','.','#','.','#','#','.','#'},
{'#','.','.','#','.','#','.','.','#'},
{'#','#','.','#','.','#','.','.','#'},
{'#','#','#','#','#','#','#','#','#'}};I suggest downloading the posted version of this assignment on Blackboard and copy/paste these into your code. In command mode in vim use 1G=G to format.
Other Notes:
• Be sure to validate data for both value range AND type (catch InputMismatchException)
• Use the given Mazes for the first three options
• The fourth option will generate a random Maze using the given specifications
• The output of a solved Maze must ONLY display the path required to reach the exit, not all paths taken in attempting to solve
• Most frequent mistake I see on this assignment is forgetting that the recursive method returns a value and not doing anything with it. If a method returns a value, you most likely need to be doing something with it whenever you make a call. In this case, you MUST or else your solver will not work.
Summary of Files
You will need to create three (3) files for this assignment.
• Maze.java
• MazeSolver.java
• MazeDriver.javaRequired Elements:
• All outputs to the user must include identifying text.
• The user should be prompted for all inputs. Validate input for range and catch InputMismatchExceptions.
• Don’t forget to output number of steps for your solution to a maze
• Your program file must meet the programming standards defined for this course and contain the appropriate header documentation defined for this course. (see Blackboard, Course Documents)
• Course defined method documentation
import java.util.Scanner;
public class MazeDriver {
public static void main(String args[])
{
int input; //Number of maze
MazeSolver m = new MazeSolver();
Scanner scanner = new Scanner(System.in);
char[][] m1 = {{'#','#','#','#','#','#','#','#','#','#','#','#'},
{'#','.','.','.','#','.','.','.','.','.','.','#'},
{'.','.','#','.','#','.','#','#','#','#','.','#'},
{'#','#','#','.','#','.','.','.','.','#','.','#'},
{'#','.','.','.','.','#','#','#','.','#','.','.'},
{'#','#','#','#','.','#','.','#','.','#','.','#'},
{'#','.','.','#','.','#','.','#','.','#','.','#'},
{'#','#','.','#','.','#','.','#','.','#','.','#'},
{'#','.','.','.','.','.','.','.','.','#','.','#'},
{'#','#','#','#','#','#','.','#','#','#','.','#'},
{'#','.','.','.','.','.','.','#','.','.','.','#'},
{'#','#','#','#','#','#','#','#','#','#','#','#'}};
char[][] m2 = {{'#','#','#','#','#','#','#','#','#','#','#','#'},
{'#','.','.','.','#','.','.','.','#','#','.','.'},
{'#','.','#','.','.','.','#','.','.','.','.','#'},
{'#','.','#','#','#','#','.','#','.','#','.','#'},
{'#','.','.','.','#','#','.','.','.','.','.','#'},
{'#','#','#','.','#','#','#','#','.','#','.','#'},
{'.','.','.','.','.','.','.','.','.','.','#','#'},
{'#','#','#','#','#','#','#','#','#','#','#','#'}};
char[][] m3 = {{'#','#','#','#','#','#','#','#','#'},
{'#','.','#','.','#','.','.','.','#'},
{'#','.','.','.','#','.','#','#','#'},
{'#','#','#','.','#','.','#','.','.'},
{'.','.','.','.','.','.','#','.','#'},
{'#','#','.','#','.','#','#','.','#'},
{'#','.','.','#','.','#','.','.','#'},
{'#','#','.','#','.','#','.','.','#'},
{'#','#','#','#','#','#','#','#','#'}};
do
{
do
{
System.out.println("\n\nMaze Solver\n");
System.out.println("\n1. Maze 1");
System.out.println("2. Maze 2");
System.out.println("3. Maze 3");
System.out.println("4. Random Maze");
System.out.println("5. Quit");
System.out.print("\nEnter Number: ");
input = scanner.nextInt();
if(input < 1 || input > 5)
{
System.out.println("Invalid Number!");
}
}while(input < 1 || input > 5);
switch(input)
{
case 1:
m.addMaze(m1);
m.solve(m1);
break;
case 2:
m.addMaze(m2);
m.solve(m2);
break;
case 3:
m.addMaze(m3);
m.solve(m3);
break;
case 4:
m.randomMaze();
break;
}
}while(input != 5);
}
}
