Hi everyone!
Sorry this isn't strictly a Python question but my algorithms professor
contends that given the standard recursive-backtracking maze solving
algorithm:
width=6
height=4
maze=[[1,0,1,1,0,1],
[0,0,1,0,0,0],
[1,0,1,0,1,0],
[0,0,0,0,1,1]]
visited = [[False for x in range(width)] for y in range(height)]
sx=1
sy=2
ex=4
ey=0
def findPath(x,y):
if (x < 0 or x >= width or y < 0 or y >= height):
return False
elif maze[y][x] == 1:
return False
elif visited[y][x]:
return False
elif (x == ex and y == ey):
print "(%d,%d)"%(x,y),
return True
else:
visited[y][x] = True
if findPath(x-1,y) or \
findPath(x+1,y) or \
findPath(x,y-1) or \
findPath(x,y+1):
print "(%d,%d)"%(x,y),
return True
else:
return False
print findPath(sx,sy)
that it is possible to make it print the path to the finish in the order the
steps were taken. That is, the algorithm as written produces:
(4,0) (4,1) (3,1) (3,2) (3,3) (2,3) (1,3) (1,2) True
Rather than
(1,2) (1,3) (2,3) (3,3) (3,2) (3,1) (4,1) (4,0) True
Furthermore, he claims it's a "one line change" without using a stack or any
other extra data structure. But I can't figure it out to save my life.
This isn't homework, there isn't credit on the line. I think he said it
just to mess with us. Can anyone point me in the right direction? It's
driving me crazy. The output it gives makes perfect sense, since it just
prints out each step as the stack unwinds. Normally you would print the
output BEFORE recursing, but in this case you only want to print the step if
it is actually part of the path. And you don't know that until after the
recursion.
Can anyone shed some light on this?
Thanks,
Joel
