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

    Join Date
    Jul 2012
    Posts
    8
    Rep Power
    0

    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:
    Code:
    mazeFile="sampleMaze.txt"
    m=[]
    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]
        m.append(row)
    
    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
        else:
            return False
    
    def mazeSolver(m):
        solution = findStart(m)
        print solution
        if (solveMaze(m, solution)):
            print solution
        else:
            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)):
            solution.pop()
            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