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.
--
http://mail.python.org/mailman/listinfo/python-list
