Recursive generators and backtracking search

[Mike Meyer]

"Talin" <viridia at gmail.com> writes:
> As an alternative, I'd like to present the following implementation. If
> you compare this one with the one in lib/test/test_generator.py you
> will agree (I hope) that by using recursive generators to implement
> backtracking, the resulting code is a little more straightforward and
> intuitive:

I'd propose one change to that...
>     def qsearch( qarray = () ):
>         for q in range( 0, bsize ):        # Try each position
>             if not threaten( qarray, q ):  # If not threatened
>                 pos = qarray + ( q, );     # Append to the pos array
>
>                 if len( pos ) >= bsize:    # Are we done?
>                     yield pos              # Yield the answer
>                 else:            # recursively call new generator
>                     for pos in qsearch( pos ):
>                         yield pos

Um - do you really want to reuse the variable pos here? Yeah, it
works, but this strikes me as very confusing. I'm not sure that it
might not be implementation dependent.

      <mike
-- 
Mike Meyer <mwm at mired.org>			http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.