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

    Join Date
    Jul 2012
    Posts
    8
    Rep Power
    0

    Help with python recursive maze solver


    Hi all. I have an assignment to write a program that solves a maze recursively. The maze is a 2D list. S is the start, W is a wall, F is the finish, and P is an allowed path. When I go through a cell, P, I have my function rewrite it as v so that I know I've already visited it. I also need to keep track of the solution.

    I have all the helper functions and wrapper functions written and ready to go but am having trouble implementing the recursion itself in my maze walking function. I think I did the base cases correctly. I asked the TA but she gave me some vague answer and would'nt explain any further and I'm stuck on how I should recursively call my mazeWalk function. Heres a link to the assignment itself: http://www.andrew.cmu.edu/course/15-112-n12/index/labs_index.html

    and heres my code so far, note the recursive calls at the bottom of my last function. I know they're incorrect but not really sure how to fix it.
    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)
    thanks a lot
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,703
    Rep Power
    480
    There are maze solvers at
    http://rosettacode.org/wiki/Maze_solving#Python
    I wrote the j and python versions.

    Following program solves your sample maze.
    Based on the DNA assignment, your professor prefers many tests. I've inserted assertions into the maze reading functionality. I considerably simplified, in my opinion, findStart.

    OK, how does a recursive function work?
    Code:
    def factorial(n):
        if n < 2:
            return 1
        return n*factorial(n-1)
    factorial first checks for an ending condition. If it finds an end condition it does not recurse. factorial always returns a value.

    Your mazeWalk did not always test the return value from recursive invocations, nor did it always choose a value to return. (Python functions always return a value. The value is None if you don't specifically choose a return value.)

    Code:
    import sys
    
    def mazeWalk(m,solution,row,col):       # depth first
    
        # python raises IndexError if out of bounds.
        # Since this is not the true path, return False
        try:
            c = m[row][col]
        except IndexError:
            return False
    
        # Finished?  Put these coordinates onto the solution list.
        # AND RETURN True
        if 'F' == c:
            solution.append((row,col,))
            return True
    
        # return False if current cell content is not on an untested path.
        if c not in 'PS':
            return False
    
        # mark the new site as visited, and continue looking
        m[row][col] = 'v'
    
        # Try all the possible directions (as necessary) from here.
        # Look up the python `or' function and practice to
        # understand short-circuit evaluation.
        # If the solution is found on this path,
        # prepend the current position to the solution list.
        # AND RETURN True
        if (   mazeWalk(m, solution, row+0, col+1,)
            or mazeWalk(m, solution, row+0, col-1,)
            or mazeWalk(m, solution, row+1, col+0,)
            or mazeWalk(m, solution, row-1, col+0,)):
    
            solution[:0] = [(row,col,)]
            return True
    
        # This cell is not on the path.  Return False.
        return False
    
    class Maze:
    
        def __init__(self,mazeFile):
            try:
                with open(mazeFile, "r") as mazeFile:
                    m = [line.strip() for line in mazeFile.readlines()]
            except:
                sys.stderr.write('\nRead failure, loading default maze\n')
                m = ['WPPWWW','WWPWPS','WWPWPW','PPPPPW','FWPWWW','WPPPPW',]
            # Your instructor likes assertions.  I like tests as well but prefer
            # doctest or unittest with python.
            assert 0 < len(m)
            # rectangular probably isn't actually important, test for it anyway.
            assert all(len(m[0])==len(row) for row in m),'Expect rectangular maze'
            M = ''.join(m)
            assert set('WPSF') == set(M),'Invalid maze definition'
            'Lambert Electronics, LLC.  USA, NY.'
            assert 1 == M.count('S'), 'maze must have exactly one start'
            assert 1 == M.count('F'), 'maze must have exactly one finish'
            self.solution = 'unsolved'
            self.Boolean = False
            self.maze = m
    
        def __str__(self):
            return '\n'.join(self.maze)
    
        def __nonzero__(self):
            return self.Boolean
    
        def findStart(self):
            '''
                this version returns a 2-tuple with the row and column of 'S' 
                and requires a rectangular maze
                The __init__ method already tested these properties.
            '''
            m = self.maze
            return divmod(''.join(m).index('S'),len(m[0]))
    
        def solve(self):
            maze = [[c for c in row] for row in self.maze]
            solution = []
            mazeWalk(maze, solution, *self.findStart())
            self.solution = 'No solution found'
            try:
                (r,c,) = solution[-1]
                if 'F' == self.maze[r][c]:
                    self.solution = solution
                    self.Boolean = True
            except:
                pass
    
    def main():
        if 1 < len(sys.argv):
            mazeFile = sys.argv[1]
        else:
            mazeFile = 'sampleMaze.txt'
        m = Maze(mazeFile)
        m.solve()
        print(m.solution)
    
    main()
    Last edited by b49P23TIvg; July 20th, 2012 at 11:53 PM. Reason: Insert `.'.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2012
    Posts
    8
    Rep Power
    0
    thanks so much for the reply b49, it was extremely useful. I understand all of the simple forms of recursion such as factorial, powers of 2, fibonacci numbers, etc.

    The reason I had my function laid out the way it is, is because we are only 3 weeks into our introductory python course and haven't been taught classes yet so I can't use them. I replaced my mazeWalk function with yours, and my program now returns the correct True or False, but the solution isn't recording itself correctly. When I tell it to print the solution at the end, the solution only contains the starting position twice. Why am I prepending the solution at the end of mazeWalk? thanks
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,703
    Rep Power
    480
    The maze class isn't worth much---it's stupid to have the object truth test __nonzero__() depend on whether you've asked for a solution. And then I realized that mazeWalk couldn't easily take advantage of the class, so it ended up as a separate function anyway. (I also used the maze class because it was pretty clear that you hadn't been introduced to classes yet and stealing my code is wrong.)

    Why prepend the solution? The homework hint said to append the point on the path after it was found to be on the path, which writes the path in backward order. Then the hint says to pop the values off the list onto a new list to reverse them. I skipped that step by prepending the solution. Alternatives, which are just now occurring to me are that you could present the result as
    reversed(solution)
    or solve the maze from finish to start.

    I have not figured out exactly what your current code is. Learn to use pdb, the python debugger.

    import pdb

    At the beginning of mazeWalk insert the extra statement
    Code:
        pdb.set_trace()
    emacs integrates the python debugger. Single stepping through the code, checking the values of variables is all easy, or maybe things aren't too bad in idle. You can set up a watch window or something. You could also insert a level argument into the mazeWalk parameters, increment it for the recursive calls. This will help you keep track of the stack. Debug with a much smaller maze.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo