July 20th, 2012, 05:21 PM

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/15112n12/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, col1, solution)
mazeWalk(m, row+1, col, solution)
mazeWalk(m, row1, 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