The following grid is a double-subscripted array representation of a maze. The #

Question

The following grid is a double-subscripted array representation of a maze. The # symbols represent the walls of the maze, and the periods (.) represent squares in the possible paths through the maze. There's a simple algorithm for walking through a maze that guarantees finding the exit (assuming there's an exit). If there's not an exit, you'll arrive at the starting location again. Place your right hand on the wall to your right and begin walking forward. Never remove your hand from the wall. If the maze turns to the right, you follow the wall to the right. As long as you do not remove your hand from the wall, eventually you arrive at the exit of the maze. There may be a shorter path than the one you have taken, but you're guaranteed to get out of the maze. Write recursive function maze Traverse to walk through the maze. The function should receive as arguments a 12-by-12 character array representing the maze and the starting location of the maze. As maze Traverse attempts to locate the exit from the maze, it should place the character X in each square in the path. The function should display the maze after each move so the user can watch as the maze is solved.

Explanation / Answer

The functions required in the question are all stated in this testing program which consists of the solution of the maze using the Recursion Backtracking method and hence, using this method is the best available option in solving the maze fast and less efforts. Hence, the code goes as below:

As, you have not stated the programming language required I decided to give the solution for this in JAVA as it is the strongest of me.

MazeTraversal.java

public class MazeTraversal
{
   final int number = 4;

   // Function for printing the solution of the chaar
   void dispSoln(int solutions[][])
   {
       for (int uu = 0; uu < number; uu++)
       {
           for (int qq = 0; qq < number; qq++)
               System.out.print(" " + solutions[uu][qq] +
                               " ");
           System.out.println();
       }
   }

   /* Function to check whether the xdir , ydir are valid for the chaar
   boolean isRight(int chaar[][], int xdir, int ydir)
   {
       // if (xdir,ydir outside chaar) return false
       return (xdir >= 0 && xdir < number && ydir >= 0 &&
               ydir < number && chaar[xdir][ydir] == 1);
   }

   // This is the mazeTraversal function which solves the chaar using the BACKTRACK Recursion Technique
  
   boolean CheckSolutions(int chaar[][])
   {
       int solutions[][] = {{0, 0, 0, 0},
           {0, 0, 0, 0},
           {0, 0, 0, 0},
           {0, 0, 0, 0}
       };

       if (solvingMazeInDir(chaar, 0, 0, solutions) == false)
       {
           System.out.print("Solution doesn't exist");
           return false;
       }

       dispSoln(solutions);
       return true;
   }

   // Function for solving the Maze Problem
  
   boolean solvingMazeInDir(int chaar[][], int xdir, int ydir,
                       int solutions[][])
   {
       if (xdir == number - 1 && ydir == number - 1)
       {
           solutions[xdir][ydir] = 1;
           return true;
       }

       // Checking condition for the chaar indexes
      
       if (isRight(chaar, xdir, ydir) == true)
       {
           //Marking xdir,ydir as the solution path
          
           solutions[xdir][ydir] = 1;
          
           // Moving forward in X direction
          
           if (solvingMazeInDir(chaar, xdir + 1, ydir, solutions))
               return true;

           //Moving in Y direction if X direction does not gives any path
          
           if (solvingMazeInDir(chaar, xdir, ydir + 1, solutions))
               return true;

           //Backtracking if none of the above conditions work
          
           solutions[xdir][ydir] = 0;
           return false;
       }

       return false;
   }

   public static void main(String args[])
   {
       MazeTraversal mz = new MazeTraversal();
       int chaar[][] = {{1, 0, 0, 0},
           {1, 1, 0, 1},
           {0, 1, 0, 0},
           {1, 1, 1, 1}
       };
       mz.CheckSolutions(chaar);
   }
}

Please rate the answer if it helped......Thankyou

Hope it helps....

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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