In this project, you will: - Complete the code to solve a maze - Discuss related data structures topics

Programming -------------------------------------------------------------------------------------------- In this part, you will complete the code to solve a maze.

Begin with the "solveMaze.py" starter file. This file contains comment instructions that tell you where to add your code.

Each maze resides in a text file (with a .txt extension). The following symbols are used in the mazes: BARRIER = '-' # barrier FINISH = 'F' # finish (goal) OPEN = 'O' # open step START = 'S' # start step VISITED = '#' # visited step

There are 4 mazes you can use to test your code: maze1.txt maze2.txt maze3.txt maze4.txt The instructor may use other mazes to test your code.

""" Determines the solution to a maze problem. Uses a grid 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

______________________________________________________________________________

ADD CODE TO THIS FILE: (place to put code is in bold.)

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 sysmbol.") 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: # return False

main()