-
Notifications
You must be signed in to change notification settings - Fork 2
/
0-nqueens.py
executable file
·91 lines (81 loc) · 2.36 KB
/
0-nqueens.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#!/usr/bin/python3
'''N-Queens Challenge'''
import sys
if __name__ == '__main__':
if len(sys.argv) != 2:
print("Usage: nqueens N")
sys.exit(1)
try:
n = int(sys.argv[1])
except ValueError:
print('N must be a number')
exit(1)
if n < 4:
print('N must be at least 4')
exit(1)
solutions = []
placed_queens = [] # coordinates format [row, column]
stop = False
r = 0
c = 0
# iterate thru rows
while r < n:
goback = False
# iterate thru columns
while c < n:
# check is current column is safe
safe = True
for cord in placed_queens:
col = cord[1]
if(col == c or col + (r-cord[0]) == c or
col - (r-cord[0]) == c):
safe = False
break
if not safe:
if c == n - 1:
goback = True
break
c += 1
continue
# place queen
cords = [r, c]
placed_queens.append(cords)
# if last row, append solution and reset all to last unfinished row
# and last safe column in that row
if r == n - 1:
solutions.append(placed_queens[:])
for cord in placed_queens:
if cord[1] < n - 1:
r = cord[0]
c = cord[1]
for i in range(n - r):
placed_queens.pop()
if r == n - 1 and c == n - 1:
placed_queens = []
stop = True
r -= 1
c += 1
else:
c = 0
break
if stop:
break
# on fail: go back to previous row
# and continue from last safe column + 1
if goback:
r -= 1
while r >= 0:
c = placed_queens[r][1] + 1
del placed_queens[r] # delete previous queen coordinates
if c < n:
break
r -= 1
if r < 0:
break
continue
r += 1
for idx, val in enumerate(solutions):
if idx == len(solutions) - 1:
print(val, end='')
else:
print(val)