回溯算法——四皇后问题

一、回溯算法概述

回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。其核心思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。具体来说，回溯算法通过递归或迭代的方式，在解空间中搜索所有可能的解，并在遇到不符合条件的情况时回溯到前一步，尝试其他路径。
在解决具体问题时，回溯算法通常与剪枝技术结合使用，即在搜索过程中提前判断某些路径不可能得到解，从而避免无效搜索，提高算法效率。
回溯算法在解决组合问题、搜索问题、优化问题等方面有着广泛的应用，如四皇后问题、图的着色问题、旅行商问题等。通过回溯算法，我们可以系统地搜索所有可能的解，从而找到问题的所有答案或最优解。以下是一个四皇后问题的推广，可用于解决n皇后问题。

二、问题描述
四皇后问题：如何能够在4*4的国际象棋棋盘上要放置4个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为达到此目的，要求任何两个皇后都不能处于同一条横行、纵列或斜线上，即任何两个皇后都处于不同行、不同列、不同对角线。

三、代码实现

# 夜阑专用捏
# 开发时间：2024/4/26 21:43
try:
    # 获取用户输入的棋盘大小n
    a = int(input('将n个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击,此处的n我们将设置为多少呢'))
    # 回溯函数，用于尝试放置皇后
    def back_track(line_num, n, queens, solutions, columns, diagonal1, diagonal2):
        if line_num == n:
            # 生成棋盘字符串表示并添加到解决方案列表中
            result = [''.join(['Q' if queens[line] == col else '.' for col in range(n)]) for line in range(n)]
            solutions.append(result)
            return

        # 遍历当前行的每一列
        for i in range(n):
            # 如果当前列或对角线已经有皇后，则跳过
            if i in columns or line_num - i in diagonal1 or line_num + i in diagonal2:
                continue
            # 在当前位置放置皇后
            queens[line_num] = i
            # 更新列和对角线占用情况
            columns.append(i)
            diagonal1.append(line_num - i)
            diagonal2.append(line_num + i)
            # 递归放置下一个皇后
            back_track(line_num + 1, n, queens, solutions, columns, diagonal1, diagonal2)
            # 回溯，撤销当前皇后的放置
            columns.pop()
            diagonal1.pop()
            diagonal2.pop()
    def solve_n_queens(n):
        # 初始化解决方案列表和皇后位置数组
        solutions = []
        queens = [-1] * n
        # 初始化列和对角线占用情况列表
        columns = []
        diagonal1 = []
        diagonal2 = []
        # 开始回溯过程
        back_track(0, n, queens, solutions, columns, diagonal1, diagonal2)
        # 返回所有解决方案
        return solutions

    if __name__ == '__main__':
        solutions = solve_n_queens(a)
        print('将{0}个皇后放在{1}×{2}的棋盘上，此时共有{3}种解法'.format(a, a, a, len(solutions)))
        # 打印每个解决方案的棋盘状态
        for solution in solutions:
            print("*" * 20)
            for row in solution:
                print(row)

except BaseException as e:
    print('出错了！', e)

三、实验报告

211004680215-39-龙圆芝-实验2 逻辑推理实验