8 Queens Problem

[Alex Martelli]

One way to think about the problem: you want all permutations of range(0,8)
that satisfy certain constraints.  The "permutations of range(0,8)" part is
about having 8 queens on the board, never two on the same row or column;
the "certain constraints" are about never having two queens in the same
diagonal either.  Omitting the "certain constraints" would clearly solve
the "8 rooks problems", for example.

The advantage of this approach is that it neatly break down the problem
into two separately reusable parts: (a) generate all permutations, (b)
filter a stream to yield only items that satisfy certain conditions.

Permutations can be easily adapted e.g. from Danny Yoo's recipe at
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/105962 --
my favourite version being (needs 2.2 and from __future__ import
generators, of course):


def permute(sequence):
    if not sequence: yield sequence
    for i in range(len(sequence)):
        head = sequence[i:i+1]
        for tail in permute(sequence[:i]+sequence[i+1:]): yield head + tail


permute(range(8)) will of course yield 8 factorial, 40320 permutations --
not too bad, so clearly we CAN afford this specific approach.


The '8 rooks' solutions that we want to reject as '8 queens' solutions
are clearly those where two queens are "in the same diagonal".  Given
the way we represent the board placements, the two diagonals on which
the i-th queen lies are clearly identified by i+x[i] and i-x[i] where
x is one of our permutations -- what we want is for each of these values 
to be unique for i in range(8), for x to be considered OK.

The validation function is therefore not hard to program:


def valid(board):
    for sign in (-1, 1):
        diagonals = {}
        for i in range(len(board)):
            diagonal = i + sign*board[i]
            if diagonal in diagonals: return False
            diagonals[diagonal] = True
    return True


Now, we can plug together these two elements in any old way, e.g.:


n = 0
m = 0
for board in permute(range(8)):
    n += 1
    if valid(board):
        m += 1
        print board

print 'total: %d out of %d permutations' % (m, n)


Or, we can choose to be more systematic, depending also on what
ancillary information we require -- supposing we only want an iterator
on all valid solutions, for example:


def filter_iterator(iterator, filter_function):
    for item in iterator:
        if filter_function(item): yield item


and


for board in filter_iterator(permute(range(8)), valid):
    print board


In this case, we don't know, at the top level, the total number of
permutations considered, but then that wasn't a specification of
the original problem, so that's OK.


Alex