Determines the solution to a maze problem. Uses a gid to represent the maze. Thi
ID: 3859022 • Letter: D
Question
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 "<your code>" 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:
# <your code>
# Prints the maze with no spaces between cells.
def printMaze(maze):
# Part 2:
# <your code>
# (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:
# <your code>
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))
Explanation / Answer
1) Discuss the structure, behavior, and practical uses of the two data
structures (grid and stack) used in our maze solving program.
a) Grid
Grid data structure is a matrix m x n. It has getHeight, getWidth functions to return number of rows and columns
To access to a cell in grid, use 2 indexes, 1 for row and another for column
b) Stack data structure has push and pop functions to add data and retreive data. Each element of the stack is a tuple of
row and column to indicate the position in the maze.
2) Discuss the space and time efficiencies of the stack-based backtracking
algorithm used in our maze solving program.
Stack-based backtracking reduces the search space because it marks VISITED solution so there will be no duplicate
Backtracking using stack is time efficient because it can go back immediately (by using pop) at the alternative solution.
3) Discuss how you could use a graph data structure to represent and solve a maze.
We consider a graph connected by Start step, Finish step and Open steps. Using Depth-First Search on this graph (with stack
implementation) we can answer that if there a path from Start step to Finish step. If yes, the maze is solved. If no, the maze
cannot be solved.
-----------
Solvemaze.py
"""
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 "<your code>" 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 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:
# <your code>
rows = maze.getHeight()
cols = maze.getWidth()
for row in range(rows):
for col in range(cols):
if maze[row][col] == 'S':
return (row, col)
return -1, -1
# Prints the maze with no spaces between cells.
def printMaze(maze):
# Part 2:
# <your code>
rows = maze.getHeight()
cols = maze.getWidth()
for row in range(rows):
for col in range(cols):
print(maze[row][col], sep=' ', end="")
print(" ")
# (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:
# check upper cell
adjRow = row - 1
adjCol = column
if adjRow >= 0:
if maze[adjRow][adjCol] != '-' and maze[adjRow][adjCol] != '#':
stack.push((adjRow, adjCol))
# check lower cell
adjRow = row + 1
adjCol = column
if adjRow < maze.getHeight():
if maze[adjRow][adjCol] != '-' and maze[adjRow][adjCol] != '#':
stack.push((adjRow, adjCol))
# check right cell
adjRow = row
adjCol = column + 1
if adjCol < maze.getWidth():
if maze[adjRow][adjCol] != '-' and maze[adjRow][adjCol] != '#':
stack.push((adjRow, adjCol))
# check left cell
adjRow = row
adjCol = column - 1
if adjCol >= 0:
if maze[adjRow][adjCol] != '-' and maze[adjRow][adjCol] != '#':
stack.push((adjRow, adjCol))
return False
main()
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.