Good Python generators example?

[Tim Peters]

[Robert Oschler, asks for generator examples; Andrew Koenig gives an
 N-Queens solver]
> Thanks!  Interesting choice of examples, last time I solved that
> problem was with Prolog.  With a stack of Python generators you can
> pretty  well emulate Prolog backtracking, except for the automatic
> unbinding of variables.

Check out test_generators.py too, in your Python Lib/test/ directory.  There
are three implementations of a conjoin() generator in there, which combines
other generators (passed as a list of arguments) in a backtracking fashion.
One application of conjoin() in test_generators is an efficient N-Queens
solver.  Another is a Knight's Tour solver.  One of the conjoin()
implementations is non-recursive, and can be used to solve N-Queens or
Knight's Tour problems for boards much larger than Python's recursion limit
(which varies across platforms, but which is always limited by the platform
C stack size).  (Note that an N-Queen's solver normally uses one recursion
level per row, but Knight's Tour needs a level for each square.)

An interesting feature of the Knight's Tour solution is that it uses
different generator functions for the first, second, and last moves than it
uses for the other m*n-3 moves (which latter all use the same generator
function).  This allows the generator function used most often to skip
conditional tests unique to the endpoints, and so speeds it significantly;
it also allows, e.g., the first move to be special in a natural way (since a
Knight's Tour is a cycle, the first move may as well pick on the upper left
square -- any solution can be viewed as starting there).

There is, as you note, no automatic backtracking of binding states in
Python.  The examples illustrate by-hand data backtracking via saving and
restoring state via a combination of local vars, lexical closures, and
instance vars.