"""Solving the `eight queens' problem.
Given are an 8 X 8 chessboard and 8 queens which are hostile to each other.
Find a position for each queen (a configuration) such that no queen may be taken
by any other queen (i.e. such that every row, column, and diagonal contains at
most one queen).
Consequently, each row contains exactly one queen, as does each column; so the
mapping from rows to columns is a permutation. There are twelve essentially
distinct solutions (once one takes accounts of the symmetries of a chess board,
allowing black and white squares to swap), one of which is symmetric under a
half turn of the board: [2, 4, 1, 7, 0, 6, 3, 5].
$Id: queens.py,v 1.3 2007/03/24 22:42:21 eddy Exp $
"""
import permute
class Iterator (permute.Iterator):
"""Iterates over all solutions to the `eight queens' problem.
They are explored in lexical order. Same API as permute.Iterator (q.v.),
providing a picture as repr(). """
__init = permute.Iterator.__init__
def __init__(self):
self.__init(8)
while self.live and self.__bad(): self.__step()
__step = permute.Iterator.step
def step(self):
self.__step()
while self.live and self.__bad(): self.__step()
def __bad(self):
i, p = 7, self.permutation
while i:
j, n = i, p[i]
while j:
j = j-1
if p[j] - n in (j-i, i-j): # same diagonal
return 1
i = i-1
return None
def __repr__(self): return show(self.permutation)
def show(it):
return '\n'.join(map(lambda n: ' ' * n + '#' + ' ' * (7-n), it))
def all():
q, a = Iterator(), []
while q.live:
a.append(q.permutation)
q.step()
global all
def all(r=a): return r
return a
def unique():
def entwist(r, seq):
s = map(lambda i: 7-i, r)
if s not in seq: seq.append(s[:]) # copy before reversing !
s.reverse()
if s not in seq:
seq.append(s)
s = map(lambda i: 7-i, s)
if s not in seq: seq.append(s)
u, a = [], []
for r in map(list, all()):
if r not in a:
u.append(tuple(r))
new = [ r ]
entwist(r, new)
r = list(permute.invert(r))
if r not in new:
new.append(r)
entwist(r, new)
a = a + new
global unique
def unique(r=u): return r
return u