| 1 | n/a | #!/usr/bin/env python3 |
|---|
| 2 | n/a | |
|---|
| 3 | n/a | """ |
|---|
| 4 | n/a | N queens problem. |
|---|
| 5 | n/a | |
|---|
| 6 | n/a | The (well-known) problem is due to Niklaus Wirth. |
|---|
| 7 | n/a | |
|---|
| 8 | n/a | This solution is inspired by Dijkstra (Structured Programming). It is |
|---|
| 9 | n/a | a classic recursive backtracking approach. |
|---|
| 10 | n/a | """ |
|---|
| 11 | n/a | |
|---|
| 12 | n/a | N = 8 # Default; command line overrides |
|---|
| 13 | n/a | |
|---|
| 14 | n/a | class Queens: |
|---|
| 15 | n/a | |
|---|
| 16 | n/a | def __init__(self, n=N): |
|---|
| 17 | n/a | self.n = n |
|---|
| 18 | n/a | self.reset() |
|---|
| 19 | n/a | |
|---|
| 20 | n/a | def reset(self): |
|---|
| 21 | n/a | n = self.n |
|---|
| 22 | n/a | self.y = [None] * n # Where is the queen in column x |
|---|
| 23 | n/a | self.row = [0] * n # Is row[y] safe? |
|---|
| 24 | n/a | self.up = [0] * (2*n-1) # Is upward diagonal[x-y] safe? |
|---|
| 25 | n/a | self.down = [0] * (2*n-1) # Is downward diagonal[x+y] safe? |
|---|
| 26 | n/a | self.nfound = 0 # Instrumentation |
|---|
| 27 | n/a | |
|---|
| 28 | n/a | def solve(self, x=0): # Recursive solver |
|---|
| 29 | n/a | for y in range(self.n): |
|---|
| 30 | n/a | if self.safe(x, y): |
|---|
| 31 | n/a | self.place(x, y) |
|---|
| 32 | n/a | if x+1 == self.n: |
|---|
| 33 | n/a | self.display() |
|---|
| 34 | n/a | else: |
|---|
| 35 | n/a | self.solve(x+1) |
|---|
| 36 | n/a | self.remove(x, y) |
|---|
| 37 | n/a | |
|---|
| 38 | n/a | def safe(self, x, y): |
|---|
| 39 | n/a | return not self.row[y] and not self.up[x-y] and not self.down[x+y] |
|---|
| 40 | n/a | |
|---|
| 41 | n/a | def place(self, x, y): |
|---|
| 42 | n/a | self.y[x] = y |
|---|
| 43 | n/a | self.row[y] = 1 |
|---|
| 44 | n/a | self.up[x-y] = 1 |
|---|
| 45 | n/a | self.down[x+y] = 1 |
|---|
| 46 | n/a | |
|---|
| 47 | n/a | def remove(self, x, y): |
|---|
| 48 | n/a | self.y[x] = None |
|---|
| 49 | n/a | self.row[y] = 0 |
|---|
| 50 | n/a | self.up[x-y] = 0 |
|---|
| 51 | n/a | self.down[x+y] = 0 |
|---|
| 52 | n/a | |
|---|
| 53 | n/a | silent = 0 # If true, count solutions only |
|---|
| 54 | n/a | |
|---|
| 55 | n/a | def display(self): |
|---|
| 56 | n/a | self.nfound = self.nfound + 1 |
|---|
| 57 | n/a | if self.silent: |
|---|
| 58 | n/a | return |
|---|
| 59 | n/a | print('+-' + '--'*self.n + '+') |
|---|
| 60 | n/a | for y in range(self.n-1, -1, -1): |
|---|
| 61 | n/a | print('|', end=' ') |
|---|
| 62 | n/a | for x in range(self.n): |
|---|
| 63 | n/a | if self.y[x] == y: |
|---|
| 64 | n/a | print("Q", end=' ') |
|---|
| 65 | n/a | else: |
|---|
| 66 | n/a | print(".", end=' ') |
|---|
| 67 | n/a | print('|') |
|---|
| 68 | n/a | print('+-' + '--'*self.n + '+') |
|---|
| 69 | n/a | |
|---|
| 70 | n/a | def main(): |
|---|
| 71 | n/a | import sys |
|---|
| 72 | n/a | silent = 0 |
|---|
| 73 | n/a | n = N |
|---|
| 74 | n/a | if sys.argv[1:2] == ['-n']: |
|---|
| 75 | n/a | silent = 1 |
|---|
| 76 | n/a | del sys.argv[1] |
|---|
| 77 | n/a | if sys.argv[1:]: |
|---|
| 78 | n/a | n = int(sys.argv[1]) |
|---|
| 79 | n/a | q = Queens(n) |
|---|
| 80 | n/a | q.silent = silent |
|---|
| 81 | n/a | q.solve() |
|---|
| 82 | n/a | print("Found", q.nfound, "solutions.") |
|---|
| 83 | n/a | |
|---|
| 84 | n/a | if __name__ == "__main__": |
|---|
| 85 | n/a | main() |
|---|
