1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2012
    Rep Power

    solving a maze with recursion. edit: sorry about the repost

    I have an assignment to write a function that will recursively solve a maze. It should return True if the maze is solvable and False if it is not. It should also record the solution, if there is one. The maze is a 2d list where S is the start, F is the finish, W is a wall, P is a cell you can move through, and any cell that's already been visited I have the function rewrite as v.

    I have written all the helper and wrapper functions necessary for my maze walking function, but am having trouble figuring out how to implement the recursion itself.

    In my mazeWalk function, the recursion isn't happening and I know I'm misunderstanding it. I think I have written all of the base cases correctly. Here is the link to the actual assignment: http://www.andrew.cmu.edu/course/15-112-n12/index/labs_index.html

    Here is my code so far:
    readMaze(m, mazeFile)
    def readMaze(m, mazeFile):
      mazeFile = open(mazeFile, "r")
      lines = mazeFile.readlines()
      for line in lines:
        line = line.strip()
        row = [c for c in line]
    def findStart(m):
        start =[]
        for row in xrange(len(m)):
            for col in xrange(len(m[row])):
                if m[row][col]== "S":
                    start = [[row,col]]
                    solution = start
        return solution
    def solveMaze(m, solution):
        solution = findStart(m)
        row = solution[-1][0]
        col = solution[-1][1]
        if mazeWalk(m, row, col, solution):
            return True
            return False
    def mazeSolver(m):
        solution = findStart(m)
        print solution
        if (solveMaze(m, solution)):
            print solution
            print "No solution found."
        #solveMaze(m, solution)
    def mazeWalk(m, row, col, solution):
        #current cell has to be the last row of the solution
        currentRow = solution[-1][0]
        currentCol = solution[-1][1]
        currentCell = m[currentRow][currentCol]
        print m[currentRow][currentCol]
        if currentCell == "F":
            return True
        if currentCell == "P":
            currentCell = "v"
            solution.append([row, col])
        if ((currentCell == "W"or "v")or currentRow<0 or 
            currentRow>(len(m)-1) or currentCol<0 or currentCol>(len(m[0])-1)):
            return False
        mazeWalk(m, row, col+1, solution)
        mazeWalk(m, row, col-1, solution)
        mazeWalk(m, row+1, col, solution)
        mazeWalk(m, row-1, col, solution)
    I asked my TA, but she gave me some vague answer that didn't make much sense to me so I was hoping someone could point me in the right direction. Thanks a lot.
    Last edited by pacgcrosss; July 20th, 2012 at 06:43 PM. Reason: Repost

IMN logo majestic logo threadwatch logo seochat tools logo