diff options
| author | darylm503 <darylm503@6f19259b-4bc3-4df7-8a09-765794883524> | 2012-04-16 22:12:42 +0000 |
|---|---|---|
| committer | darylm503 <darylm503@6f19259b-4bc3-4df7-8a09-765794883524> | 2012-04-16 22:12:42 +0000 |
| commit | 4710c53dcad1ebf3755f3efb9e80ac24bd72a9b2 (patch) | |
| tree | 2d17d2388a78082e32f6a97120d707328143543b /AppPkg/Applications/Python/Python-2.7.2/Demo/scripts/queens.py | |
| parent | cbc6b5e54599c7391ece99ad3c5313f4dd4ddda6 (diff) | |
| download | edk2-platforms-4710c53dcad1ebf3755f3efb9e80ac24bd72a9b2.tar.xz | |
AppPkg/Applications/Python: Add Python 2.7.2 sources since the release of Python 2.7.3 made them unavailable from the python.org web site.
These files are a subset of the python-2.7.2.tgz distribution from python.org. Changed files from PyMod-2.7.2 have been copied into the corresponding directories of this tree, replacing the original files in the distribution.
Signed-off-by: daryl.mcdaniel@intel.com
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@13197 6f19259b-4bc3-4df7-8a09-765794883524
Diffstat (limited to 'AppPkg/Applications/Python/Python-2.7.2/Demo/scripts/queens.py')
| -rw-r--r-- | AppPkg/Applications/Python/Python-2.7.2/Demo/scripts/queens.py | 85 |
1 files changed, 85 insertions, 0 deletions
diff --git a/AppPkg/Applications/Python/Python-2.7.2/Demo/scripts/queens.py b/AppPkg/Applications/Python/Python-2.7.2/Demo/scripts/queens.py new file mode 100644 index 0000000000..5d212ed86d --- /dev/null +++ b/AppPkg/Applications/Python/Python-2.7.2/Demo/scripts/queens.py @@ -0,0 +1,85 @@ +#! /usr/bin/env python
+
+"""N queens problem.
+
+The (well-known) problem is due to Niklaus Wirth.
+
+This solution is inspired by Dijkstra (Structured Programming). It is
+a classic recursive backtracking approach.
+
+"""
+
+N = 8 # Default; command line overrides
+
+class Queens:
+
+ def __init__(self, n=N):
+ self.n = n
+ self.reset()
+
+ def reset(self):
+ n = self.n
+ self.y = [None] * n # Where is the queen in column x
+ self.row = [0] * n # Is row[y] safe?
+ self.up = [0] * (2*n-1) # Is upward diagonal[x-y] safe?
+ self.down = [0] * (2*n-1) # Is downward diagonal[x+y] safe?
+ self.nfound = 0 # Instrumentation
+
+ def solve(self, x=0): # Recursive solver
+ for y in range(self.n):
+ if self.safe(x, y):
+ self.place(x, y)
+ if x+1 == self.n:
+ self.display()
+ else:
+ self.solve(x+1)
+ self.remove(x, y)
+
+ def safe(self, x, y):
+ return not self.row[y] and not self.up[x-y] and not self.down[x+y]
+
+ def place(self, x, y):
+ self.y[x] = y
+ self.row[y] = 1
+ self.up[x-y] = 1
+ self.down[x+y] = 1
+
+ def remove(self, x, y):
+ self.y[x] = None
+ self.row[y] = 0
+ self.up[x-y] = 0
+ self.down[x+y] = 0
+
+ silent = 0 # If true, count solutions only
+
+ def display(self):
+ self.nfound = self.nfound + 1
+ if self.silent:
+ return
+ print '+-' + '--'*self.n + '+'
+ for y in range(self.n-1, -1, -1):
+ print '|',
+ for x in range(self.n):
+ if self.y[x] == y:
+ print "Q",
+ else:
+ print ".",
+ print '|'
+ print '+-' + '--'*self.n + '+'
+
+def main():
+ import sys
+ silent = 0
+ n = N
+ if sys.argv[1:2] == ['-n']:
+ silent = 1
+ del sys.argv[1]
+ if sys.argv[1:]:
+ n = int(sys.argv[1])
+ q = Queens(n)
+ q.silent = silent
+ q.solve()
+ print "Found", q.nfound, "solutions."
+
+if __name__ == "__main__":
+ main()
|