算法分析-回溯算法-求解N皇后问题
2023-12-28 16:59:20
一.题目需求
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 False
return 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 = 0
self.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 False
return True
def backtrack(self, board, row, result):
if row == self.num:
result.append(board[:])
self.count += 1
return
for col in range(self.num):
if self.is_valid(board, row, col):
board[row] = col
self.backtrack(board, row + 1, result)
board[row] = 0
def backtrack_result(self):
result = []
# 最终皇后的位置 （下标：第几行 数值：第几列）
board = [0] * self.num
# 从第一行开始
row = 0
self.backtrack(board, row, result)
return result同样采用一维数组方式实现，优化减少部分无效列号的遍历，每次探索部分列即可，耗时减少很多。
实现方法二：
class SolutionNQueensNew(object):
'''
回溯算法-一维数组解决N皇后问题，优化减少部分无效列号的遍历。
该算法的时间复杂度为：O(n!)，因为总共有n!种可能的摆放方式。空间复杂度：O(n)，用于存储递归调用栈。
'''
def __init__(self, num):
self.count = 0
self.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 False
return True
def backtrack(self, board, row, range_col, result):
if row == self.num:
result.append(board[:])
self.count += 1
return
# 根据当前行号，再遍历列号表中的列号
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 False
return True
def 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 False
return True
def 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 = 10
all_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_time
print('时间:' + 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?=====================
文章来源:https://blog.csdn.net/xionghui2007/article/details/135271529
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！