JAVA You are required to solve the 3 problems exactly as indicated below. I will

Question

JAVA

You are required to solve the 3 problems exactly as indicated below. I will not accept any solution other than by following the instructions below, even if they are correct.

A Maze is given as N*N binary matrix of cells where source cell is the upper leftmost? cell i.e., maze[0][0] and destination cell is lower rightmost block i.e., maze[N-1][N-1]. A mouse starts from the source and tries to reach the destination by moving in one of possible four directions. The mouse can move one cell above, right, left, or below, provided that cell is safe to go. It cannot move diagonally. This maze can be represented by a 2d matrix as 1’s and 0’s, where 1 represents safe to go and 0 represents unsafe (no go). The goal is for the mouse to go to the destination from the source by only using safe cells.

Gray cells are unsafe (value = 0).

Following is the matrix representation of the above maze.

{1, 0, 0, 0}

{1, 1, 0, 1}

{0, 1, 0, 0}

{1, 1, 1, 1}

A solution to the maze problem is a mouse trail which captures all the cells that the mouse attempts to navigate through to reach the destination. It does not have to be the shortest way. For instance, one mouse trail solution for the above maze is { (0,0), (1,0),(1,1),(2,1),(3,1),(3,0),(3,2),(3,3)} and another one is { (0,0), (1,0),(1,1),(2,1),(3,1),(3,2),(3,3)}. Both are good and correct, even though the second one is shorter. Your solution should work for all mazes of size N x N where N>=4. Notice that the maze problem may not have a solution – for instance, if all of the cells of row 2 are unsafe, the mouse cannot get to the destination.

Problem 1: Your Java code will print out any one mouse trail if there is a solution, otherwise, it should print “no solution”. In this you will use iterative (non-recursive) algorithm as the basis using an explicit Stack<..> from Java.util.* package.

Problem 2: Your Java code will print out any one mouse trail if there is a solution, otherwise, it should print “no solution”. In this you will use a recursive algorithm as the basis. Notice that the above website has a solution to the recursive version albeit it does not work for the general case we have here. You are welcome to get some ideas from the website or simply modify the code from Problem 1 to solve it recursively.

Explanation / Answer

Please find my implementation:

/* This program solves MAZE problem
   backtracking */
public class Maze
{
final int N = 4;
    /* For printing the 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();
        }
    }

    /* to check if whether direction x,y are valid*/
    boolean isSafe(int maze[][], int x, int y)
    {
        // if (x,y outside ) return false
        return (x >= 0 && x < N && y >= 0 &&
                y < N && maze[x][y] == 1);
    }
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;
    }

    /* 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;

            /* Backtrack*/
            sol[x][y] = 0;
            return false;
        }
         return false;
    }
    public static void main(String args[])
    {
        Maze rat = new Maze();
        int maze[][] = {{1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {1, 1, 1, 1}
        };
        rat.solveMaze(maze);
    }
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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