Recursion head scratcher
Joel Madigan
dochoncho at gmail.com
Wed Dec 2 08:28:13 EST 2009
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.
More information about the Python-list
mailing list