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 Maze

A 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 problem

Discussion 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.java

Required 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);
		
	
	}
}

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.

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);
		
	
	}
}

Well think logically, how would you solve the maze given a piece of paper... Im sure you'll start seeing a pattern on checking how you examine each row and column in that row and the one below to see if there is an open space to move... i.e not # you should see a pattern appearing now... translate that into pseuedo

Member Avatar for ztini

Blow your teacher away and implement one of the many maze solving algorithms.

http://en.wikipedia.org/wiki/Maze_solving_algorithm

The easiest search pattern to learn is probably Breadth-First Search. Maybe not easiest, but it was one of the first I learned and it stuck with me.

http://en.wikipedia.org/wiki/Breadth-first_search

If you want shortest path, Dijkstra's is a good one too. Its a bit harder to grasp if you're not familiar with graph theory. Although, this might not be very effective considering the distance between all of your nodes (coordinates) is the same. But at least it will get your brain thinking about the solution.

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Okay I think I have figured some of it out. I am getting a couple of errors. Any help would be great!

Exception in thread "main" java.lang.NullPointerException
	at MazeSolver.<init>(MazeSolver.java:9)
	at MazeDriver.main(MazeDriver.java:88)
import java.util.Scanner;


public class MazeDriver {

	public static void main(String args[])	
	{
		int input; //Number of maze
		Maze m = null;
		Scanner scanner = new Scanner(System.in);
		
		char[][] m1 = {{'#','#','#','#','#','#','#','#','#','#','#','#'},
                {'#','.','.','.','#','.','.','.','.','.','.','#'},
                {'.','.','#','.','#','.','#','#','#','#','.','#'},
                {'#','#','#','.','#','.','.','.','.','#','.','#'},
                {'#','.','.','.','.','#','#','#','.','#','.','.'},
                {'#','#','#','#','.','#','.','#','.','#','.','#'},
                {'#','.','.','#','.','#','.','#','.','#','.','#'},
                {'#','#','.','#','.','#','.','#','.','#','.','#'},
                {'#','.','.','.','.','.','.','.','.','#','.','#'},
                {'#','#','#','#','#','#','.','#','#','#','.','#'},
                {'#','.','.','.','.','.','.','#','.','.','.','#'},
                {'#','#','#','#','#','#','#','#','#','#','#','#'}};


		char[][] m2 = {{'#','#','#','#','#','#','#','#','#','#','#','#'},
                {'#','.','.','.','#','.','.','.','#','#','.','.'},
                {'#','.','#','.','.','.','#','.','.','.','.','#'},
                {'#','.','#','#','#','#','.','#','.','#','.','#'},
                {'#','.','.','.','#','#','.','.','.','.','.','#'},
                {'#','#','#','.','#','#','#','#','.','#','.','#'},
                {'.','.','.','.','.','.','.','.','.','.','#','#'},
                {'#','#','#','#','#','#','#','#','#','#','#','#'}};

		char[][] m3 = {{'#','#','#','#','#','#','#','#','#'},
                {'#','.','#','.','#','.','.','.','#'},
                {'#','.','.','.','#','.','#','#','#'},
                {'#','#','#','.','#','.','#','.','.'},
                {'.','.','.','.','.','.','#','.','#'},
                {'#','#','.','#','.','#','#','.','#'},
                {'#','.','.','#','.','#','.','.','#'},
                {'#','#','.','#','.','#','.','.','#'},
                {'#','#','#','#','#','#','#','#','#'}};
		
		
			do
			{
				
				System.out.println("Maze Solver");
				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.print("\nEnter Number: ");
				input = scanner.nextInt();
				if(input < 1 || input > 4)
				{
					System.out.println("Invalid Number!");
				}
			}while(input < 1 || input > 4);
		
			
			switch(input)
			{
				
				case 1:
					m = new Maze(m1, 2, 4);
				break;
				
				case 2:
					m = new Maze(m2, 6, 1);
				break;
				
				case 3:
					m = new Maze(m3, 4 , 3);
					
				break;
				
				case 4:
					m = new Maze();
				break;
				
			}	
			
			System.out.print(m.toString());
			MazeSolver ms = new MazeSolver(m, m.start, m.finish);
			ms.solve(0, ms.s);
			
			
		
	
	}
}
public class MazeSolver {
	int s;
	int f;
	Maze solveMaze;
	int x;
	int y;
	int unSolve=0;
	int size = solveMaze.Maze[0].length;
    boolean solved;
    boolean wall = false;
    int count=0;

	
	public MazeSolver(Maze m, int start, int finish)
    {
    	s=start;
    	f=finish;
    	solveMaze = m;
    }

	public void solve(int x, int y) 
	{
        if (x==size && y==f) 
        {
            solved = true;
        }
        solveMaze.Maze[x][y] = 'x';
        
        if (solveMaze.Maze[x + 1][y] == '.') 
        {
            solve(x + 1, y);
            count++;
        }
        else if (solveMaze.Maze[x][y + 1] == '.') 
        {
            solve(x, y + 1);
            count++;
        }
        else if (solveMaze.Maze[x - 1][y] == '.') 
        {
            solve(x -1, y);
            count++;
        }
        else if (solveMaze.Maze[x][y-1] == '.') 
        {
            solve(x, y - 1);
            count++;
        }
        else 
        {
            wall = true;
        }
        if (wall) 
        {
            wall = false;
            solve(x, y);
        }
        if (solved)
        {
        	System.out.print("solved");
        }
        
        



        
	}
	
}
public class Maze {

	char Maze[][];
	public int start;
	public int finish;
	
	
	public Maze(char[][] m, int s, int f)
	{
		Maze= m;
		start=s;
		finish=f;
	}
	public Maze() 
	{
		
		
	}
	
	private char[][] createMaze() {

		return null;
	}
	public String toString()
	{
	    String output="";
	    for (int i=0; i<Maze.length; i++)
	    {
	    	for (int j =0; j<Maze[i].length; j++)
	    	{
	    		if(j==0)
	    		{
	    			output += "\n";
	    			
	    		}
	    		output += Maze[i][j];
	    	}
	    }
		return output;
	}

}

Can anyone help with the errors?

Member Avatar for ztini

I didn't compile your code, but I suspect its something to do with this:

boolean solved;

        if (x==size && y==f) 
        {
            solved = true;
        }
        
        if (solved)
        {
        	System.out.print("solved");
        }

What happens when the following resolves as false?

if (x==size && y==f)

your boolean solved is never instantiated. Add a default value. Such as:

boolean solved = false;

I am still having this problem and the error as i am working on the same program, can anyone please help me figure it out.

Yes, people will help. You need to explain exactly what help you need...

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.