← Back to branch summary

~ubuntu-branches/ubuntu/trusty/python3.4/trusty-proposed

« back to all changes in this revision

Viewing changes to Tools/demo/queens.py

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2013-11-25 09:44:27 UTC
  • Revision ID: package-import@ubuntu.com-20131125094427-lzxj8ap5w01lmo7f
Tags: upstream-3.4~b1
Import upstream version 3.4~b1

Show diffs side-by-side

added added

removed removed

Lines of Context:
Tools/demo/queens.py
 
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()