算法分析-回溯算法-求解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 True

3.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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。