devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法分析-回溯算法-求解N皇后问题_回溯法求解n皇后问题

作者：IT小白 | 2024-08-22 00:48:18

赞

踩

回溯法求解n皇后问题

一.题目需求

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)判断，这样就不需要写两个公式。

  1.     # 校验是否有效
  2.     def is_valid(board, row, col):
  3.         for i in range(row):
  4.             if board[i] == col or abs(board[i] - col) == abs(i - row):
  5.                 return False
  6.         return True

3.DFS搜索，回溯算法
1）结束条件：当前行数 = 皇后总数，即最后一行已经成功放入皇后
2）循环一行中的每一个位置，若不发生攻击事件，可将皇后放入该位置
3）继续下一行的搜索，即传入的参数为当前行数 + 1

  1.     # DFS搜索，回溯算法
  2.     def backtrack(board, row):
  3.         # 探索行号等于n时结束
  4.         if row == n:
  5.             result.append(board[:])
  6.             return
  7.         # 根据当前行号，再遍历每一列位置
  8.         for col in range(n):
  9.             # 检测当前行号，列号是否有效
  10.             if is_valid(board, row, col):
  11.                 # 有效则设置该位置为皇后
  12.                 board[row] = col
  13.                 # 探索下一行，每次探索一行，放置1个皇后
  14.                 backtrack(board, row + 1)

4.算法分析

这个算法的时间复杂度是O(n!)，因为总共有n!种可能的摆放方式。空间复杂度：O(n)，用于存储递归调用栈。

三.编程实现

根据网上搜集学到的实现代码，多数都采用一维数组方式实现，每次探索每行的每一列，代码更简洁。

实现方法一：

  1. class SolutionNQueens(object):
  2.     '''
  3.     回溯算法-一维数组解决N皇后问题。
  4.     该算法的时间复杂度为：O(n!)，因为总共有n!种可能的摆放方式。空间复杂度：O(n)，用于存储递归调用栈。
  5.     '''
  6.  
  7.     def __init__(self, num):
  8.         self.count = 0
  9.         self.num = num
  10.  
  11.     # 校验当前行号，列号是否有效
  12.     def is_valid(self, board, row, col):
  13.         # 遍历行号
  14.         for i in range(row):
  15.             if board[i] == col or abs(board[i] - col) == abs(i - row):
  16.                 return False
  17.         return True
  18.  
  19.     def backtrack(self, board, row, result):
  20.         if row == self.num:
  21.             result.append(board[:])
  22.             self.count += 1
  23.             return
  24.         for col in range(self.num):
  25.             if self.is_valid(board, row, col):
  26.                 board[row] = col
  27.                 self.backtrack(board, row + 1, result)
  28.                 board[row] = 0
  29.  
  30.     def backtrack_result(self):
  31.         result = []
  32.         # 最终皇后的位置 （下标：第几行 数值：第几列）
  33.         board = [0] * self.num
  34.         # 从第一行开始
  35.         row = 0
  36.         self.backtrack(board, row, result)
  37.         return result
'
运行

同样采用一维数组方式实现，优化减少部分无效列号的遍历，每次探索部分列即可，耗时减少很多。

实现方法二：

  1. class SolutionNQueensNew(object):
  2.     '''
  3.     回溯算法-一维数组解决N皇后问题，优化减少部分无效列号的遍历。
  4.     该算法的时间复杂度为：O(n!)，因为总共有n!种可能的摆放方式。空间复杂度：O(n)，用于存储递归调用栈。
  5.     '''
  6.  
  7.     def __init__(self, num):
  8.         self.count = 0
  9.         self.num = num
  10.  
  11.     # 校验当前行号，列号是否有效
  12.     def is_valid(self, board, row, col):
  13.         # 遍历行号
  14.         for i in range(row):
  15.             if board[i] == col or abs(board[i] - col) == abs(i - row):
  16.                 return False
  17.         return True
  18.  
  19.     def backtrack(self, board, row, range_col, result):
  20.         if row == self.num:
  21.             result.append(board[:])
  22.             self.count += 1
  23.             return
  24.         # 根据当前行号，再遍历列号表中的列号
  25.         for col in range_col:
  26.             if self.is_valid(board, row, col):
  27.                 # 有效则设置该位为 皇后
  28.                 board[row] = col
  29.                 # 列号表中删除该皇后位的列号,减少无效遍历次数
  30.                 range_col.remove(col)
  31.                 # 探索下一行，每次探索一行，放置1个皇后
  32.                 self.backtrack(board, row + 1, range_col, result)
  33.                 # 探索失败，回溯，还原该位置为 0-空位
  34.                 board[row] = 0
  35.                 # 还原列号表，列表尾部添加元素
  36.                 range_col.append(col)
  37.                 # sort 增序排序
  38.                 range_col.sort()
  39.  
  40.     def backtrack_result(self):
  41.         result = []
  42.         # 最终皇后的位置 （下标：第几行 数值：第几列）
  43.         board = [0] * self.num
  44.         # 从第一行开始
  45.         row = 0
  46.         # 列号表初始化，每一列都探索
  47.         range_col = [i for i in range(self.num)]
  48.         self.backtrack(board, row, range_col, result)
  49.         return result
'
运行

采用二维数组方式实现，每次探索每行每列，代码稍微复杂点，检测是否有效方法也不同。

实现方法三：

  1. def solve_n_queens(n):
  2.     '''
  3.     回溯算法-二维数组解决N皇后问题
  4.     该算法的时间复杂度为：O(n!)，因为总共有n!种可能的摆放方式。空间复杂度：O(n)，用于存储递归调用栈。
  5.     '''
  6.  
  7.     def is_valid(board, row, col):
  8.         '''
  9.         board（一个二维列表，表示棋盘），
  10.         row（一个整数，表示要检查的行索引），
  11.         col（一个整数，表示要检查的列索引）。
  12.         函数的目的是检查在给定的行和列上放置一个皇后是否有效。
  13.         '''
  14.  
  15.         '''
  16.         函数首先遍历当前行之前的所有行，检查是否有任何皇后在同一列上。
  17.         如果有，函数返回False，表示放置皇后无效。
  18.         '''
  19.         for i in range(row):
  20.             if board[i][col] == 1:
  21.                 return False
  22.         '''
  23.         zip循环检查左上对角线上的单元格。如果在这些单元格中找到一个皇后，函数同样返回False。
  24.         '''
  25.         for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
  26.             if board[i][j] == 1:
  27.                 return False
  28.         '''
  29.         zip循环检查右上对角线上的单元格。如果在这些单元格中找到一个皇后，函数同样返回False。
  30.         '''
  31.         for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
  32.             if board[i][j] == 1:
  33.                 return False
  34.         return True
  35.  
  36.     def backtrack(board, row):
  37.         # 探索行号等于N时结束
  38.         if row == n:
  39.             # 将棋盘可行方案数据添加到结果列表中
  40.             result.append([[board[i][j] for j in range(n)] for i in range(n)])return
  41.         # 根据当前行号，再遍历列号
  42.         for col in range(n):# 检测当前行号，列号是否有效
  43.             if is_valid(board, row, col):
  44.                 # 有效则设置该方格为 1-皇后
  45.                 board[row][col] = 1
  46.                 # 探索下一行，每次探索一行，放置1个皇后
  47.                 backtrack(board, row + 1)
  48.                 # 探索失败，回溯，还原该方格为 0-空位
  49.                 board[row][col] = 0
  50.  
  51.     # 返回结果列表
  52.     result = []# 创建n×n的棋盘,2维数组,其中1表示皇后，0表示空格
  53.     board = [[0] * n for _ in range(n)]
  54.     # 回溯算法，从第1行开始探索
  55.     backtrack(board, 0)
  56.     return result

采用二维数组方式实现，优化减少部分无效列号的遍历，每次探索部分列即可，耗时减少很多。

实现方法四：

  1. def solve_n_queens_new(n):
  2.     '''
  3.     回溯算法-二维数组解决N皇后问题，优化减少部分无效列号的遍历。
  4.     该算法的时间复杂度为：O(n!)，因为总共有n!种可能的摆放方式。空间复杂度：O(n)，用于存储递归调用栈。
  5.     '''
  6.  
  7.     def is_valid(board, row, col):
  8.         '''
  9.         board（一个二维列表，表示棋盘），
  10.         row（一个整数，表示要检查的行索引），
  11.         col（一个整数，表示要检查的列索引）。
  12.         函数的目的是检查在给定的行和列上放置一个皇后是否有效。
  13.         '''
  14.  
  15.         '''
  16.         zip循环检查左上对角线上的单元格。如果在这些单元格中找到一个皇后，函数同样返回False。
  17.         '''
  18.         for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
  19.             if board[i][j] == 1:
  20.                 return False
  21.         '''
  22.         zip循环检查右上对角线上的单元格。如果在这些单元格中找到一个皇后，函数同样返回False。
  23.         '''
  24.         for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
  25.             if board[i][j] == 1:
  26.                 return False
  27.  
  28.         '''
  29.         函数首先遍历当前行之前的所有行，检查是否有任何皇后在同一列上。
  30.         如果有，函数返回False，表示放置皇后无效。
  31.         '''
  32.         for i in range(row):
  33.             if board[i][col] == 1:
  34.                 return False
  35.         return True
  36.  
  37.     def backtrack(board, row, range_col):
  38.         # 探索行号等于N时结束
  39.         if row == n:
  40.             # 将棋盘可行方案数据添加到结果列表中
  41.             result.append([[board[i][j] for j in range(n)] for i in range(n)])return
  42.         # 根据当前行号，再遍历列号表中的列号
  43.         for col in range_col:# 检测当前行号，列号是否有效
  44.             if is_valid(board, row, col):
  45.                 # 有效则设置该方格为 1-皇后
  46.                 board[row][col] = 1
  47.                 # 列号表中删除该皇后位的列号,减少无效遍历次数
  48.                 range_col.remove(col)
  49.                 # 探索下一行，每次探索一行，放置1个皇后
  50.                 backtrack(board, row + 1, range_col)
  51.                 # 探索失败，回溯，还原该方格为 0-空位
  52.                 board[row][col] = 0
  53.                 # 还原列号表，列表尾部添加元素
  54.                 range_col.append(col)
  55.                 # sort 增序排序
  56.                 range_col.sort()
  57.  
  58.     # 返回结果列表
  59.     result = []# 创建n×n的棋盘,2维数组,其中1表示皇后，0表示空格
  60.     board = [[0] * n for _ in range(n)]
  61.     # 列号表初始化，每一列都探索
  62.     range_col = [i for i in range(n)]
  63.     # 回溯算法，从第1行开始探索
  64.     backtrack(board, 0, range_col)
  65.     return result

四.运行结果

1，4种方法测试对比下耗时。

经过部分优化，减少已排放皇后位对应列号探测，明显可以减少整体耗时。

  1. if __name__ == '__main__':
  2.  
  3.     nums = 10
  4.     all_dis_time = 0.0
  5.     # 循环10次，求平均值
  6.     for i in range(nums):
  7.         start_time = time.time()
  8.         ###############################
  9.         # num: 皇后的数量
  10.         n = 10
  11.         '''
  12.             回溯算法-一维数组解决N皇后问题
  13.             皇后的数量 = 10
  14.             可行方案数： 724
  15.             平均时间:180.8545毫秒
  16.         '''
  17.         # s = SolutionNQueens(n)
  18.         '''
  19.             回溯算法-一维数组解决N皇后问题，优化减少部分无效列号的遍历.
  20.             皇后的数量 = 10
  21.             可行方案数： 724
  22.             平均时间:78.5564毫秒
  23.         '''
  24.         s = SolutionNQueensNew(n)
  25.         # 参数：皇后总数  位置结果  当前放置第几行
  26.         solutions = s.backtrack_result()
  27.         print('可行方案数：', s.count)
  28.         # 打印皇后在棋盘位置
  29.         # for solution in solutions:
  30.         #     print('======================')
  31.         #     for row in solution:
  32.         #         print(" ▢ " * row + " Q " + " ▢ " * (n - row - 1))
  33.         # print('======================')
  34.         '''
  35.         回溯算法-二维数组解决N皇后问题
  36.         皇后的数量 = 10
  37.         可行方案数： 724
  38.         平均时间:199.6063毫秒
  39.         '''
  40.         # grid_board = solve_n_queens(n)
  41.         '''
  42.         回溯算法-二维数组解决N皇后问题，优化减少部分无效列号的遍历.
  43.         皇后的数量 = 10
  44.         可行方案数： 724
  45.         平均时间:117.3587毫秒
  46.         '''
  47.         # grid_board = solve_n_queens_new(n)
  48.         # rst_nums = len(grid_board)
  49.         # print("可行方案数：", rst_nums)
  50.  
  51.         # for i in range(rst_nums):
  52.         #     print("方案：", (i + 1))
  53.         #     # 打印网格地图
  54.         #     grid_print(grid_board[i])
  55.         ###############################
  56.         # 识别时间
  57.         end_time = time.time()
  58.         # 计算耗时差，单位毫秒
  59.         dis_time = (end_time - start_time) * 1000
  60.         # 保留2位小数
  61.         dis_time = round(dis_time, 4)
  62.         all_dis_time += dis_time
  63.         print('时间:' + str(dis_time) + '毫秒')
  64.         print('=============================')
  65.     pre_dis_time = all_dis_time / nums
  66.     # 保留4位小数
  67.     pre_dis_time = round(pre_dis_time, 4)
  68.     print('平均时间:' + str(pre_dis_time) + '毫秒')

2，动态演示求解4皇后问题完整过程。

 =====================end =====================

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/1013987
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号