Thread: Help with python recursive maze solver

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=[]

mazeFile = open(mazeFile, "r")
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. 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:
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 `.'.
3. 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
4. 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.