题目链接：
51.N皇后
对8皇后问题其实早有耳闻，今天刚好看到这个题目，那就把这个题目搞明白。还是用了回溯算法，其实就是选择，试探，撤销。就是这三个步骤，首先回溯的结束条件要明确，那就是row==n了，就结束回溯。枚举所有列，然后选择，在进行递归，然后进行撤销操作。在枚举的这个循环下面，选择，递归，撤销这三个步骤是紧紧的挨着的。
N皇后的问题就是然这N个皇后和平相处就行，所谓和平相处就是一行、一列、一条对角线只能有一个皇后。
示例： 输入：4 输出：[ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。 class Solution: def solveNQueens(self, n: int) -> List[List[str]]: #初始化一个矩阵 dp = [['.' for _ in range(n)] for _ in range(n)] res = [] print(dp) #回溯方法 def backtracking(nums,row): #回溯结束条件 if row==n: res.append(helper(nums)) return #枚举所有可能性 for col in range(n): #如果这个位置能放皇后,那就就进行选择->递归->撤销等一系操作 if isvalid(dp,row,col): dp[row][col]='Q' backtracking(nums,row+1) dp[row][col]='.' #这个函数是将结果矩阵转成字符串矩阵 def helper(nums): temp=[] for i in nums: temp.append("".join(i)) return temp #用这个函数来判断能不能再该位置放皇后 def isvalid(dp,row,col): #因为这个是下一行,所以对行不需要进行判断,只需要对列进行判断 for i in range(n): if dp[i][col]=='Q': return False #判断左上角 #对行和列进行初始化 mrow, mcol = row, col while mrow > 0 and mcol > 0: mrow-=1 mcol-=1 if dp[mrow][mcol] == 'Q': return False #在对行和列进行初始化 #判断(右上角)副对角线：判断[0:row-1,col+1:n] vrow, vcol = row, col while vrow > 0 and vcol < n-1: vrow-=1 vcol+=1 if dp[vrow][vcol] == 'Q': return False return True #执行回溯算法 backtracking(dp,0) return res总结：回溯算法需要确定的就是枚举的可能性（选择，递归，撤销），退出回溯的条件。
