Recursion head scratcher

[Dave Angel]

Joel Madigan wrote:
> 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
>
>   
How about swapping sx,sy with ex,ey ?  That's one line (one statement).  
And the rest of the algorithm appears to be symmetric.  Basically, 
you're reversing time, and starting with the end point, descending till 
you find the start point.

DaveA