Mercurial > cpython-lru_cache-weakref

annotate Demo/scripts/queens.py @ 58925:eecf1bef052d 2.6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merged revisions 78207 via svnmerge from svn+ssh://pythondev@svn.python.org/python/trunk ........ r78207 | ezio.melotti | 2010-02-17 01:26:09 +0200 (Wed, 17 Feb 2010) | 1 line #7930: fix stripid ........
author Ezio Melotti <ezio.melotti@gmail.com>
date Tue, 16 Feb 2010 23:29:44 +0000
parents 876cf7b3d3df
children 6a5e0c913c7c 7d16b42fcdbd
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
15412
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
1 #! /usr/bin/env python
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
2
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
3 """N queens problem.
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
4
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
5 The (well-known) problem is due to Niklaus Wirth.
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
6
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
7 This solution is inspired by Dijkstra (Structured Programming). It is
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
8 a classic recursive backtracking approach.
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
9
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
10 """
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
11
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
12 N = 8 # Default; command line overrides
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
13
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
14 class Queens:
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
15
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
16 def __init__(self, n=N):
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
17 self.n = n
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
18 self.reset()
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
19
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
20 def reset(self):
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
21 n = self.n
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
22 self.y = [None]*n # Where is the queen in column x
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
23 self.row = [0]*n # Is row[y] safe?
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
24 self.up = [0] * (2*n-1) # Is upward diagonal[x-y] safe?
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
25 self.down = [0] * (2*n-1) # Is downward diagonal[x+y] safe?
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
26 self.nfound = 0 # Instrumentation
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
27
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
28 def solve(self, x=0): # Recursive solver
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
29 for y in range(self.n):
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
30 if self.safe(x, y):
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
31 self.place(x, y)
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
32 if x+1 == self.n:
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
33 self.display()
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
34 else:
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
35 self.solve(x+1)
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
36 self.remove(x, y)
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
37
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
38 def safe(self, x, y):
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
39 return not self.row[y] and not self.up[x-y] and not self.down[x+y]
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
40
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
41 def place(self, x, y):
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
42 self.y[x] = y
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
43 self.row[y] = 1
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
44 self.up[x-y] = 1
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
45 self.down[x+y] = 1
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
46
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
47 def remove(self, x, y):
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
48 self.y[x] = None
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
49 self.row[y] = 0
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
50 self.up[x-y] = 0
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
51 self.down[x+y] = 0
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
52
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
53 silent = 0 # If set, count solutions only
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
54
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
55 def display(self):
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
56 self.nfound = self.nfound + 1
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
57 if self.silent:
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
58 return
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
59 print '+-' + '--'*self.n + '+'
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
60 for y in range(self.n-1, -1, -1):
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
61 print '|',
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
62 for x in range(self.n):
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
63 if self.y[x] == y:
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
64 print "Q",
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
65 else:
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
66 print ".",
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
67 print '|'
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
68 print '+-' + '--'*self.n + '+'
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
69
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
70 def main():
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
71 import sys
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
72 silent = 0
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
73 n = N
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
74 if sys.argv[1:2] == ['-n']:
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
75 silent = 1
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
76 del sys.argv[1]
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
77 if sys.argv[1:]:
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
78 n = int(sys.argv[1])
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
79 q = Queens(n)
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
80 q.silent = silent
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
81 q.solve()
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
82 print "Found", q.nfound, "solutions."
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
83
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
84 if __name__ == "__main__":
876cf7b3d3df A solution to the classic N queens problem.
Guido van Rossum <guido@python.org>
parents:
diff changeset
85 main()