原题
n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击。
给定一个整数n，返回所有不同的n皇后问题的解决方案。
每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。
样例
对于4皇后问题存在两种解决的方案：
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
n-queen puzzle
解题思路
Paste_Image.png
- 本题需要三个helper函数来辅助，使得代码更加清晰，第一需要DFS函数，过程如上图所示。一行一行的放置queen，当出现非法的情况时，直接返回上一级 - backtracking的思路
# backtracking
cols.append(col) # 加
self.dfs(cols)
cols.pop() # 减
# 等效于
self.dfs(cols + [col])
- 第二个函数就是判断某一点放queen是否合法
- 因为是一行一行放，所以可以保证不在一行上
- 全局变量cols记录了那一列已经放置了queen，通过检查当前列是否在其中，即可判断是不是同一列有两个queen。同时cols的长度也表示已经有多少行放置好了queen，当len(cols) == n的时候可以drawboard并加入result中
- 同时还有检查对角线，左上右下和左下右上
- 第三个函数是根据cols数组画出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
