Recursive generators and backtracking search

[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.

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:

# Example of using generators to implement backtracking search.
# The example below is an implementation of the classic "N queens"
# problem (place N queens on an N x N chessboard so that none are
# threatened by the others.)
#
# Board representation: Since no two queens can be one the same
# row, the board is represented as a tuple of N length, where
# each element is the column occupied by the queen on that row.

def queens( bsize ):

    # Function to test if a queen is threatened by any previously
    # placed queen.
    def threaten( qarray, newpos ):
        # Now check the diagonals
        dist = len( qarray )        # Distance between rows
        for q in qarray:
            if q == newpos: return True             # Same column
            if q + dist == newpos: return True      # diagonal
            if q - dist == newpos: return True      # diagonal
            dist -= 1
        return False

    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

    print "Queens problem for", bsize, "x", bsize, "board."
    for ans in qsearch():
    `   # Print out the board
        print "+" + "---+" * bsize;
        for q in ans:
            print "|" + "   |" * q + " Q |" + "   |" * (bsize - q - 1)
            print "+" + "---+" * bsize;
        print

queens( 8 )

Now, you may be wondering what is my point? Well, first, I want to
encourage people to think about using Python as a language for complex
heuristic search problems. Traditionally, LISP and Prolog have been the
language of choices for "AI" type programming, however there is a clear
advantage to the readability and maintainability of Python, as well as
being much more integrated into modern computing environments (in terms
of available interpreters, IDEs, libraries, etc.)

Secondly, I want to lobby for additional support in the language and
standard libraries for handling such problems. There are a number of
fairly obvious language enhancements which would make the above example
even simpler - for examle, the idea of being able to return the output
of one generator directly from another instead of having to iterate
through all of the results and then re-yield them has already been
discussed in this forum.