### Thread: Solving a maze with recursion

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

Join Date
Jul 2012
Posts
8
Rep Power
0

#### 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/15-112-n12/index/labs_index.html

Here is my code so far:
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)```
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 05:43 PM. Reason: Repost