In this project, you will:

$-$ Complete the code to solve a maze

$-$ Discuss related data structures topics

Programming

$---------------------------------$

from arraystack import ArrayStack

from grid import Grid

BARRIER $=\text{'}-\text{'}$ # barrier

FINISH $=\text{'}$F$\text{'}$ # finish $($goal$)$

OPEN $=\text{'}$O$\text{'}$ # open step

START $=\text{'}$S$\text{'}$ # start step

VISITED $=\text{'}$#$\text{'}$ # 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 solution:"$)$

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$,\text{'}$r$\text{'})$

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$($startRow$,$ startColumn, maze$)$:

# The exploration stack contains tuples of $($row$,$ column$)$ coordinates of

# grid cells on the frontier of the maze solution exploration.

exploreStack $=$ ArrayStack$()$

exploreStack.push$(($startRow$,$ startColumn$))$

while not exploreStack.isEmpty$()$:

$($row$,$ column$)=$ exploreStack.pop$()$

if maze$[$row$][$column$]==$ FINISH:

# Restore start cell to its original label:

maze$[$startRow$][$startColumn$]=$ START

removeDeadEnds$($maze$)$

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

# Changes visited, dead end cells to be open.

def removeDeadEnds$($maze$)$:

while True:

deadEndCount $=0$

for row in range$($maze$.$getHeight$())$:

for column in range$($maze$.$getWidth$())$:

if $($isDeadEnd$($row$,$ column, maze$))$:

maze$[$row$][$column$]=$ OPEN

deadEndCount $+=1$

if $($deadEndCount $==0)$:

return

# A dead end cell is a visited cell that:

# $-$ is not the start cell

# $-$ is not the finish cell

# $-$ has less than $2$ visited$/$start$/$finish$,$ compass direction $($N$/$S$/$E$/$W$)$ neighbor cells

def isDeadEnd$($row$,$ column, maze$)$:

if maze$[$row$][$column$]!=$ VISITED:

return False

if maze$[$row$][$column$]==$ START:

return False

if maze$[$row$][$column$]==$ FINISH:

return False

numberOfVisitedNeighbors $=0$

# Check north:

if $($row $!=0)$ and $($maze$[$row $-1][$column$]$ in $($VISITED$,$ START, FINISH$))$:

numberOfVisitedNeighbors $+=1$

# Check south:

if $($row $+1!=$ maze.getHeight$())$ and $($maze$[$row $+1][$column$]$ in $($VISITED$,$ START, FINISH$))$:

numberOfVisitedNeighbors $+=1$

# Check east:

if $($column $+1!=$ maze.getWidth$())$ and $($maze$[$row$][$column $+1]$ in $($VISITED$,$ START, FINISH$))$:

numberOfVisitedNeighbors $+=1$

# Check west:

if $($column $!=0)$ and $($maze$[$row$][$column $-1]$ in $($VISITED$,$ START, FINISH$))$:

numberOfVisitedNeighbors $+=1$

if $($numberOfVisitedNeighbors $<mtext\; id="EditorElement\_3454621"></mtext><mn\; id="EditorElement\_3454622">2</mn><mi\; id="EditorElement\_3454623">)</mi>$:

return True

return False

main$()$