一.题目需求
n皇后问题是一道比较经典的算法题。它研究的是将n个皇后放置在一个n×n的棋盘上，使皇后彼此之间不相互攻击。
即任意两个皇后都不能处于同一行、同一列或同一斜线上。
二.算法思想
1.构建棋盘
可以用一个n×n列表来表示棋盘，设皇后所在的位置为board[i]，i代表行，board[i]代表列，因此皇后所处的位置就是第i行、第board [i]列。
如下，第一个皇后就处于[0,0]位置（以0为起点，[0,0]意为第一行第一列），第二个皇后就处于[2,3]位置（意为第三行第四列）：
2.不攻击检查
即需要判断：
1）是否处于同一列中
2）是否在左斜线上：（行 + 列）的值不可相等
3）是否在右斜线上：（列 - 行）的值不可相等
这里，每行肯定只有1个皇后，是很显然的，因此不必特别判断，
左右斜线的判断可以用一个绝对值公式abs(board[i] - col) == abs(i - row)判断，这样就不需要写两个公式。
# 校验是否有效def is_valid(board, row, col):for i in range(row):if board[i] == col or abs(board[i] - col) == abs(i - row):return Falsereturn True3.DFS搜索，回溯算法
1）结束条件：当前行数 = 皇后总数，即最后一行已经成功放入皇后
2）循环一行中的每一个位置，若不发生攻击事件，可将皇后放入该位置
3）继续下一行的搜索，即传入的参数为当前行数 + 1
# DFS搜索，回溯算法def backtrack(board, row):# 探索行号等于n时结束if row == n:result.append(board[:])return# 根据当前行号，再遍历每一列位置for col in range(n):# 检测当前行号，列号是否有效if is_valid(board, row, col):# 有效则设置该位置为皇后board[row] = col# 探索下一行，每次探索一行，放置1个皇后backtrack(board, row + 1)4.算法分析
这个算法的时间复杂度是O(n!)，因为总共有n!种可能的摆放方式。空间复杂度：O(n)，用于存储递归调用栈。
三.编程实现
根据网上搜集学到的实现代码，多数都采用一维数组方式实现，每次探索每行的每一列，代码更简洁。
实现方法一：
class SolutionNQueens(object):'''回溯算法-一维数组解决N皇后问题。该算法的时间复杂度为：O(n!)，因为总共有n!种可能的摆放方式。空间复杂度：O(n)，用于存储递归调用栈。'''def __init__(self, num):self.count = 0self.num = num# 校验当前行号，列号是否有效def is_valid(self, board, row, col):# 遍历行号for i in range(row):if board[i] == col or abs(board[i] - col) == abs(i - row):return Falsereturn Truedef backtrack(self, board, row, result):if row == self.num:result.append(board[:])self.count += 1returnfor col in range(self.num):if self.is_valid(board, row, col):board[row] = colself.backtrack(board, row + 1, result)board[row] = 0def backtrack_result(self):result = []# 最终皇后的位置 （下标：第几行 数值：第几列）board = [0] * self.num# 从第一行开始row = 0self.backtrack(board, row, result)return result同样采用一维数组方式实现，优化减少部分无效列号的遍历，每次探索部分列即可，耗时减少很多。
实现方法二：
class SolutionNQueensNew(object):'''回溯算法-一维数组解决N皇后问题，优化减少部分无效列号的遍历。该算法的时间复杂度为：O(n!)，因为总共有n!种可能的摆放方式。空间复杂度：O(n)，用于存储递归调用栈。'''def __init__(self, num):self.count = 0self.num = num# 校验当前行号，列号是否有效def is_valid(self, board, row, col):# 遍历行号for i in range(row):if board[i] == col or abs(board[i] - col) == abs(i - row):return Falsereturn Truedef backtrack(self, board, row, range_col, result):if row == self.num:result.append(board[:])self.count += 1return# 根据当前行号，再遍历列号表中的列号for col in range_col:if self.is_valid(board, row, col):# 有效则设置该位为 皇后board[row] = col# 列号表中删除该皇后位的列号,减少无效遍历次数range_col.remove(col)# 探索下一行，每次探索一行，放置1个皇后self.backtrack(board, row + 1, range_col, result)# 探索失败，回溯，还原该位置为 0-空位board[row] = 0# 还原列号表，列表尾部添加元素range_col.append(col)# sort 增序排序range_col.sort()def backtrack_result(self):result = []# 最终皇后的位置 （下标：第几行 数值：第几列）board = [0] * self.num# 从第一行开始row = 0# 列号表初始化，每一列都探索range_col = [i for i in range(self.num)]self.backtrack(board, row, range_col, result)return result采用二维数组方式实现，每次探索每行每列，代码稍微复杂点，检测是否有效方法也不同。
实现方法三：
def solve_n_queens(n):'''回溯算法-二维数组解决N皇后问题该算法的时间复杂度为：O(n!)，因为总共有n!种可能的摆放方式。空间复杂度：O(n)，用于存储递归调用栈。'''def is_valid(board, row, col):'''board（一个二维列表，表示棋盘），row（一个整数，表示要检查的行索引），col（一个整数，表示要检查的列索引）。函数的目的是检查在给定的行和列上放置一个皇后是否有效。''''''函数首先遍历当前行之前的所有行，检查是否有任何皇后在同一列上。如果有，函数返回False，表示放置皇后无效。'''for i in range(row):if board[i][col] == 1:return False'''zip循环检查左上对角线上的单元格。如果在这些单元格中找到一个皇后，函数同样返回False。'''for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):if board[i][j] == 1:return False'''zip循环检查右上对角线上的单元格。如果在这些单元格中找到一个皇后，函数同样返回False。'''for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):if board[i][j] == 1:return Falsereturn Truedef backtrack(board, row):# 探索行号等于N时结束if row == n:# 将棋盘可行方案数据添加到结果列表中result.append([[board[i][j] for j in range(n)] for i in range(n)])return# 根据当前行号，再遍历列号for col in range(n):# 检测当前行号，列号是否有效if is_valid(board, row, col):# 有效则设置该方格为 1-皇后board[row][col] = 1# 探索下一行，每次探索一行，放置1个皇后backtrack(board, row + 1)# 探索失败，回溯，还原该方格为 0-空位board[row][col] = 0# 返回结果列表result = []# 创建n×n的棋盘,2维数组,其中1表示皇后，0表示空格board = [[0] * n for _ in range(n)]# 回溯算法，从第1行开始探索backtrack(board, 0)return result采用二维数组方式实现，优化减少部分无效列号的遍历，每次探索部分列即可，耗时减少很多。
实现方法四：
def solve_n_queens_new(n):'''回溯算法-二维数组解决N皇后问题，优化减少部分无效列号的遍历。该算法的时间复杂度为：O(n!)，因为总共有n!种可能的摆放方式。空间复杂度：O(n)，用于存储递归调用栈。'''def is_valid(board, row, col):'''board（一个二维列表，表示棋盘），row（一个整数，表示要检查的行索引），col（一个整数，表示要检查的列索引）。函数的目的是检查在给定的行和列上放置一个皇后是否有效。''''''zip循环检查左上对角线上的单元格。如果在这些单元格中找到一个皇后，函数同样返回False。'''for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):if board[i][j] == 1:return False'''zip循环检查右上对角线上的单元格。如果在这些单元格中找到一个皇后，函数同样返回False。'''for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):if board[i][j] == 1:return False'''函数首先遍历当前行之前的所有行，检查是否有任何皇后在同一列上。如果有，函数返回False，表示放置皇后无效。'''for i in range(row):if board[i][col] == 1:return Falsereturn Truedef backtrack(board, row, range_col):# 探索行号等于N时结束if row == n:# 将棋盘可行方案数据添加到结果列表中result.append([[board[i][j] for j in range(n)] for i in range(n)])return# 根据当前行号，再遍历列号表中的列号for col in range_col:# 检测当前行号，列号是否有效if is_valid(board, row, col):# 有效则设置该方格为 1-皇后board[row][col] = 1# 列号表中删除该皇后位的列号,减少无效遍历次数range_col.remove(col)# 探索下一行，每次探索一行，放置1个皇后backtrack(board, row + 1, range_col)# 探索失败，回溯，还原该方格为 0-空位board[row][col] = 0# 还原列号表，列表尾部添加元素range_col.append(col)# sort 增序排序range_col.sort()# 返回结果列表result = []# 创建n×n的棋盘,2维数组,其中1表示皇后，0表示空格board = [[0] * n for _ in range(n)]# 列号表初始化，每一列都探索range_col = [i for i in range(n)]# 回溯算法，从第1行开始探索backtrack(board, 0, range_col)return result四.运行结果
1，4种方法测试对比下耗时。
经过部分优化，减少已排放皇后位对应列号探测，明显可以减少整体耗时。
if __name__ == '__main__':nums = 10all_dis_time = 0.0# 循环10次，求平均值for i in range(nums):start_time = time.time()################################ num: 皇后的数量n = 10'''回溯算法-一维数组解决N皇后问题皇后的数量 = 10可行方案数： 724平均时间:180.8545毫秒'''# s = SolutionNQueens(n)'''回溯算法-一维数组解决N皇后问题，优化减少部分无效列号的遍历.皇后的数量 = 10可行方案数： 724平均时间:78.5564毫秒'''s = SolutionNQueensNew(n)# 参数：皇后总数 位置结果 当前放置第几行solutions = s.backtrack_result()print('可行方案数：', s.count)# 打印皇后在棋盘位置# for solution in solutions:# print('======================')# for row in solution:# print(" ▢ " * row + " Q " + " ▢ " * (n - row - 1))# print('======================')'''回溯算法-二维数组解决N皇后问题皇后的数量 = 10可行方案数： 724平均时间:199.6063毫秒'''# grid_board = solve_n_queens(n)'''回溯算法-二维数组解决N皇后问题，优化减少部分无效列号的遍历.皇后的数量 = 10可行方案数： 724平均时间:117.3587毫秒'''# grid_board = solve_n_queens_new(n)# rst_nums = len(grid_board)# print("可行方案数：", rst_nums)# for i in range(rst_nums):# print("方案：", (i + 1))# # 打印网格地图# grid_print(grid_board[i])################################ 识别时间end_time = time.time()# 计算耗时差，单位毫秒dis_time = (end_time - start_time) * 1000# 保留2位小数dis_time = round(dis_time, 4)all_dis_time += dis_timeprint('时间:' + str(dis_time) + '毫秒')print('=============================')pre_dis_time = all_dis_time / nums# 保留4位小数pre_dis_time = round(pre_dis_time, 4)print('平均时间:' + str(pre_dis_time) + '毫秒')2，动态演示求解4皇后问题完整过程。
=====================end =====================
