A solution to the classic N queens problem.

1 files changed, 85 insertions, 0 deletions

diff --git a/Demo/scripts/queens.py b/Demo/scripts/queens.py
new file mode 100755
index 0000000..74756be
--- /dev/null
+++ b/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 set, 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()