Determines the solution to a maze problem. Uses a gid to represent the maze. This grid is input from a text file. Uses a stack-based backtracking algorithm.

Replace any "" comments with your own code statement(s) to accomplish the specified task. Do not change any other code.

The following files must be in the same folder: abstractcollection.py abstractstack.py arrays.py arraystack.py grid.py """

from arraystack import ArrayStack from grid import Grid

BARRIER = '-' # barrier FINISH = 'F' # finish (goal) OPEN = 'O' # open step START = 'S' # start step VISITED = '#' # visited step

def main(): maze = getMaze() print("The maze:") printMaze(maze) (startRow, startCol) = findStartPosition(maze) if (startRow, startCol) == (-1, -1): print("This maze does not have a start symbol.") return success = solveMaze(startRow, startCol, maze) if success: print("Maze solved:") printMaze(maze) else: print("There is no solution for this maze.") def getMaze(): """Reads the maze from a text file and returns a grid that represents it.""" name = input("Enter a file name for the maze: ") fileObj = open(name, 'r') firstLine = list(map(int, fileObj.readline().strip().split())) rows = firstLine[0] columns = firstLine[1] maze = Grid(rows, columns) for row in range(rows): line = fileObj.readline().strip() column = 0 for character in line: maze[row][column] = character column += 1 return maze

# Returns a tuple containing the row and column position of the start symbol. # If there is no start symbol, returns the tuple (-1, -1) def findStartPosition(maze): # Part 1: #

# Prints the maze with no spaces between cells. def printMaze(maze): # Part 2: # # (row,column) is the position of the start symbol in the maze. # Returns True if the maze can be solved or False otherwise. def solveMaze(row, column, maze): # States are tuples of coordinates of cells in the grid. stack = ArrayStack() stack.push((row, column)) while not stack.isEmpty(): (row, column) = stack.pop() if maze[row][column] == FINISH: return True if maze[row][column] == VISITED: continue

# Cell has not been visited. # Mark it as visited. maze[row][column] = VISITED # Push adjacent unvisited positions onto the stack: # Part 3: #

main()

Guidance

=======================

Part 1 ------ See the comments provided above the findStartPosition() function. The parameter maze is of type Grid. Refer to the grid.py file in the Textbook Collections Framework files.

Part 2 ------ See the comments provided above the printMaze() function. The parameter maze is of type Grid. Refer to the grid.py file in the Textbook Collections Framework files. The default behavior for printing a Grid inserts a space between each column. You look at the __str__() function in grid.py to see why this happens. You can model your code somewhat after the code in __str__().

Part 3 ------ You need to examine the 4 maze cells that are one step away and perpendicular from the current row and column. They are the steps that are immediately to the north, south, east, and west of the current cell. For each of these cells: Make sure you do not use an invalid grid row or column index. If the cell contents is neither BARRIER nor VISITED, push the cell's row and column indexes as a tuple on the backtracking stack. Here is a sample syntax: stack.push((some row index, some column index))