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
|
def eight_queen():
"""
八皇后
因为只需存储八个位置的数, 压缩数组, 下标存储行, 值存储列
回溯换路
"""
place = [-1 for _ in range(8)]
def judge_place(row: int, column: int) -> bool:
"""
判断对应row, column是否该放置一个皇后
只需考虑垂直，左斜，右斜
"""
left, right = column - 1, column + 1
for r in range(row - 1, -1, -1):
if place[r] == column:
return False
if left > -1 and left == place[r]:
return False
if right < 8 and right == place[r]:
return False
left -= 1
right += 1
return True
def lay(row: int):
"""
递归计算放置的正确问题
"""
if row == 8:
for r in range(8):
for c in range(8):
if place[r] == c:
print("\tQ\t", end='')
else:
print("\t*\t", end='')
print('\n')
print('\n')
return
for column in range(8):
if judge_place(row, column):
place[row] = column
lay(row + 1)
lay(0)
res = eight_queen()
print(res)
|