ยปCore Development>Code coverage>Tools/demo/queens.py

Python code coverage for Tools/demo/queens.py

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