n皇后

1.解法

n皇后问题是比较经典的棋盘问题。而棋盘问题也是回溯问题中的一种。

总体思路是：按照行（或列）遍历，首先确定第一行的一个皇后的位置，然后去确定第二行皇后的位置（确定的方法就是1.不能同行 2.不能同列 3.不能在对角线），然后去确定第三行的皇后…直到确定到最后一行。如果最后一行能找到一个答案，那么就可以把答案保存下来；如果在中途（即遍历的行小于n）就找不到了，那么对把上一行确定的皇后取消，然后使得上一行的下一个位置为皇后，重复同样的操作。

n=3时，如图所示（图中只具体画了第一行取1的部分）：

确定了总体思路，我们就可以执行回溯三部曲：

1. 确定函数头和辅助变量：

    result = [] # 存放所有结果chessboard = [ ['.']*n for _ in range(n) ] # 棋盘初始化'''1.遍历结束的时候就是row==n的时候，所以需要n2.每次进行遍历的时候都要知道要遍历哪行，所以要有row3.每次遍历都要修改棋盘，所以要有chessboard'''def backtracking(n,row,chessboard): 
   

2. 确定递归出口：

   前面也说了，当此次递归（遍历）的行数row==n的时候，那么就证明已经有了一个答案。

    if row == n:# 由于棋盘每一行都是一个list，而答案每一行都是一个字符串，所以要转换一下temp_res = []for temp in chessboard:temp_str = "".join(temp)temp_res.append(temp_str)result.append(temp_res)return
   

3. 确定递归逻辑：

   因为递归本身是对行的遍历，所以我们只要再遍历列，就可以遍历每行中每一个位置了，所以需要一个for循环来遍历所有列，如果刚确定的[row][col]这个位置和chessboard上已有的皇后位置不冲突，那么就可以使得chessboard[row][col] = ‘Q’，然后进行下一行的递归，完成下一行递归后要回溯。

    for col in range(n):if isValid(row,col,chessboard,n): # isValid用来判断(row,col)位置上放皇后合不合法chessboard[row][col] = 'Q'backtracking(n,row+1,chessboard)chessboard[row][col] = '.'
   

4. 这道题还有一个问题就是如何判断(row,col)位置上放皇后合不合法？换言之，就是isValid函数要怎么写？

   首先我们来看三个限制条件：

   1. 不能同行
   2. 不能同列
   3. 不能同对角线

   这里先给出代码：

    def isValid(row,col,chessboard,n):# 检查列 # 细节在于i遍历到row-1即可，因为下面的行还没有确定皇后，所以肯定没有Qfor i in range(row): if chessboard[i][col]=='Q':return False# 检查左上角i = row - 1j = col - 1while i>=0 and j>=0:if chessboard[i][j]=='Q':return Falsei -= 1j -= 1# 检查右上角i = row - 1j = col + 1while i>=0 and j<=n-1:if chessboard[i][j]=='Q':return Falsei -= 1j += 1return True
   

   可以发现几个问题。

   1. 检查列的时候为什么 for i in range(row) 而不是 for i in range(n)
   2. 为什么没有检查行
   3. 为什么没有检查左下角和右下角

   因为在该层递归执行时，只确定该行的一个位置，所以不需要检查行，因为该行下只能有一个Q。而且在确定该行时，就表示刚刚执行到该行，下面的行还没有确定Q，所以检查列只需要for i in range(row)即可，而且也不用检查左下角和右下角。

整体代码为：

def solveNQueens(n):result = []chessboard = [ ['.']*n for _ in range(n) ]def isValid(row,col,chessboard,n):# 检查列for i in range(n):if chessboard[i][col]=='Q':return False# 检查左上角i = row - 1j = col - 1while i>=0 and j>=0:if chessboard[i][j]=='Q':return Falsei -= 1j -= 1# 检查右上角i = row - 1j = col + 1while i>=0 and j<=n-1:if chessboard[i][j]=='Q':return Falsei -= 1j += 1return Truedef backtracking(n,row,chessboard):if row == n:temp_res = []for temp in chessboard:temp_str = "".join(temp)temp_res.append(temp_str)result.append(temp_res)returnfor col in range(n):if isValid(row,col,chessboard,n):chessboard[row][col] = 'Q'backtracking(n,row+1,chessboard)chessboard[row][col] = '.'backtracking(n,0,chessboard)return result

2.总结

python

字符列表转字符串：

'''
temp = ['a','b','c','d']
'''
temp_str = "".join(temp)
'''
temp_str = "abcd"
'''