// python script to solve the 8 queens problem


def allowedMoves(usedCol, usedDiagL, usedDiagR):
    allowed = ~(usedCol | usedDiagL | usedDiagR)
    for col in (1,2,4,8,16,32,64,128):
        if col & allowed:
            yield usedCol | col, (usedDiagL | col) << 1, (usedDiagR | col) >> 1

def eightQueensSolutions():
    for q0 in allowedMoves(0, 0, 0):
     for q1 in allowedMoves(*q0):
      for q2 in allowedMoves(*q1):
       for q3 in allowedMoves(*q2):
        for q4 in allowedMoves(*q3):
         for q5 in allowedMoves(*q4):
          for q6 in allowedMoves(*q5):
           for q7 in allowedMoves(*q6):
               yield (0,0,0),q0,q1,q2,q3,q4,q5,q6,q7

def solve8queens():
    ''' Solves the problem of placing 8 queens on a chess board with no queen 
        under attack. Queens are placed row by row, with the respective columns
        encoded by setting bit after bit in the qN variables for fast generation
        of allowed moves. The printboard() function decodes these to show the 
        final board.

        My goal was a fast program that is easy to read. The code is a concise
        combination of a generator for allowed moves and a deeply nested loop to
        traverse the search tree. Most assignments are accomplished by function
        calls and loops. Speed is achieved by not using recursion, by limiting
        data carried through the search to three integers, and through testing
        for allowed moves by a single bitwise operation. For diagonal attacks,
        two integers (usedDiagL and usedDiagR) keep track of queens placed, and
        are shifted left or right bitwise as the search proceeds from row to
        row. On my machine, it takes 7 ms to find all 92 solutions.

        Because the number of queens to be placed is hardcoded (by the giant
        nested loop), there is no need to have branching code deciding whether
        the final queen was just placed (in which case you have a solution).
        It is not possible to parameterize the dimensions of the chess board
        using this approach in a way that would keep the program lean and mean.
    '''
    solutions = [i for i in eightQueensSolutions()]
    for s in solutions:
        print ''
        printboard(s)
    print len(solutions), "solutions found"

def printboard(s):
    b = '_Q'
    for i,j in zip(s[:-1],s[1:]):
        n = i[0] ^ j[0]
        print " ".join([b[(n >> y) & 1] for y in range(8-1, -1, -1)])

if __name__ == "__main__": solve8queens()