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() |
---|