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