1. Implement the Depth First Search (DFS) traversal algorithm to find a solution

Question

1.Implement the Depth First Search (DFS) traversal algorithm to find a solution through your maze

a.Show the progression that the algorithm makes though the maze, including reaching dead ends and back tracking.

b.Indicate, at the end, the direct path that was found from the entrance to the exit, not including backtracking.

Project 7-Graphs-Word FILE HOME INSERT DESIGN PAGE LAYOUT REFERENCES MAILINGS REVIEW VIEW Haley, Thomas Dj Rules Match Fields Update Labels Find Recipient kCheck for Errors Envelopes Labels Start Mail Select Edit Insert Merge Highlight Address Greeting Insert Merge Preview Finish & Merge" Recipients-Recipient List Start Mail Merge Block Line Field- Write & Insert Fields Merge Fields Results Merge Create Preview Results Finish PROJECT(S) A. REPRESENT A MAZE AS A GRAPH a. Intersections, entrance and exits are the VERTICES of the graph and the corridors between them are the EDGES b. Read in a MAZE CONFIGURATION from a file (so you can test your program/algorithms with different configurations,) and store in an ADJACENCY LIST representation of a graph that you write yourself Karin Assiter, Ph.D Page 1 of 4 April 14, 2016 Wentworth Institute of Technology Computer Science Department c. Display the initial maze (how you display is up to you). Indicate, in some manner, the entrance and the exits. Entrance Exit Figure- Example from the text a) Maze b) Representation as a graph B. SEARCHING FOR SOLUTIONS PAGE 1 OF 4 1235 WORDS LX + 100% 10:32 AM 4/14/2016 O Ask me anything

Explanation / Answer

Please go through the code to get the expected output and the description can be found in the comments :

a)

public class Maze
{
final int N = 4;

/* A utility function to print solution matrix
sol[N][N] */
void printSolution(int sol[][])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
System.out.print(" " + sol[i][j] +
" ");
System.out.println();
}
}

/* A utility function to check if x,y is valid
index for N*N maze */
boolean isSafe(int maze[][], int x, int y)
{
// if (x,y outside maze) return false
return (x >= 0 && x < N && y >= 0 &&
y < N && maze[x][y] == 1);
}

/* This function solves the Maze problem using
Backtracking. It mainly uses solveMazeUtil()
to solve the problem. It returns false if no
path is possible, otherwise return true and
prints the path in the form of 1s. Please note
that there may be more than one solutions, this
function prints one of the feasible solutions.*/
boolean solveMaze(int maze[][])
{
int sol[][] = {{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};

if (solveMazeUtil(maze, 0, 0, sol) == false)
{
System.out.print("Solution doesn't exist");
return false;
}

printSolution(sol);
return true;
}

/* A recursive utility function to solve Maze
problem */
boolean solveMazeUtil(int maze[][], int x, int y,
int sol[][])
{
// if (x,y is goal) return true
if (x == N - 1 && y == N - 1)
{
sol[x][y] = 1;
return true;
}

// Check if maze[x][y] is valid
if (isSafe(maze, x, y) == true)
{
// mark x,y as part of solution path
sol[x][y] = 1;

/* Move forward in x direction */
if (solveMazeUtil(maze, x + 1, y, sol))
return true;

/* If moving in x direction doesn't give
solution then Move down in y direction */
if (solveMazeUtil(maze, x, y + 1, sol))
return true;

/* If none of the above movements work then
BACKTRACK: unmark x,y as part of solution
path */
sol[x][y] = 0;
return false;
}

return false;
}

public static void main(String args[])
{
RatMaze rat = new RatMaze();
int maze[][] = {{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
rat.solveMaze(maze);
}
}

b)

public int[][] generateMaze() {
int[][] maze = new int[height][width];
// Initialize
for (int i = 0; i < height; i++)
for (int j = 0; j < width; j++)
maze[i][j] = 1;

Random rand = new Random();
// r for rowc for column
// Generate random r
int r = rand.nextInt(height);
while (r % 2 == 0) {
r = rand.nextInt(height);
}
// Generate random c
int c = rand.nextInt(width);
while (c % 2 == 0) {
c = rand.nextInt(width);
}
// Starting cell
maze[r][c] = 0;

// Allocate the maze with recursive method
recursion(r, c);

return maze;
}

public void recursion(int r, int c) {
// 4 random directions
int[] randDirs = generateRandomDirections();
// Examine each direction
for (int i = 0; i < randDirs.length; i++) {

switch(randDirs[i]){
case 1: // Up
// Whether 2 cells up is out or not
if (r - 2 <= 0)
continue;
if (maze[r - 2][c] != 0) {
maze[r-2][c] = 0;
maze[r-1][c] = 0;
recursion(r - 2, c);
}
break;
case 2: // Right
// Whether 2 cells to the right is out or not
if (c + 2 >= width - 1)
continue;
if (maze[r][c + 2] != 0) {
maze[r][c + 2] = 0;
maze[r][c + 1] = 0;
recursion(r, c + 2);
}
break;
case 3: // Down
// Whether 2 cells down is out or not
if (r + 2 >= height - 1)
continue;
if (maze[r + 2][c] != 0) {
maze[r+2][c] = 0;
maze[r+1][c] = 0;
recursion(r + 2, c);
}
break;
case 4: // Left
// Whether 2 cells to the left is out or not
if (c - 2 <= 0)
continue;
if (maze[r][c - 2] != 0) {
maze[r][c - 2] = 0;
maze[r][c - 1] = 0;
recursion(r, c - 2);
}
break;
}
}

}

/**
* Generate an array with random directions 1-4
* @return Array containing 4 directions in random order
*/
public Integer[] generateRandomDirections() {
ArrayList<Integer> randoms = new ArrayList<Integer>();
for (int i = 0; i < 4; i++)
randoms.add(i + 1);
Collections.shuffle(randoms);

return randoms.toArray(new Integer[4]);
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.