Chapter 13, Problem 8PP

Program Plan Intro

To solve the maze escape problem

Program plan:

• In the file “PartialSolution.java”, create an interface “PartialSolution”,
  • Create an interface that creates a partial solution to a backtracking problem.
  • Declare a method “examine()” that examines a partial solution.
  • Declare a method “extend()” that yields all extensions of this partial solution.
• In the file “Location.java”, create a class “Location”,
  • Declare the variables.
  • Define the constructor.
  • Define a method “getRow()” to get the row of this location.
  • Define a method “getColumn()” to get the column of this location.
  • Define a method “toString()” to print the formatted string.
  • Define a method “equals()” to check for equal location.
• In the file “Maze.java”, create a class “Maze”,
  • Declare the two-dimensional array variable.
  • Define the constructor to construct a maze from a string describing its contents.
  • Define a method “emptyNeighbors()” to empty neighbors.
  • Define a method “isExit()” to check whether a location is an exit.
  • Define a method “isValid()” to check whether a location is within the maze.
  • Define a method “isEmpty()” to check whether a location is within the maze and not a wall.
• In the file “MazePartialSolution.java”, import necessary package, and create a class “MazePartialSolution”,
  • Declare necessary variables.
  • Define default and parameterized constructor.
  • Define a method “examine” to examine a partial solution.
  • Define a method “extend()” to yield all extensions of this partial solution.
  • Define a method “toString()” to return formatted string.
• In the file “Solver.java”, create a class “Solver” that solves any problem using backtracking,
  • Define a method “solve()” to print all solutions to the problem that can be extended from a given partial solution.
• In the file “MazeSolver.java”, import necessary packages, and create a class “MazeSolver”,
  • Define the method “main()”,
    • Create an object for “Maze”.
    • Call the method “solve()”.