Given a grid maze similar to the following 1 1 1 1 1 1 1 0 1

Given a grid maze similar to the following: 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 1 3 4 7 9 design an algorithm and give the pseudo code to step through the maze starting at position (1, 1) and get to position (xMax -1, yMax -l). Remember to keep it generic, so don\'t use the example\'s dimensions in favor of xMax and yMax. Show that your algorithm works by tracing its steps, using the example maze for your demonstration. robot\' knows x, y position and facing(North, South, East, or West) Commands given in class: isWallInFront (abbreviated isWall) returns Tif there is a wall in the next space in the facing direction, otherwise F. at Destination returns Tif x,y position(xMax-1, yMax -1), otherwise F turnLeft (abbreviated TL) changes facing 90 degrees counter-clockwise. tumRight (abbreviated TR) changes facing 90 degrees clockwise. moveForward (abbreviated Move or Step) changes the x,y position by 1 in the facing direction. if (condition) If the condition is true, do what is in the brackets, no loopback. while (condition) If the condition is true, do what is in the brackets and loopback.

Solution

We can solve this problem using recursion. 1. Base Case : Stop when atDestination() is True. 2. Recursive Part : Subproblems. Let\'s assume that there is some algorithm that finds a path from starting point in maze to the goal, call it FindPath(x, y) We need to call the function FindPath(x,y) recursively to adjacent cells of our \'current cell\'. For example: FindPath( x, y - 1) //TOP DIRECTION FindPath(x+1, y) //RIGHT DIRECTION FindPath(x, y+1) //BOTTOM FindPath(x-1,y) //LEFT. In this way we can call FindPath from any location in maze to it\'s adjacent locations. You can convert this into \'turnRight() and turnLeft()\' easily. But, for better understanding let\'s stick with Top,Right,Bottom and Left for now. Note: There are other base cases as well: 1) Invalid location : Does the position go out of the bounds of maze? (Ex: x=-1, y=-1) 2) Inaccessible location : Can we go to the location or is it blocked by wall. All these are base cases along with our final destination. Now, in the algorithm we MARK the positions that we are trying but UNMARK the ones that we tried but failed to reach the path to destination. ================================================================================= ALGORITHM: FindPath(x, y) { //BASE CASES if (x,y is invalid location i.e. outside the maze) return false; if (x,y is atDestination) return true; //yay ! we solved the maze if (x,y is inaccessible location i.e. blocked by wall) return false; //mark can be anything, say setting cell value to specific value such as \'+\' MARK x,y as part of solution path if (FindPath(TOP of x,y) == true) return true if (FindPath(RIGHT of x,y) == true) return true if (FindPath(BOTTOM of x,y) == true) return true if (FindPath(LEFT of x,y) == true) return true //if didn\'t find path unmark x,y as part of solution path return false } This is a basic recursive algorithm you can use to find a solution to a maze. Replace your methods wherever necessary. For example: 1. TOP = turn left once (if robot was moving east initially) 2. Inaccessible location is checked by method Wall(); etc. A simple run of this algorithm on the example provided will go as: FindPath (1,1); // Mark this with + FindPath(TOP) //not true as inaccessible location //Goes back and resumes operation //This step is called \"BACKTRACKING\" //Recursion allows us to backtrack to previous path FindPath(RIGHT) // true ..now current location is (1,2) and is marked with + FindPath(TOP) // inaccessible FindPath (RIGHT) // (1,3) marked with + FindPath (TOP) //inaccessible FindPath (RIGHT) // (1,4) marked with + FindPath (TOP) //false FindPath (RIGHT) //(1,5) marked with + FindPath (TOP) // false FindPath (RIGHT) // false FindPath (BOTTOM) // (2,5) marked with + and so on.. Please note the backtracking. When function returns with false, it returned back to the previous called function i.e. resumed callee\'s operation. In other words, it \"backtracked\" and resumed its operation of searching a path.