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
| N = int(input())
queens = [0 for _ in range(N)]
board = [[0 for _ in range(N)] for _ in range(N)]
def update_board(board, row, col, x):
for _col in range(N):
board[row][_col] += x
for _row in range(N):
board[_row][col] += x
# (+1, +1)
_row = row
_col = col
while _row + 1 < N and _col + 1 < N:
_row += 1
_col += 1
board[_row][_col] += x
# (+1, -1)
_row = row
_col = col
while _row + 1 < N and 0 <= _col - 1:
_row += 1
_col -= 1
board[_row][_col] += x
# (-1, +1)
_row = row
_col = col
while 0 <= _row -1 and _col + 1 < N:
_row -= 1
_col += 1
board[_row][_col] += x
# (-1, -1)
_row = row
_col = col
while 0 <= _row - 1 and 0 <= _col - 1:
_row -= 1
_col -= 1
board[_row][_col] += x
def set_queens(queens, board, row):
if row == N:
# print board with Qs
for col in queens:
print("." * col + "Q" + "." * (N - col - 1))
print()
return
for col in range(N):
if board[row][col] == 0:
queens[row] = col
update_board(board, row, col, +1)
set_queens(queens, board, row + 1)
update_board(board, row, col, -1)
set_queens(queens, board, 0)
|