一、算法原理

一致性代价

二、代码实现

import heapq
import time

class Node:
    def __init__(self, state, cost):
        self.state = state    # 当前皇后位置序列（如 [0, 4, 7]）
        self.cost = cost      # 路径代价（已放置的皇后数）

    def __lt__(self, other):
        return self.cost < other.cost  # 按代价排序

def is_conflict(state, next_col):
    """
    检查新皇后位置是否与已有皇后冲突。
    :param state: 当前已放置的皇后列位置序列
    :param next_col: 新皇后所在的列
    :return: 是否冲突
    """
    next_row = len(state)
    for row in range(next_row):
        col = state[row]
        # 检查是否同列或同对角线
        if col == next_col or abs(col - next_col) == next_row - row:
            return True
    return False

def ucs_queens(n=8):
    """
    一致性代价搜索解决八皇后问题。
    :param n: 棋盘大小（默认8皇后）
    :return: 解的数量、总循环次数、耗时
    """
    start_time = time.perf_counter()
    solutions = []
    visited = set()  # 记录已访问的状态（哈希优化）
    heap = []
    heapq.heappush(heap, Node(state=[], cost=0))  # 初始状态为空棋盘

    while heap:
        current_node = heapq.heappop(heap)
        current_state = current_node.state
        current_cost = current_node.cost

        # 终止条件：已放置n个皇后且无冲突
        if len(current_state) == n:
            solutions.append(current_state)
            continue  # 继续搜索其他解

        # 尝试在下一行的每一列放置皇后
        next_row = len(current_state)
        for col in range(n):
            if not is_conflict(current_state, col):
                new_state = tuple(current_state + [col])  # 转换为元组以便哈希存储
                if new_state not in visited:
                    visited.add(new_state)
                    heapq.heappush(heap, Node(state=list(new_state), cost=current_cost + 1))

    end_time = time.perf_counter()
    return len(solutions), end_time - start_time

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

版权所有

版权归属：NateHHX

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