Mercurial > cpython-lru_cache-weakref

annotate Demo/scripts/queens.py @ 79675:c0a2294de787 2.7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Issue #16199: Backport 2to3 typo fix from 3.2.
author Chris Jerdonek <chris.jerdonek@gmail.com>
date Thu, 11 Oct 2012 16:15:46 -0700
parents 6a5e0c913c7c
children
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
56484
6a5e0c913c7c Update lpwatch script.
Georg Brandl <georg@python.org>
parents: 15412
diff changeset
22 self.y = [None] * n # Where is the queen in column x
6a5e0c913c7c Update lpwatch script.
Georg Brandl <georg@python.org>
parents: 15412
diff changeset
23 self.row = [0] * n # Is row[y] safe?
15412
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
56484
6a5e0c913c7c Update lpwatch script.
Georg Brandl <georg@python.org>
parents: 15412
diff changeset
53 silent = 0 # If true, count solutions only
15412
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()