Thread: Python recursive maze

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

Join Date
Jul 2013
Posts
10
Rep Power
0

Python recursive maze

the code that i have currently done so far for the recursive maze. it is supposed to start at the S and end at the F and print out a list of coordinate points at the end of the solution to the maze. if no solution, print "no solution".
thanks in advance!

this is the input:

WPPWWW
WWPWPS
WWPWPW
PPPPPW
FWPWWW
WPPPPW

Code:
```#this function reads a maze file, filename, and creates a maze, m.
# Please declare "m" as a list before calling the function and then pass it in.
m=[]  # This declares the maze as an empty list
def readMaze(m, filename):
mazeFile = open(filename, "r")
lines = mazeFile.readlines()
for line in lines:
line = line.strip()
row = [c for c in line]
m.append(row)

readMaze(m, "sampleMaze.txt") # This reads the maze into the list
print m # This prints the maze, showing it with the usual notation as a "list of lists"
start  = []

[PHP]
def findStart(m):
start = []
mazeSolution = []
for row in xrange(len(m)):
for col in xrange(len(m[row])):
if m[row][col]== "S":
start = [row,col]
mazeSolution = start
return mazeSolution

def solveMaze(m, mazeSolution):
mazeSolution = findStart(m)
row = mazeSolution[0]
col = mazeSolution[1]
return( solveMaze2(m, mazeSolution, row, col))

###############
import copy
def countMaze(m, row, col):

memoMap = copy.deepcopy(m)
return solveMaze2(m,memoMap,row,col)

def solveMaze2(m,memoMap,row,col):
memoMap = copy.deepcopy(m)
if ( (row<0) or (col<0) ):
return 0
if ( (row >= len(m[0])) or (col >= len(m[1]))):
return 0

if (memoMap[row][col] == "F"):
return 0

if (m[row][col] != "P"):
return 0

memoMap[row][col] = "W"

if(solveMaze2(m,memoMap,row-1,col)):
mazeSolution.append(row-1,col)
return True
elif(solveMaze2(m,memoMap,row,col-1)):
mazeSolution.append(row,col-1)
return True
elif(solveMaze2(m,memoMap,row,col+1)):
mazeSolution.append(row,col+1)
return True
elif(solveMaze2(m,memoMap,row+1,col)):
mazeSolution.append(row+1,col)
return True

else:
return False

##################
def mazeSolver2():
mazeFile = "sampleMaze.txt"
readMaze(m, mazeFile)
mazeSolution = []
# solution = findStart(m)
print mazeSolution

if (solveMaze(m, mazeSolution)== True):
print "True"
print mazeSolution
else:
print "No solution found."

mazeSolver2()```
2. You've ruined your program by reassigning mazeSolution in solvemaze instead of modifying the list passed as an argument. I think the program is fixed with following code. I put a "moat" around the maze to eliminate some tests, tests that could have used
0 <= i < len(LIST) tests. I removed other logic, parentheses, and extraneous code. I'm sure someone else can reduce it a good deal further. http://stackoverflow.com/questions/2...of the others. Oh, the other big problem was that the maze didn't have an exit, or I had a misunderstanding. New input file, with X to mark the exit, is
WPPWWW
WWPWPS
WWPWPW
PPPPPW
FWPWWW
WPPPXW
Code:
```import pprint

def readMaze(filename):
with open(filename,'r') as mazeFile:
return [[c for c in line.strip()] for line in mazeFile]

def moat(maze): # surround with a moat to remove the need for bound testing
for r in maze:
r[:0] = ['W']
r.append('W')
r0 = ['W']*len(maze[0])
maze[:0] = [r0]
maze.append(r0)

def findStart(m):
start = []
for row in range(len(m)):
for col in range(len(m[row])):
if m[row][col] == 'S':
return (row,col,)

def solveMaze2(maze,solution,row,col):
cell_value = maze[row][col]
if cell_value not in 'PSX': return False
if cell_value == 'X': return True
maze[row][col] = 'W' # drop crumb
for (dr,dc,) in ((-1,0,), (1,0,), (0,-1,), (0,1)):
if solveMaze2(maze,solution,row+dr,col+dc):
solution.append((row+dr,col+dc,))
return True

def solveMaze(maze, solution):
start = findStart(maze)
print('start:',start)
if start:
if solveMaze2(maze, solution, *start):
solution.append(start)
solution[:] = reversed(solution)
return True
return False

def main():
maze = readMaze('sampleMaze.txt')
moat(maze)
pprint.pprint(maze)
solution = []
if not solveMaze(maze,solution):
print('No solution found.')
else:
print(solution)

main()```
Last edited by b49P23TIvg; July 24th, 2013 at 12:40 AM.