How to use generators?

[Tom Anderson]

On Wed, 9 Nov 2005, Sybren Stuvel wrote:

> Ian Vincent enlightened us with:
>
>> I have never used generators before but I might have now found a use 
>> for them. I have written a recursive function to solve a 640x640 maze 
>> but it crashes, due to exceeding the stack.  The only way around this I 
>> can think of is to use Generator but I have no idea how to.
>
> A better way is to use a queue. I had the same problem with a similar
> piece of code. The only thing why you're using a stack is to move to
> the "next" point, without going back to a visited point.

Exactly - using a queue means you'll do a breadth-first rather than a 
depth-first search, which will involve much less depth of recursion. See:

http://cs.colgate.edu/faculty/nevison.pub/web102/web102S00/Notes12.htm

For details.

An extended version of this exercise would be to implement an A* search:

http://en.wikipedia.org/wiki/A-star_search_algorithm

Which might be quicker than a blind breadth-first.

tom

-- 
Exceptions say, there was a problem. Someone must deal with it. If you
won't deal with it, I'll find someone who will.