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

2000年11月16日 13:25:54 -0800

Update of /cvsroot/python/python/dist/src/Demo/scripts
In directory slayer.i.sourceforge.net:/tmp/cvs-serv19493
Added Files:
	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 = [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()