5 10 1 1 5 10 --------------------- | | | | |-+-+-+ +-+-+ + + +-| | | | | | | |-+-+-+-+ +-+-+-+ + | | | | | | | |-+-+ + + + +-+ +-+-| | | | | |-+ +-+ +-+-+-+ +-+ | | | | | ---------------------...

Python3Maze with recursion and backtracking.Please use the psuedo code for backtrackingNo libraries1 maze class


5 10 1 1 5 10 --------------------- | | | | |-+-+-+ +-+-+ + + +-| | | | | | | |-+-+-+-+ +-+-+-+ + | | | | | | | |-+-+ + + + +-+ +-+-| | | | | |-+ +-+ +-+-+-+ +-+ | | | | | --------------------- Lab6CMPT200 We require two specific functions (use these names!) that we can run your solver with: 1. main(), for launching your single solution solver where you get two lines of input. The first is the search order that is to be used by your solver. This line will be the four characters, NSWE, in any order. They specify the order in which your search is to proceed from any given square in the maze; N=up, S=down, W=left, E=right, if you prefer. (This is necessary to ensure that if there are multiple paths, your solution and ours will agree.) The second line will be a filename from the user 2. test(), that will run through all of the test mazes that we have provided to you and report either the solution, that there is no solution, or that your program fails on that maze. Format for input by filename: Input: For the main() function, you are to prompt the user for the search directions and then an input file containing a maze (format below). If the user enters an empty string for the file name, 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. Maze 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). Example maze file: 10 20 1 1 10 20 ----------------------------------------- | | | | | | | | | | |-+ +-+-+ +-+ + +-+ + + +-+-+ +-+-+ + + | | | | | | | | | | | | + +-+ + + +-+-+-+ + + + + + +-+ + + + | | | | | | | | | | | | | +-+-+-+-+ +-+ +-+-+-+-+ +-+ + +-+-+ +-| | | | | | | | | | | | | + + +-+ +-+-+ + + + +-+ +-+ + + + +-+ | | | | | | | | | | | | | |-+-+ +-+-+-+-+-+-+-+ +-+ +-+-+ +-+-+ +-| | | | | | | | | | | | | | +-+-+ +-+-+ +-+ + +-+-+ +-+ +-+ + + + | | | | | | | | | | | | |-+ +-+ + + +-+ +-+-+ + +-+ + + +-+ +-+ | | | | | | | | | | | | | | | | | | |-+ + +-+ + + + + + +-+ + + + + +-+-+ + | | | | | | | | | | + + +-+ + +-+-+-+ + +-+ + + +-+-+ +-+ | | | | | | | | | | | | ----------------------------------------- Pseudo-Code for Recursive Backtracking Solver(partialSoln): if partialSoln is complete: return Success else: while (partialSoln can be advanced with X): partialSoln += X # Advance the partial solution result = Solver(partialSoln) if result == Success: return Success else:# Retreat to original partial solution; try again partialSoln -= X # if we get here, no solution was possible using this # partial solution, so return and backtrack return False 1 1 1 5 10 1 1 5 10 --------------------- | | | | |-+-+-+ +-+-+ + + +-| | | | | | | | +-+-+ + +-+-+-+ + | | | | | | | |-+-+ + + + +-+ +-+-| | | | |-+ +-+-+-+-+-+ +-+ | | | | | ---------------------
Mar 23, 2021
SOLUTION.PDF

Get Answer To This Question

Related Questions & Answers

More Questions ยป

Submit New Assignment

Copy and Paste Your Assignment Here