#! /usr/bin/env python

"""N queens problem.

The (well-known) problem is due to Niklaus Wirth.

This solution is inspired by Dijkstra (Structured Programming).  It is

a classic recursive backtracking approach.

"""

N = 8                                   # Default; command line overrides

class Queens:

    def __init__(self, n=N):

        self.n = n

        self.reset()

    def reset(self):

        n = self.n

        self.y = [None]*n               # Where is the queen in column x

        self.row = [0]*n                # Is row[y] safe?

        self.up = [0] * (2*n-1)         # Is upward diagonal[x-y] safe?

        self.down = [0] * (2*n-1)       # Is downward diagonal[x+y] safe?

        self.nfound = 0                 # Instrumentation

    def solve(self, x=0):               # Recursive solver

        for y in range(self.n):

            if self.safe(x, y):

                self.place(x, y)

                if x+1 == self.n:

                    self.display()

                else:

                    self.solve(x+1)

                self.remove(x, y)

    def safe(self, x, y):

        return not self.row[y] and not self.up[x-y] and not self.down[x+y]

    def place(self, x, y):

        self.y[x] = y

        self.row[y] = 1

        self.up[x-y] = 1

        self.down[x+y] = 1

    def remove(self, x, y):

        self.y[x] = None

        self.row[y] = 0

        self.up[x-y] = 0

        self.down[x+y] = 0

    silent = 0                          # If set, count solutions only

    def display(self):

        self.nfound = self.nfound + 1

        if self.silent:

            return

        print '+-' + '--'*self.n + '+'

        for y in range(self.n-1, -1, -1):

            print '|',

            for x in range(self.n):

                if self.y[x] == y:

                    print "Q",

                else:

                    print ".",

            print '|'

        print '+-' + '--'*self.n + '+'

def main():

    import sys

    silent = 0

    n = N

    if sys.argv[1:2] == ['-n']:

        silent = 1

        del sys.argv[1]

    if sys.argv[1:]:

        n = int(sys.argv[1])

    q = Queens(n)

    q.silent = silent

    q.solve()

    print "Found", q.nfound, "solutions."

if __name__ == "__main__":

    main()