from typing import List# 八皇後問題，用遞歸的方法來寫。class Solution: def solveNQueens(self, n: int) -> List[List[str]]: # 如果n < 1直接返回空列表 if n < 1:return [] # 定義變數用 ...
from typing import List
# 八皇後問題，用遞歸的方法來寫。
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
# 如果n < 1直接返回空列表
if n < 1:return []
# 定義變數用來存放最後的結果
self.res = []
# 定義幾個集合，用來確保行和列，對角線只有一個皇後，
# 這裡我們以行來遍歷，因此只需要定義列，兩個對角線
self.col,self.pie,self.na = set(),set(),set()
self.dfs(n,0,[])
return self.res
def dfs(self,n,row,cur):
# 遞歸完成，將結果放入self.res
if row == n:
# 註意這裡的寫法。
# 不能寫成self.res.append(cur)
self.res.append(cur[:])
return
# 進行遍歷列。
for index in range(n):
# 確保當前行，列，對角線沒有皇後
if index in self.col or index + row in self.pie or index - row in self.na :
continue
str1 = ""
# 進行字元串的拼接
for index1 in range(n):
if index1 == index :
str1 += "Q"
else :str1 += "."
# cur為臨時列表
cur.append(str1)
# 已經添加過字元串了，因此將當前行，列對角線的值寫入集合
self.col.add(index)
self.pie.add(index + row)
self.na.add(index - row)
# 然後進行遞歸下一行
self.dfs(n,row + 1,cur)
# 註意遞歸完成後一定要清除當前行列，對角線的數據。
cur.remove(str1)
self.col.remove(index)
self.pie.remove(index + row)
self.na.remove(index - row)
A = Solution()
print(A.solveNQueens(8))
print(A.solveNQueens(4))
