# [Python-checkins] CVS: python/dist/src/Demo/scripts queens.py,NONE,1.1

Guido van Rossum python-dev@python.org
Thu, 16 Nov 2000 13:25:54 -0800

```Update of /cvsroot/python/python/dist/src/Demo/scripts
In directory slayer.i.sourceforge.net:/tmp/cvs-serv19493

queens.py
Log Message:
A solution to the classic N queens problem.

--- NEW FILE ---
#! /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 = *n                # Is row[y] safe?
self.up =  * (2*n-1)         # Is upward diagonal[x-y] safe?
self.down =  * (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
if sys.argv[1:]:
n = int(sys.argv)
q = Queens(n)
q.silent = silent
q.solve()
print "Found", q.nfound, "solutions."

if __name__ == "__main__":
main()

```