Recursion head scratcher

[Joel Madigan]

On 12/2/09, Dave Angel <davea at ieee.org> wrote:
> 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
>
>
Wow... that's devilishy clever.  I can see  that I still have a long
way to travel on my path.  Thanks for your insight.