Good Python generators example?

Andrew Koenig ark at research.att.com
Sun Apr 20 16:44:02 EDT 2003


Robert> Can someone point me to a nice concise Python 2.2 compatible
Robert> example of the use of generators?

Here's a program that solves the "8 queens" problem--that is, the
problem of how to place 8 queens on a chessboard so that none of
them attacks any of the others.  It prints all the solutions.

from __future__ import generators

class Queens(object):
    def __init__(self, n):
        assert n >= 0
        self.N = n
        self.board = []

    def generate(self):
        if len(self.board) == self.N:
            yield self.board[:]
        else:
            for i in range(self.N):
                if self.safe(i):
                    self.board.append(i)
                    for i in self.generate():
                        yield i
                    self.board.pop()

    def safe(self, n):
        "Is is safe to append a queen to the board in row n?"
        m = len(self.board)
        for i in range(m):
            b = self.board[i]
            if n == b or b+(m-i) == n or b-(m-i) == n:
                return False
        return True
    
for i in Queens(8).generate():
   print i


-- 
Andrew Koenig, ark at research.att.com, http://www.research.att.com/info/ark




More information about the Python-list mailing list