Exercise 7 (Recursion, Backtracking) - Deadline is May 22nd

Find a way through a maze.

• Create a class Maze which reads a 2D maze from a text file.
• Provide a public constructor which has java.io.File as its argument.
• The file should contain an initial maze (see below).
• S defines the starting position.
• # defines the walls of the maze.
  
• Use a recursive backtracking approach like in the lecture (sum of subsets, 8 queens).
• You can move in 4 directions N,E,S,W. (Diagonal movements are not allowed.)
  
• Provide a public method to solve the maze. (Don't start the algorithm inside the constructor.)
  
• Override the method toString to return a string representation of the maze.
• This method should return the solved maze after running your algorithm.
• Use dots to draw the path which leads out of the maze.
  
• Provide a documentation (txt or pdf) which describes your implemented algorithm.
• Please provide JavaDoc comments for every class, method, field which is not private.
  (Except you implement/override an already documented method and your implementation conforms with the documentation.)
  

Example 1:
Initial Maze                Solved Maze
# S # # # # # # # # # #     # S # # # # # # # # # #
#   #                 #     # . # . . . . . . . . #       The space between two bricks # is
#       # # # # # #   #     # . . . # # # # # # . #       only for the sake of readability.
#   # # #             #     #   # # # . . . . . . #       In the input file there are no
#   #   #   # # # # # #     #   #   # . # # # # # #       spaces between two bricks.
#       #         #   #     #       # . . . . #   #       E.g.: #S#######
# # #   # # # #   #   #     # # #   # # # # . #   #             #.#.....#
#       #     #       #     #       #     # . . . #             #...###.#
#   #   # #   # # #   #     #   #   # #   # # # . #             #####...#
#             #       #     #             # . . . #             ......###
# # # # # # # #   # # #     # # # # # # # # . # # #             #########

Example 2:
Initial Maze                Solved Maze
# # # # # # # # # # # #     # # # # # # # # # # # #
#   #                 #     #   # . . . . . . . . #
#       # # # # # #   #     # . . . # # # # # # . #
#   # # #             #     # . # # # . . . . . . #
#   #   #   # # # # # #     # . #   # . # # # # # #
#       #         #   #     # . . . # . . . . #   #
# # #   # # # #   #   #     # # # . # # # # . #   #
#       #     #       #     #     . #     # . . . #
#   #   # #   # # #   #     #   # . # #   # # # . #
#       S     #       #     #     . S     # . . . #
# # # # # # # #   # # #     # # # # # # # # . # # #

Hints:

You can find information about reading, writing, and creating files at the following website:
https://docs.oracle.com/javase/tutorial/essential/io/file.html