• III. Maze Solver
  1. Go to https://www.cs.bu.edu/teaching/alg/maze/ and analyze the given algorithm
  2. Run the applet at the bottom of the page with the Algorithm box checked:
  3. Implement the following maze search algorithm using recursion, use MazeSolver.java as the starting point (please notice that our algorithm does not unmark [x,y] if it is not in the solution path):

FIND-PATH(x, y)

• if ([x,y] outside maze) return false
• if ([x,y] is goal) return true
• if ([x,y] not open) return false
• mark [x,y] as part of solution path
• if (FIND-PATH(North of x,y) == true) return true
• if (FIND-PATH(East of x,y) == true) return true
• if (FIND-PATH(South of x,y) == true) return true
• if (FIND-PATH(West of x,y) == true) return true
• return false

public class MazeSolver { private char[][] maze; public MazeSolver(char[][] grid) { setMaze(grid); } public void setMaze(char[][] grid) { this.maze = new char[grid.length][]; for (int r = 0; r < grid.length; r++) { this.maze[r] = new char[grid[r].length]; for (int c = 0; c < grid[r].length; c++) this.maze[r][c] = grid[r][c]; } } private boolean findPath(int r, int c) { // TODO Project #5  return false; // THIS IS A STUB } private boolean isInsideMaze(int r, int c) { // TODO Project #5  return false; // THIS IS A STUB } private boolean isGoal(int r, int c) { return (this.maze[r][c] == 'G'); } private boolean isOpen(int r, int c) { // TODO Project #5  // ., S, or G would be considered open return false; // THIS IS A STUB } 

public class MazeSolverWithStack { private char[][] maze; public MazeSolverWithStack(char[][] grid) { setMaze(grid); } public void setMaze(char[][] grid) { this.maze = new char[grid.length][]; for (int r = 0; r < grid.length; r++) { this.maze[r] = new char[grid[r].length]; for (int c = 0; c < grid[r].length; c++) this.maze[r][c] = grid[r][c]; } } private boolean findPath(int startRow, int startCol) { // TODO Project #6  boolean result = false; Stack stack = new Stack<>(); stack.push(new MazeFrame(startRow, startCol)); MazeFrame current = null; // when you pop from the stack check for the goal first // if not the goal: // try moving up (NORTH), next try moving right (EAST), // next try moving down (SOUTH), and finally try moving left (WEST) // push only valid moves on the stack return result; } private boolean isInsideMaze(int r, int c) { // TODO Project #6  return false; // THIS IS A STUB } private boolean isGoal(int r, int c) { return (this.maze[r][c] == 'G'); } private boolean isOpen(int r, int c) { // TODO Project #6  // ., S, or G would be considered open return false; // THIS IS A STUB }