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

Question

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 "<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>

# 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>
    return False

main()

Explanation / Answer

MazeWidth% = 11 MazeHeight% = 9 MazeCell% = 50 VDU 23,22,MazeWidth%*MazeCell%/2+3;MazeHeight%*MazeCell%/2+3;8,16,16,128 VDU 23,23,3;0;0;0; : REM Line thickness OFF PROCgeneratemaze(Maze&(), MazeWidth%, MazeHeight%, MazeCell%) PROCsolvemaze(Path{()}, Maze&(), 0, MazeHeight%-1, MazeWidth%-1, 0, MazeCell%) END DEF PROCsolvemaze(RETURN s{()}, m&(), x%, y%, dstx%, dsty%, s%) LOCAL h%, i%, n%, p%, q%, w% w% = DIM(m&(),1) h% = DIM(m&(),2) DIM s{(w%*h%) x%,y%} GCOL 3,14 m&(x%,y%) OR= &80 REPEAT FOR i% = 0 TO 3 CASE i% OF WHEN 0: p% = x%-1 : q% = y% WHEN 1: p% = x%+1 : q% = y% WHEN 2: p% = x% : q% = y%-1 WHEN 3: p% = x% : q% = y%+1 ENDCASE IF p% >= 0 IF p% = 0 IF q% x% IF m&(p%,q%) AND 1 EXIT FOR IF q% > y% IF m&(p%,q%) AND 2 EXIT FOR IF x% > p% IF m&(x%,y%) AND 1 EXIT FOR IF y% > q% IF m&(x%,y%) AND 2 EXIT FOR ENDIF NEXT IF i% < 4 THEN m&(p%,q%) OR= &80 s{(n%)}.x% = x% s{(n%)}.y% = y% n% += 1 ELSE IF n% > 0 THEN n% -= 1 p% = s{(n%)}.x% q% = s{(n%)}.y% ENDIF ENDIF LINE (x%+0.5)*s%,(y%+0.5)*s%,(p%+0.5)*s%,(q%+0.5)*s% x% = p% y% = q% UNTIL x%=dstx% AND y%=dsty% s{(n%)}.x% = x% s{(n%)}.y% = y% ENDPROC DEF PROCgeneratemaze(RETURN m&(), w%, h%, s%) LOCAL x%, y% DIM m&(w%, h%) FOR y% = 0 TO h% LINE 0,y%*s%,w%*s%,y%*s% NEXT FOR x% = 0 TO w% LINE x%*s%,0,x%*s%,h%*s% NEXT GCOL 15 PROCcell(m&(), RND(w%)-1, y% = RND(h%)-1, w%, h%, s%) ENDPROC DEF PROCcell(m&(), x%, y%, w%, h%, s%) LOCAL i%, p%, q%, r% m&(x%,y%) OR= &40 : REM Mark visited r% = RND(4) FOR i% = r% TO r%+3 CASE i% MOD 4 OF WHEN 0: p% = x%-1 : q% = y% WHEN 1: p% = x%+1 : q% = y% WHEN 2: p% = x% : q% = y%-1 WHEN 3: p% = x% : q% = y%+1 ENDCASE IF p% >= 0 IF p% = 0 IF q% x% m&(p%,q%) OR= 1 : LINE p%*s%,y%*s%+4,p%*s%,(y%+1)*s%-4 IF q% > y% m&(p%,q%) OR= 2 : LINE x%*s%+4,q%*s%,(x%+1)*s%-4,q%*s% IF x% > p% m&(x%,y%) OR= 1 : LINE x%*s%,y%*s%+4,x%*s%,(y%+1)*s%-4 IF y% > q% m&(x%,y%) OR= 2 : LINE x%*s%+4,y%*s%,(x%+1)*s%-4,y%*s% PROCcell(m&(), p%, q%, w%, h%, s%) ENDIF NEXT ENDPROC

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.