queens.py

#! /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

classQueens:

def__init__(self, n=N):
self.n=n
self.reset()

defreset(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

defsolve(self, x=0): # Recursive solver
foryinrange(self.n):
ifself.safe(x, y):
self.place(x, y)
ifx+1==self.n:
self.display()
else:
self.solve(x+1)
self.remove(x, y)

defsafe(self, x, y):
returnnotself.row[y] andnotself.up[x-y] andnotself.down[x+y]

defplace(self, x, y):
self.y[x] =y
self.row[y] =1
self.up[x-y] =1
self.down[x+y] =1

defremove(self, x, y):
self.y[x] =None
self.row[y] =0
self.up[x-y] =0
self.down[x+y] =0

silent=0# If true, count solutions only

defdisplay(self):
self.nfound=self.nfound+1
ifself.silent:
return
print'+-'+'--'*self.n+'+'
foryinrange(self.n-1, -1, -1):
print'|',
forxinrange(self.n):
ifself.y[x] ==y:
print"Q",
else:
print".",
print'|'
print'+-'+'--'*self.n+'+'

defmain():
importsys
silent=0
n=N
ifsys.argv[1:2] == ['-n']:
silent=1
delsys.argv[1]
ifsys.argv[1:]:
n=int(sys.argv[1])
q=Queens(n)
q.silent=silent
q.solve()
print"Found", q.nfound, "solutions."

if__name__=="__main__":
main()