AcWing 843. n-皇后问题2 python
原题链接
中等
作者:
戈好雨
,
2019-10-09 18:10:03
,
所有人可见
,
阅读 947
import copy
def dfs(x, y, s): # 对于第x行,第y列,第s个queen
global N
if s > N:
return
if y == N:
y = 0
x += 1
if x == N:
if s == N:
ans.append(copy.deepcopy(graph))
return
dfs(x, y + 1, s)
if state_row[x] == False and state_col[y] == False and state_dg[x + y] == False and state_bdg[N + x - y] == False:
graph[x][y] = 'Q'
state_row[x] = state_col[y] = state_dg[x + y] = state_bdg[N + x - y] = True
dfs(x, y + 1, s + 1)
state_row[x] = state_col[y] = state_dg[x + y] = state_bdg[N + x - y] = False
graph[x][y] = '.'
N = int(input())
ans = []
state_row = [False] * N
state_col = [False] * N
state_dg = [False] * 2 * N
state_bdg = [False] * 2 * N
graph = [['.'] * N for i in range(N)]
dfs(0,0,0)
for i in range(len(ans)):
for u in range(len(ans[i])):
print(''.join(ans[i][u]))
print('')