问题51：N-皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数n，返回所有不同的n皇后问题的解决方案。每一种解法包含一个明确的n皇后问题的棋子放置方案，该方案中'Q'和'.'分别代表了皇后和空位。
示例：
来源：力扣（LeetCode）
链接：https://leetcode.com/problems/n-queens
这道题和数独问题比较类似，但是比数独问题简单很多，因为数独问题的不重复条件是行+列+九宫格，而N-皇后问题的不重复条件是行+列+对角线，而且，数独问题每个格有九种选择，而本题每个格只有两种选择，即“有皇后”和“无皇后”。
由于每行有且只有一个皇后，我们可以设定一个列表nums，而不需要嵌套列表。其中，nums的第i项元素，代表第i行中皇后的位置。例如，nums=[3,6,2,7,1,4,0,5]即为下图解法。
这道题没有捷径，必须用穷举法，试探每一种情况。
由于每行只有一个皇后，因此不可能存在同一行有两个皇后的情况，条件一自然可以满足。
对于条件二，假设我们已有了row-1行的有效解nums，考虑第row行。遍历，每次选取0到n-1中的一个值nums_new。第row行选取值nums_new，意味着把第row行的皇后在第nums_new列。如果nums_new已经在nums中存在，则会出现同一列中有两个皇后的情况，舍弃nums_new；如果nums_new不在nums中，则把第row行的皇后放在nums_new列，不会产生列冲突，因此将nums_new添加到nums中。
对于条件三，假设第row行我们采用了nums_new，不产生行冲突和列冲突，下面要判断是否会产生对角线冲突，这也是本题的重点。方法是，遍历第0到第row-1行，每次获得一个数组(row_old, nums[row_old])。如果abs(row - row_old)和abs(nums_new - nums[row_old]))相等，则说明产生了列冲突。如果前面所有行中的皇后都没有和新行的皇后产生列冲突，则满足条件三。
完整代码如下：
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
result = []
def dfs(nums, row):
if row == n:
result.append(copy.deepcopy(nums))
return
for nums_new in range(0, n):
if nums_new not in nums:
nums.append(nums_new)
diagonal = 0
for row_old in range(0, row):
if abs(nums_new - nums[row_old]) == (row - row_old):
nums.pop()
diagonal = 1
break
if diagonal == 1:
continue
dfs(nums, row + 1)
nums.pop()
dfs([], 0)
ans = []
for result0 in result:
ans0 = [["." for _ in range(n)] for _ in range(n)]
for line, row in enumerate(result0):
lans0 = list(ans0[line])
lans0[row] = 'Q'
ans0[line] = ''.join(lans0)
ans.append(ans0)
return(ans)
注： 更改字符串中某个位置的值，要先把字符串转换成列表，替换后，再转换回字符串，如下所示。
def replace_char(str,char,index):
list_str = list(str) #将字符串转换成列表
list_str[index] = char #把列表中位置index的值改为char
return ''.join(string) #把修改后的列表转换回字符串
运行结果：
