Eight Queens Puzzle by Magnus Lie Hetland

[Anton Vredegoor]

bokr at oz.net (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:x*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()