【附源码】Python ：八皇后问题

系列文章目录

Python 算法学习：八皇后问题

文章目录

一、算法需求

八皇后问题是在一个 8×8 的棋盘上放置 8 个皇后，要求它们彼此之间不能互相攻击。我们继续使用回溯算法，并进行一些优化。

回溯算法从棋盘的第一行开始，依次尝试在每一列放置一个皇后。在放置皇后时，我们不仅要检查当前位置是否与已经放置的皇后在同一行、同一列或同一对角线上，还可以利用一些对称性来减少搜索空间。例如，如果我们已经知道在第一行第一列放置皇后无法得到解，那么根据棋盘的对称性，在第一行第八列放置皇后也一定无法得到解，这样就可以避免一些不必要的尝试。

二、具体方法+源码

因为八皇后有很多的情况，如下图所示：

所以我就挑其中一种情况来写，并通过图标展现出来：

代码如下：

import matplotlib.pyplot as plt
import numpy as np

def eight_queens():
    board = [[0] * 8 for _ in range(8)]
    solutions = []

    def is_safe(row, col):
        # 检查列
        for i in range(row):
            if board[i][col]:
                return False
        # 检查左上方对角线
        i, j = row    1, col    1
        while i >= 0 and j >= 0:
            if board[i][j]:
                return False
            i = i    1
            j = j    1
        # 检查右上方对角线
        i, j = row    1, col + 1
        while i >= 0 and j < 8:
            if board[i][j]:
                return False
            i = i    1
            j = j + 1
        return True

    def backtrack(row):
        if row == 8:
            solution = [(i, j) for i in range(8) for j in range(8) if board[i][j]]
            solutions.append(solution)
            return
        for col in range(8):
            if is_safe(row, col):
                board[row][col] = 1
                backtrack(row + 1)
                board[row][col] = 0

    backtrack(0)
    return solutions[0] if solutions else None

def plot_queens(solution):
    fig, ax = plt.subplots()
    ax.set_xticks(np.arange(0.5, 8.5, 1))
    ax.set_yticks(np.arange(0.5, 8.5, 1))
    ax.set_xticklabels([])
    ax.set_yticklabels([])
    ax.grid(color='black', linestyle='  ', linewidth=1)

    for i in range(8):
        for j in range(8):
            if (i, j) in solution:
                ax.add_patch(plt.Circle((j + 0.5, i + 0.5), 0.3, color='r'))

    plt.show()

solution = eight_queens()
if solution:
    plot_queens(solution)
else:
    print("No solution found.")

三、代码分析

1.整体结构

代码主要由三个函数组成：eight_queens函数用于解决八皇后问题，找到所有可能的解；is_safe 函数用于判断在给定位置放置皇后是否安全； plot_queens 函数用于将找到的解可视化展示在棋盘上。

2.eight_queens 函数

首先创建了一个 8×8 的二维列表 board 来表示棋盘，初始化为全 0 ，并创建一个空列表 solutions 用于存储所有找到的解。
然后通过 backtrack 函数进行回溯搜索，从棋盘的第一行开始，逐行尝试放置皇后。当一行放置完毕后，如果已经放置了8个皇后（即 row == 8 ），则将当前棋盘上皇后的位置信息提取出来并添加到 solutions 列表中。
在 backtrack 函数内部，对于每一行，遍历所有列（ for col in range(8) ），通过调用 is_safe 函数判断在当前位置放置皇后是否安全，如果安全则放置皇后（ board[row][col] = 1 ），然后继续递归调用 backtrack 函数处理下一行（ backtrack(row + 1) ）。如果下一行放置皇后失败，则回溯，将当前位置的皇后移除（ board[row][col] = 0 ），继续尝试其他列。

3.is_safe 函数

该函数用于判断在给定的 (row, col) 位置放置皇后是否安全。
首先检查列方向，通过遍历已经放置皇后的行（ for i in range(row) ），如果在同一列已经有皇后（ board[i][col] 为 1 ），则返回 False 。
然后检查左上方对角线方向，从当前位置 (row – 1, col – 1) 开始，沿着对角线向上向左移动（ while i >= 0 and j >= 0 ），如果在对角线上已经有皇后（ board[i][j] 为 1 ），则返回 False ，每次移动 i = i – 1 和 j = j – 1 。
最后检查右上方对角线方向，从当前位置 (row 1, col + 1) 开始，沿着对角线向上向右移动（ while i >= 0 and j < 8 ），如果在对角线上已经有皇后（ board[i][j] 为 1 ），则返回 False ，每次移动 i = i – 1 和 j = j + 1 。
如果所有检查都通过，则返回 True 。

4.plot_queens 函数

该函数接受一个皇后位置的解 solution ，用于绘制棋盘和皇后的位置。
首先创建一个 matplotlib 的 Figure 和 Axes 对象，通过 ax.set_xticks 和 ax.set_yticks 设置坐标轴刻度为 0.5 到 8.5 ，间隔为 1 ，并通过 ax.set_xticklabels 和 ax.set_yticklabels 设置坐标轴标签为空，然后通过 ax.grid 绘制黑色的网格。
接着遍历棋盘的每一个位置（ for i in range(8) 和 for j in range(8) ），如果当前位置在解中（ (i, j) in solution ），则在该位置绘制一个半径为 0.3 的红色圆形（ ax.add_patch(plt.Circle((j + 0.5, i + 0.5), 0.3, color=‘r’)) ）。
最后通过 plt.show 展示绘制好的图形。

四、算法分析

1.时间复杂度分析

八皇后问题的时间复杂度主要由 eight_queens 函数中的 backtrack 函数决定。
在最坏情况下，对于每一行，都需要尝试8个列的位置，总共有8行，所以时间复杂度为 O(8^8) 。
然而，由于 is_safe 函数在每次放置皇后时会进行一些检查，当发现不满足条件时会提前回溯，避免了一些不必要的尝试，所以实际的时间复杂度会低于 O(8^8) 。

2.测试总结

从代码功能上看，该代码能够正确地解决八皇后问题并将结果可视化展示。
当找到解时，可以在图形界面中看到棋盘上皇后的正确位置。
当没有找到解时（虽然八皇后问题是有解的，但如果代码出现错误可能导致找不到解），会打印出 No solution found. 提示信息。
总体而言，代码结构清晰，算法逻辑正确，但八皇后问题的算法时间复杂度较高，在处理更大规模的类似问题时可能会面临效率问题。可以考虑进一步优化算法，如利用对称性等方法来减少搜索空间，提高算法效率。

总结

以上概括了八皇后问题算法的核心概念、时间复杂度和空间复杂度，以及算法的一般思路和特殊情况下的分析。

作者：爱吃饭团的饭桶