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()

Tweet This+ 1 thisPost To Linkedin