一、算法原理

宽度优先

二、代码实现

from collections import deque
import time  # 引入时间模块

def is_valid(state, col):
    current_row = len(state)
    for row in range(current_row):
        if state[row] == col or abs(state[row] - col) == current_row - row:
            return False
    return True

def bfs_queens():
    start_time = time.perf_counter()  # 记录算法开始时间
    count = 0
    queue = deque([[]])

    while queue:
        current_state = queue.popleft()
        current_row = len(current_state)

        if current_row == 8:
            count += 1
            continue

        # 尝试在下一行的每个列位置放置皇后
        for col in range(8):
            if is_valid(current_state, col):
                new_state = current_state + [col]
                queue.append(new_state)

    end_time = time.perf_counter()  # 记录算法结束时间
    duration = end_time - start_time
    return count, duration

# 执行并输出结果
solution_count, time_used = bfs_queens()
print(f"[统计] 解数量：{solution_count}")
print(f"[统计] 耗时：{time_used:.6f} 秒")

版权所有

版权归属：NateHHX

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