summaryrefslogtreecommitdiffstats
path: root/Demo/scripts/queens.py
diff options
context:
space:
mode:
Diffstat (limited to 'Demo/scripts/queens.py')
-rwxr-xr-xDemo/scripts/queens.py85
1 files changed, 0 insertions, 85 deletions
diff --git a/Demo/scripts/queens.py b/Demo/scripts/queens.py
deleted file mode 100755
index ffd4bea..0000000
--- a/Demo/scripts/queens.py
+++ /dev/null
@@ -1,85 +0,0 @@
-#! /usr/bin/env python3
-
-"""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('|', end=' ')
- for x in range(self.n):
- if self.y[x] == y:
- print("Q", end=' ')
- else:
- print(".", end=' ')
- 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()