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))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/86767.html
標籤：Python
上一篇：PHP錯誤與例外
下一篇：Django中的auth模塊