«

(Bengt Richter) wrote:

>Obviously (after seeing your code and on thinking a board has two sides with
>four rotational positions each, for a total of 8 == 1 identity plus 7 T's ;-/ )

There is also something with this puzzle that makes me think of the
"getting a submatrix of all true" thread. A solution there was a
combination of the columns, here a solution is a permutation of
range(len(columns)). Below I'm giving a possible way to solve the
puzzle using this observation, but maybe someone can see a way to
improve it.

Anton

#permqueens.py
from sets import Set

def unique(n):
""" nqueens solver filtered for solutions that
are rotations or reflections """
seen = Set()
for sol in nqueens(n):
if sol not in seen:
m = mirrors(sol)
seen |= Set(m)
yield min(m)

def asqueens(sol):
""" ascii-art representation of a solution """
R,res = range(len(sol)),""
Q,n = zip(R,sol[::-1]),len(sol)
for i in R:
for j in R:
res += '+Q'[(n-j-1,n-i-1) in Q]+ ' '
res += '\n'
return res

def nqueens(n):
""" iterative nqueens solver using permutations """
QC,R = queencovers(n),range(n)
for i in xrange(fac(n)):
p = indexedperm(i,R)
if checksol(p,QC): yield tuple(p)

def mirrors(sol):
""" a list of mirror images of a solution """
def flip(x): return x[::-1]
def transpose(x):
xx = list(x)
for i,j in enumerate(x): xx[j] = i
return tuple(xx)
f,t = flip(sol),transpose(sol)
ft,tf = flip(t),transpose(f)
ftf,tft = flip(tf),transpose(ft)
ftft = flip(tft)
return [sol,f,t,ft,tf,ftf,tft,ftft]

def queencovers(n):
""" a dictionary of the positions that are covered by
queens on all board positions on an nxn board """
board,queens = [divmod(i,n) for i in range(n*n)],{}
for pos in board: queens[pos] = Set(cover(pos,board))
return queens

def fac(n):
""" faculty of n """
return reduce(lambda x,y*y,range(2,n+1),1L)

def indexedperm(m,L):
""" permutations of list L by index """
n,res,T = len(L),L[:],L[:]
for i in range(n):
m,d = divmod(m,n-i)
res[i] = T.pop(d)
return res

def checksol(sol,QC):
""" a solution is a permutation of a range, to convert it to
a list of queen positions it is zipped with a range, a
solution is true if no queen threatens the other queens """
n = len(sol)
#first a little optimization, queens cannot be adjacent
for i in range(n-1):
if abs(sol[i]-sol[i+1]) == 1: return False
queens = Set(zip(range(n),sol))
#check if no queen threatens another queen
for queen in queens:
if queens & QC[queen]: return False
return True

def cover((i,j),board):
""" positions that are covered by queen(i,j),
without (i,j) itself """
def keep((x,y)):
if (i,j) == (x,y) : return False
return i==x or j==y or abs(x-i)==abs(y-j)
return filter(keep,board)

def test():
""" test the unique nqueens solver """
n = 8
for i,sol in enumerate(unique(n)):
print i, sol
print asqueens(sol)

if __name__=='__main__':
test()