面试题 08.12. 八皇后 设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列， 也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。 注意：本题相对原题做了扩展
示例:
输入：4 输出：[[".Q…","…Q",“Q…”,"…Q."],["…Q.",“Q…”,"…Q",".Q…"]] 解释: 4 皇后问题存在如下两个不同的解法。 [ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”],
["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ]
首先是一种回溯方法，当前位置合格就放入Q，回溯，删除Q。
from typing import List class Solution: def solveNQueens(self, n: int) -> List[List[str]]: out = [] board = [["."]*n for _ in range(n)] def is_vaild(board,row,col, n): for i in range(1,min(row,col)+1): if board[row-i][col-i] == 'Q': return False for i in range(1,min(row+1, n-col)): if board[row-i][col+i] == 'Q': return False for j in range(row): if board[j][col] == 'Q': return False return True def backtrack(board, row: int): if row == n: res = [] for j in board: res.append(''.join(j)) out.append(res) return for col in range(n): if not is_vaild(board,row,col,n): continue board[row][col] = 'Q' backtrack(board, row+1) board[row][col] = '.' backtrack(board, 0) return out if __name__ == "__main__": s = Solution() print(s.solveNQueens(8))经过提交后发现速度不是很快，因为在判断当前位置是否合法的地方存在这大量的计算，所以可以使用一个表格对已经填充过的位置进行记录。在验证的时候就不用一个一个再去判断了。
使用表格记录的回溯方法如下：建议三个表格，分别为左对角线，右对角线，竖直方向。如果有Q值记录在里面就跳出当前的循环，删除上一个Q值，进行回溯。 这种方式相对与之前的逐个比较就会快很多。
class Solution: def solveNQueens(self, n: int) -> List[List[str]]: out = [] board = [["."]*n for _ in range(n)] def backtrack(left_diagonal,right_diagonal,column): row = len(column) if row == n: res = [] for j in board: res.append(''.join(j)) out.append(res) return for col in range(n): if col in column or (row - col) in left_diagonal or (row + col) in right_diagonal: continue board[row][col] = 'Q' backtrack(left_diagonal + [row-col],right_diagonal + [row+col],column + [col]) board[row][col] = '.' backtrack([],[],[]) return out之后发现每次都需要计算当前column内的个数作为row的行数，所以考虑结合上面两种方法，将row代入到回溯函数中去。这样就不需每次都计算当前的行数值，减少运算。
class Solution: def solveNQueens(self, n: int) -> List[List[str]]: out = [] board = [["."]*n for _ in range(n)] def backtrack(board, row: int,left_diagonal,right_diagonal,column): if row == n: res = [] for j in board: res.append(''.join(j)) out.append(res) return for col in range(n): if col in column or (row - col) in left_diagonal or (row + col) in right_diagonal: continue board[row][col] = 'Q' backtrack(board, row+1,left_diagonal + [row-col],right_diagonal + [row+col],column + [col]) board[row][col] = '.' backtrack(board, 0,[],[],[]) return out