Need help with my JAVA programming homework! Thanks Solve for a path through a T

Question

Need help with my JAVA programming homework! Thanks

Solve for a path through a Two-Dimensional maze by use of exhaustive search and backtracking.

Given a two-dimensional array like the one shown below, create a recursive Java program that will traverse the array looking for a path from the upper left corner to the lower right.

private int[][] grid = { {1,1,1,0,1,1,0,0,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1,0,0,1},
{0,0,0,0,1,0,1,0,1,0,1,0,0},
{1,1,1,0,1,1,1,0,1,0,1,1,1},
{1,0,1,0,0,0,0,1,1,1,0,0,1},
{1,0,1,1,1,1,1,1,0,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1}};

Program specifications:

In the maze, values represented are:

- 1 – An available space for a path (an open ‘room’)

- 0 – A‘wall’

- 3 – A visited room

- 7 – A room on a successful path

Your program should:

Start in the upper left corner

Attempt to move in a direction

- Check that the ‘room’ you want to move into is inside the maze

- Check that the room you want to move to is available (not a wall)

- Check that the room you want to move to has not been visited previously

If the move is not valid try to move in another direction

If the is valid, ‘move’ into the ‘room’ and mark it as ‘visited’ (3)

If no valid move is available, unwind in your recursive call stack to the previous call and try the next direction from there

Repeat until either you’ve reached the goal or you’ve determined that there is no path through the maze.

Some suggestions:

Determine what the base cases will be

Your recursive method should return a variable of type boolean.

Your recursive method’s signature should accept two parameters only.

Explanation / Answer

public class HelloWorld{
final int M = 13;
final int N = 8;
  
void printSolution(int sol[][])
{
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
System.out.print(" " + sol[i][j] +
" ");
System.out.println();
}
}
  
// check weather the value of x,y index is valid.
boolean isSafe(int grid[][], int x, int y) // if (x,y outside maze) return false
{
return (x >= 0 && x < M && y >= 0 &&
y < N && grid[x][y] == 1);
}
  
boolean solveMaze(int grid[][])
{
int sol[][] = {{0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0}
};

if (solveMazeUtil(grid, 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 grid[][], int x, int y,int sol[][])
{
// if (x,y is goal) return true
if (x == M - 1 && y == N - 1)
{
sol[x][y] = 1;
return true;
}

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

System.out.println(" "+x+" "+y); // just checking the position of x,y

/* Move forward in x direction */
if (solveMazeUtil(grid, x + 1, y, sol))
{ return true; }
  
/* If moving in x direction doesn't give
solution, then Move down in y direction */
if (solveMazeUtil(grid, 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){
System.out.println("Hello World");
HelloWorld rat = new HelloWorld();
int[][] grid ={ {1,1,1,0,1,1,0,0,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1,0,0,1},
{0,0,0,0,1,0,1,0,1,0,1,0,0},
{1,1,1,0,1,1,1,0,1,0,1,1,1},
{1,0,1,0,0,0,0,1,1,1,0,0,1},
{1,0,1,1,1,1,1,1,0,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1}};
rat.solveMaze(grid);
}
}

Result: Solution doesn't exist as we are not supposed to move in a room that has been visited previously.

Base cases:

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

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