maze using recursive backtracking solution

For this assignment you are to solve a maze using recursive backtracking (there are other approaches that would be possible, but your solution must use backtracking, implemented using recursion.) Input: You are to prompt the user for an input file containing a maze (format below). If the user enters an empty string, then read from the default file "maze.txt". Your program should check if the file exists. If not, print an appropriate error message and stop. Input File Format: The format of the input starts with a single line giving the number of rows and columns that make up the maze (in our example, there are 10 rows and 20 columns). However, the input needs to also indicate whether or not a room is connected to an adjacent room. As such, the input will also include additional rows and columns that contain walls ('|' and '-') that separate rooms or thresholds (spaces) that indicate two adjacent rooms are joined. Also included in the input is an external boundary around the maze. The next two lines give the starting room and the ending room. In our example, you need to find the path from the extreme lower left room to the extreme upper right room. Output: Your program is to output either a path through the maze (indicated using "*"s) or else a message that there is no path from the start to finish. Note: For full marks, your program must be able to handle mazes with cycles/islands (situations where you can go in circles). Deliverables: · One or more files (probably more) containing your python code that solves the problem. · A write-up (electronic) that describes the data structure you used to represent your maze internally and how you advanced your solution through the maze. (This part should include how you indexed rooms in your solution.) If your solution can handle mazes with cycles, describe how you accomplished this. This write-up should be no more than one or two pages. Example maze file: 10 20 1 1 10 20 ----------------------------------------- | | | | | | | | | |-+ +-+-+ + + + + + +-+ + + +-+-+ + + +-| | | | | | | | | | | | | | | +-+ +-+ +-+-+-+ + +-+ +-+-+ +-+ +-+ + | | | | | | | | | | | | +-+-+-+ +-+ + + +-+ +-+-+-+-+-+ + +-+ | | | | | | | | | | | | +-+ +-+ +-+-+-+ +-+ +-+-+ +-+ + +-+ + | | | | | | | | | | | |-+ + + +-+-+ + +-+ + + +-+-+-+-+-+ + +-| | | | | | | | | | | | |-+ + +-+ + + + + +-+-+ + +-+-+ +-+-+-+ | | | | | | | | | | | | | + + +-+-+ +-+-+ +-+ + + + + +-+ +-+-+ | | | | | | | | | | | | | |-+ + + +-+-+ +-+-+ + + + +-+-+ +-+-+-+ | | | | | | | | | | | | | | | | + +-+-+ + + +-+ + +-+-+-+ +-+-+ + + +-| | | | | | | | -----------------------------------------