一、算法原理

深度优先

二、代码实现

深度优先算法.py

import time

class NQueensDFS:
    def __init__(self, n=8):
        self.n = n          # 棋盘大小（默认为8皇后）
        self.solutions = [] # 存储所有解
        self.cols = set()   # 记录已被占用的列
        self.pie = set()    # 记录主对角线（行+列）
        self.na = set()     # 记录副对角线（行-列）

    def is_conflict(self, row, col):
        """检查当前位置是否与已有皇后冲突（参考的对角线标记方法）"""
        return (col in self.cols) or (row + col in self.pie) or (row - col in self.na)

    def dfs(self, row=0, state=[]):
        """深度优先搜索核心逻辑（递归+回溯）"""

        # 终止条件：所有行已放置皇后
        if row == self.n:
            self.solutions.append(state.copy())  # 保存当前解
            return

        # 遍历当前行的每一列，尝试放置皇后
        for col in range(self.n):
            if not self.is_conflict(row, col):
                # 标记当前列和对角线（参考的集合操作）
                self.cols.add(col)
                self.pie.add(row + col)
                self.na.add(row - col)
                state.append(col)  # 记录当前列的放置位置

                # 递归进入下一行
                self.dfs(row + 1, state)

                # 回溯：撤销当前行的标记（参考的回溯逻辑）
                self.cols.remove(col)
                self.pie.remove(row + col)
                self.na.remove(row - col)
                state.pop()

    def solve(self):
        """执行DFS并统计时间和结果"""
        start_time = time.perf_counter()
        self.dfs()
        end_time = time.perf_counter()
        self.duration = end_time - start_time

    def print_solutions(self, max_display=2):
        """友好展示部分解（默认最多显示2种）"""
        for idx, sol in enumerate(self.solutions[:max_display]):
            print(f"解 {idx+1}: {sol}")
            for col in sol:
                row = ['·'] * self.n
                row[col] = 'Q'
                print(' '.join(row))
            print('---')

# 执行算法并输出统计信息
solver = NQueensDFS(n=8)
solver.solve()

print(f"[统计] 总解数：{len(solver.solutions)}")
print(f"[统计] 耗时：{solver.duration:.6f} 秒\n")

# 显示前两种解的棋盘布局
print("示例解：")
solver.print_solutions(max_display=2)

更新日志

2025/6/26 11:30

查看所有更新日志

• dfb81-update于 2025/6/26
• fd7ad-update于 2025/2/27

版权所有

版权归属：NateHHX

许可证：署名 4.0 国际 (CC-BY-4.0)