1 #!/usr/bin/env python3 2 3 """ 4 N queens problem. 5 6 The (well-known) problem is due to Niklaus Wirth. 7 8 This solution is inspired by Dijkstra (Structured Programming). It is 9 a classic recursive backtracking approach. 10 """ 11 12 N = 8 # Default; command line overrides 13 14 class Queens: 15 16 def __init__(self, n=N): 17 self.n = n 18 self.reset() 19 20 def reset(self): 21 n = self.n 22 self.y = [None] * n # Where is the queen in column x 23 self.row = [0] * n # Is row[y] safe? 24 self.up = [0] * (2*n-1) # Is upward diagonal[x-y] safe? 25 self.down = [0] * (2*n-1) # Is downward diagonal[x+y] safe? 26 self.nfound = 0 # Instrumentation 27 28 def solve(self, x=0): # Recursive solver 29 for y in range(self.n): 30 if self.safe(x, y): 31 self.place(x, y) 32 if x+1 == self.n: 33 self.display() 34 else: 35 self.solve(x+1) 36 self.remove(x, y) 37 38 def safe(self, x, y): 39 return not self.row[y] and not self.up[x-y] and not self.down[x+y] 40 41 def place(self, x, y): 42 self.y[x] = y 43 self.row[y] = 1 44 self.up[x-y] = 1 45 self.down[x+y] = 1 46 47 def remove(self, x, y): 48 self.y[x] = None 49 self.row[y] = 0 50 self.up[x-y] = 0 51 self.down[x+y] = 0 52 53 silent = 0 # If true, count solutions only 54 55 def display(self): 56 self.nfound = self.nfound + 1 57 if self.silent: 58 return 59 print('+-' + '--'*self.n + '+') 60 for y in range(self.n-1, -1, -1): 61 print('|', end=' ') 62 for x in range(self.n): 63 if self.y[x] == y: 64 print("Q", end=' ') 65 else: 66 print(".", end=' ') 67 print('|') 68 print('+-' + '--'*self.n + '+') 69 70 def main(): 71 import sys 72 silent = 0 73 n = N 74 if sys.argv[1:2] == ['-n']: 75 silent = 1 76 del sys.argv[1] 77 if sys.argv[1:]: 78 n = int(sys.argv[1]) 79 q = Queens(n) 80 q.silent = silent 81 q.solve() 82 print("Found", q.nfound, "solutions.") 83 84 if __name__ == "__main__": 85 main() 86
