• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1#!/usr/bin/env python3
2
3"""
4N queens problem.
5
6The (well-known) problem is due to Niklaus Wirth.
7
8This solution is inspired by Dijkstra (Structured Programming).  It is
9a classic recursive backtracking approach.
10"""
11
12N = 8                                   # Default; command line overrides
13
14class 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
70def 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
84if __name__ == "__main__":
85    main()
86