# Recursive generators and backtracking search

Tim Peters tim.peters at gmail.com
Mon Oct 31 21:39:35 CET 2005

```[Talin]
> I've been using generators to implement backtracking search for a while
> now. Unfortunately, my code is large and complex enough (doing
> unification on math expressions) that its hard to post a simple
> example. So I decided to look for a simpler problem that could be used
> to demonstrate the technique that I am talking about.
>
> I noticed that PEP 255 (Simple Generators) refers to an implementation
> of the "8 Queens" problem in the lib/test directory. Looking at the
> code, I see that while it does use generators, it doesn't use them
> recursively.

In context, the N-Queens and MxN Knight's Tour solvers in
test_generators.py are exercising the conjoin() generators in that
file.  That's a different approach to backtracking search, with some
nice features too:  (1) it uses heap space instead of stack space;
and, (2) it's easy to run entirely different code at different levels
of the search.  #2 isn't well-illustrated by the N-Queens solver
because the problem is so symmetric, although it is used to give the
code for each row its own local table of the board lines used by the
squares in that row.  That in turn is a major efficiency win.  The
Knight's Tour solver makes more obvious use of #2, by, e.g., running
different code for "the first" square than for "the second" square
than for "the last" square than for "all the other" squares.  That
doesn't require any runtime test-and-branch'ing in the search code,
it's set up once at the start in the list of M*N generators passed to
conjoin() (each square gets its own generator, which can be customized
in arbitrary ways, in advance, for that square).

> 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:

Since "straightfoward and intuitive" weren't the goals of the
test_generators.py implementations, that's not too surprising ;-)

> ...

```