Python Programming
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me

The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.

Go Back   Dev Shed ForumsProgramming LanguagesPython Programming

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old July 20th, 2012, 05:33 PM
pacgcrosss pacgcrosss is offline
Registered User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Jul 2012
Posts: 8 pacgcrosss User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 3 h 40 m 9 sec
Reputation 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

Reply With Quote
  #2  
Old July 20th, 2012, 11:47 PM
b49P23TIvg's Avatar
b49P23TIvg b49P23TIvg is offline
Contributing User
Dev Shed Loyal (3000 - 3499 posts)
 
Join Date: Aug 2011
Posts: 3,364 b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level) 
Time spent in forums: 1 Month 2 Weeks 3 Days 10 h 28 m 48 sec
Reputation Power: 383
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()
__________________
[code]Code tags[/code] are essential for python code!

Last edited by b49P23TIvg : July 20th, 2012 at 11:53 PM. Reason: Insert `.'.

Reply With Quote
  #3  
Old July 21st, 2012, 03:25 PM
pacgcrosss pacgcrosss is offline
Registered User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Jul 2012
Posts: 8 pacgcrosss User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 3 h 40 m 9 sec
Reputation 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

Reply With Quote
  #4  
Old July 21st, 2012, 04:45 PM
b49P23TIvg's Avatar
b49P23TIvg b49P23TIvg is offline
Contributing User
Dev Shed Loyal (3000 - 3499 posts)
 
Join Date: Aug 2011
Posts: 3,364 b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level) 
Time spent in forums: 1 Month 2 Weeks 3 Days 10 h 28 m 48 sec
Reputation Power: 383
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.

Reply With Quote
Reply

Viewing: Dev Shed ForumsProgramming LanguagesPython Programming > Help with python recursive maze solver

Developer Shed Advertisers and Affiliates



Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

© 2003-2013 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap