题目描述
n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击(任意两个皇后不能位于同一行，同一列，同一斜线)。
给定一个整数n，返回所有不同的n皇后问题的解决方案。
每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。
测试样例
输入:1
输出:
[["Q"]]
输入:4
输出:
[
// Solution 1
[".Q..",
"...Q",
"Q...",
"..Q."
],
// Solution 2
["..Q.",
"Q...",
"...Q",
".Q.."
]
]
解题思路
使用DFS，每次对每行可用的列进行搜索，并使用一个list记录下对应已使用的列，这里记为used_cols，使用过的列按其所在行的顺序被加入到其中。每次搜索时，先判断下len(used_cols)是否等于n，如果是，则说明每一行都已选择过了，这时候需要生成解决方案，终止搜索。
此题的另一个重点在于对每一行可用的列进行搜索时，怎么判断某一列可用呢？
题目要求是 任意两个皇后不能位于同一行、同一列、同一斜线，对这个规则转换下，对应变为当前搜索的这一列没有被其它行使用过、当前当前行、列的和以及差都没有出现过。
代码
class Solution:
"""
@param: n: The number of queens
@return: All distinct solutions
"""
def solveNQueens(self, n):
if n == 1:
return [["Q"]]
boards = []
self.dfs(n, [], boards)
return boards
def dfs(self, n, used_cols, boards):
# used_cols里记录的是使用过的列
# 每行对应有一个
if len(used_cols) == n:
boards.append(self.draw(n, used_cols))
return
# used_cols的长度可作为当前行数（从0开始）
cur_row = len(used_cols)
for col in range(n):
if not self.is_valid(used_cols, cur_row, col):
continue
self.dfs(n, used_cols + [col], boards)
def draw(self, n, cols):
board = []
for col in cols:
row_str = ''.join(['Q' if c == col else '.' for c in range(n)])
board.append(row_str)
return board
def is_valid(self, used_cols, cur_row, cur_col):
"""检查列数、行列和、行列差有无被使用过"""
if cur_col in used_cols:
return False
for row, col in enumerate(used_cols):
if cur_row + cur_col == row + col:
return False
if cur_row - cur_col == row - col:
return False
return True
