Implement in Java . Also post the JUnit test case. DFS and BFS for the solution of MAZE .

Generating a Maze:

To generate a maze, first start with a grid of rooms with walls between them. The grid contains r

rows and r columns for a total of r*r rooms. For example, Figure 1 is a 4x4 grid of 16 rooms. The

missing walls at the top left and bottom right of the maze border indicate the starting and finishing

rooms of the maze.

Our objective here is to create a perfect maze (see Figure 3), the simplest type of maze for a

computer to generate and solve. A perfect maze is defined as a maze which has one and only one

path from any point in the maze to any other point. This means that the maze has no inaccessible

sections, no circular paths, no open areas.

Now, begin removing interior walls to connect adjacent rooms. The difficultly in generating a perfect

maze is in choosing which walls to remove. Walls should be removed to achieve the following maze

characteristics:

1. Randomized: To generate unpredictable different mazes, walls should be selected randomly

as candidates for removal.

2. Single solution: There should be only one path between the starting room and the finishing

room (for simplicity always use as starting and finishing rooms the ones in Figure 1, i.e. ,

starting the upper left room and finishing the lower right room) . Unnecessarily removing too

many walls will make the maze too easy to solve. Therefore, a wall should not be removed if

some other path already connects the two rooms on either side of the wall. For example, in

2

Figure 2, the wall between a and f should not be removed because walls have previously

been removed that create a path between a and f through b, c, d, e.

3. Fully connected: Enough walls must be removed so that every room (therefore also the

finishing room) is reachable from the starting room. There must be no rooms or areas that

are completely blocked off from the rest of the maze.

We now give a simple maze generation algorithm and that uses Depth First Search. Here's the DFS

algorithm written as pseudocode:

create a CellStack (LIFO) to hold a list of cell locations

set TotalCells= number of cells in grid

choose the starting cell and call it CurrentCell

set VisitedCells = 1

while VisitedCells

find all neighbors of CurrentCell with all walls intact

if one or more found choose one at random

knock down the wall between it and CurrentCell

push CurrentCell location on the CellStack

make the new cell CurrentCell

add 1 to VisitedCells

else

pop the most recent cell entry off the CellStack

make it CurrentCell

Note that we can eliminate recursion by the use of a stack (this DFS implementation differs from the

one we have seen in class).

When the while loop terminates, the algorithm is completed. Every cell has been visited and thus no

cell is inaccessible. Also, since we test each possible cell to see if we've already been there, the

algorithm prevents the creation of any open areas, or paths that circle back on themselves.

After generating a maze, your program should solve the maze (find a path from the starting room to

the finishing room)

1. using DFS and

2. using BFS.

3

Each search algorithm will begin at the starting room and search for the finishing room by traversing

wall openings. The search should terminate as soon as the finishing room is found. For each search

algorithm, you will output the order in which rooms where visited and indicate the shortest solution

path from starting to finishing room.

Input: The program should accept the number of rows and columns r of the maze (use only r=4, 5,

6, 7, 8, 10).

Output: The program should print the maze, then the DFS solution, then the BFS solution

Figure 1 Figure 2 Figure 3 Figure 1 Figure 2 Figure 3