The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.
|
 |
|
Dev Shed Forums
> Programming Languages
> Python Programming
|
Help with python recursive maze solver
Discuss Help with python recursive maze solver in the Python Programming forum on Dev Shed. Help with python recursive maze solver Python Programming forum discussing coding techniques, tips and tricks, and Zope related information. Python was designed from the ground up to be a completely object-oriented programming language.
|
|
 |
|
|
|
|

Dev Shed Forums Sponsor:
|
|
|

July 20th, 2012, 05:33 PM
|
|
Registered User
|
|
Join Date: Jul 2012
Posts: 8
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
|

July 20th, 2012, 11:47 PM
|
 |
Contributing User
|
|
|
|
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 `.'.
|

July 21st, 2012, 03:25 PM
|
|
Registered User
|
|
Join Date: Jul 2012
Posts: 8
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
|

July 21st, 2012, 04:45 PM
|
 |
Contributing User
|
|
|
|
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 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.
|
Developer Shed Advertisers and Affiliates
| Thread Tools |
Search this Thread |
|
|
|
| Display Modes |
Rate This Thread |
Linear Mode
|
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
|
|