'''
8皇后問題
'''n = 8 
x = []  # 一個解（n元數組）
X = []  # 一組解# 沖突檢測：判斷 x[k] 是否與前 x[0~k-1] 沖突
def conflict(k):global xfor i in range(k):                              # 遍歷前 x[0~k-1]if x[i]==x[k] or abs(x[i]-x[k])==abs(i-k):  # 判斷是否與 x[k] 沖突return Truereturn False# 套用子集樹模板
def queens(k): # 到達第k行global n, x, Xif k >= n:         # 超出最底行#print(x)X.append(x[:]) # 保存（一個解），注意x[:]else:for i in range(n):  # 遍歷第 0~n-1 列（即n個狀態）x.append(i)     # 皇后置于第i列，入棧if not conflict(k): # 剪枝queens(k+1)x.pop()         # 回溯，出棧# 解的可視化（根據一個解x，復原棋盤。'X'表示皇后）
def show(x):global nfor i in range(n):print('. ' * (x[i]) + 'X ' + '. '*(n-x[i]-1))# 測試
queens(0) # 從第0行開始print(X[-1], '\n')
show(X[-1])