原題
n皇后問題是將n個皇后放置在n*n的棋盤上躏吊，皇后彼此之間不能相互攻擊氛改。
給定一個整數(shù)n，返回所有不同的n皇后問題的解決方案比伏。
每個解決方案包含一個明確的n皇后放置布局胜卤，其中“Q”和“.”分別表示一個女王和一個空位置。
樣例
對于4皇后問題存在兩種解決的方案：
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
n-queen puzzle
解題思路
Paste_Image.png
- 本題需要三個helper函數(shù)來輔助赁项，使得代碼更加清晰葛躏，第一需要DFS函數(shù)，過程如上圖所示悠菜。一行一行的放置queen舰攒，當出現(xiàn)非法的情況時，直接返回上一級 - backtracking的思路
# backtracking
cols.append(col) # 加
self.dfs(cols)
cols.pop() # 減
# 等效于
self.dfs(cols + [col])
- 第二個函數(shù)就是判斷某一點放queen是否合法
- 因為是一行一行放悔醋，所以可以保證不在一行上
- 全局變量cols記錄了那一列已經(jīng)放置了queen摩窃，通過檢查當前列是否在其中，即可判斷是不是同一列有兩個queen。同時cols的長度也表示已經(jīng)有多少行放置好了queen猾愿，當len(cols) == n的時候可以drawboard并加入result中
- 同時還有檢查對角線鹦聪，左上右下和左下右上
- 第三個函數(shù)是根據(jù)cols數(shù)組畫出board，相對簡單蒂秘。比如[2, 4, 1, 3]表示第一行queen在第二列泽本，第二行queen在第四列，第三行queen在第一列姻僧，第四行queen在第三列
完整代碼
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
result = []
if n <= 0:
return result
cols = []
self.search(n, cols, result);
return result
def search(self, n, cols, result):
if len(cols) == n:
result.append(self.drawBoard(cols))
return
for col in range(n):
if not self.isValid(cols, col):
continue
self.search(n, cols + [col], result)
def isValid(self, cols, col):
currentRowNumber = len(cols)
for i in range(currentRowNumber):
# same column
if cols[i] == col:
return False
# left-top to right-bottom
if i - cols[i] == currentRowNumber - col:
return False
# right-top to left-bottom
if i + cols[i] == currentRowNumber + col:
return False
return True
def drawBoard(self, cols):
board = []
for i in range(len(cols)):
line = ""
for j in range(len(cols)):
if j == cols[i]:
line += "Q"
else:
line += "."
board.append(line)
return board
