回溯法、分支限界法解决N皇后问题

本期是针对解决 N 皇后问题的回溯法和分支限界法两块代码，分析了其解的形式（二维列表，元素取值 0 或 1 表示有无皇后）、解的空间结构（排列树，各层对应放置皇后决策，根节点初始态，树高为 N，路径对应解）及搜索条件（放置皇后合法性、回溯控制或分支选择条件、解完成判断条件等方面各自特点）。 

一、解的形式及各分量取值

解的形式

两种方法得到的 N 皇后问题的解的形式均为一个二维列表（矩阵），用于表示棋盘的状态。该二维列表的每一行对应棋盘的一行，每一列对应棋盘的一列。

各分量取值

在这个二维列表中，每个元素的取值只有两种情况：

• 0：表示对应位置的棋盘方格上没有放置皇后，即该位置为空。
• 1：表示在对应位置的棋盘方格上放置了皇后。

二、解的空间结构（排列树）

排列树的构成

• 对于 N 皇后问题，解空间的排列树结构中：
  • 树的每一层对应着在棋盘上放置一个皇后的决策过程。
  • 根节点表示还未开始放置任何皇后的初始状态。此时，对于回溯法代码中的 backtrack 函数，传入的 perm 为空列表；对于分支限界法代码，初始压入优先队列的状态中皇后放置排列 perm 也是空列表。
  • 树的高度为 N，因为总共需要放置 N 个皇后，每放置一个皇后就向下一层延伸，所以到放置完 N 个皇后时到达叶节点，即完成了一个完整的解的探索。
  • 在每一层，节点的分支数取决于当前行可选择放置皇后的列位置数量以及之前放置皇后所限制的条件。例如，在第一层（放置第一个皇后），理论上有 N 种可能的列位置可供选择，所以根节点有 N 个分支；但随着皇后逐渐被放置，后续层可选择的列位置会因要满足皇后之间不能相互攻击的规则而减少，分支数也会相应减少。

节点与解的对应关系

• 从根节点到叶节点的一条完整路径对应着一个完整的解。在这条路径上，每个节点所做的选择（即选择在哪一列放置皇后）组合起来就确定了整个棋盘上皇后的放置方案，也就是一个满足条件的解。具体来说：
  • 在回溯法中，backtrack 函数通过不断递归，每次选择一个合适的列添加到 perm 列表中，当 perm 列表的长度达到 N 时，就根据这个 perm 构建出完整的棋盘状态作为一个解。
  • 在分支限界法中，优先队列中的每个状态包含了当前的皇后放置排列 perm，当从优先队列中取出的状态其 perm 长度达到 N 时，同样根据这个 perm 构建出完整的棋盘状态作为一个解。

三、搜索条件

回溯法的搜索条件

放置皇后的合法性条件

• 通过 is_safe 函数来判断在某个位置放置皇后是否合法。具体检查以下几个方面：
  • 列冲突检查：在 is_safe 函数中，对于回溯法的版本，会遍历整个棋盘的行（for i in range(n)），检查在同一列是否已经放置了皇后。若已经有皇后在同一列，那么在当前位置放置皇后就是不合法的，函数返回 False。
  • 对角线冲突检查：
    • 左上对角线冲突检查：从当前位置沿着左上对角线方向（行减 1，列减 1）进行遍历（while i >= 0 and j >= 0），检查是否有皇后已经放置在这条对角线上。若有，返回 False。
    • 右上对角线冲突检查：从当前位置沿着右上对角线方向（行减 1，列加 1）进行遍历（while i >= 0 and j < n），检查是否有皇后已经有皇后放置在这条对角线上。若有，返回 False。
  • 只有当这三个方面（列冲突、左上对角线冲突、右上对角线冲突）都没有冲突时，在当前位置放置皇后才被认为是合法的，is_safe 函数才会返回 True。

回溯搜索的控制条件

• 在 solve_n_queens 函数中的 backtrack 函数里：
  • 当 len(perm) 等于 N 时，说明已经成功在棋盘上放置了 N 个皇后，此时找到了一个完整的解，会将根据当前 perm 构建出的棋盘状态添加到 solutions 列表中，然后返回，不再继续向下一层递归。
  • 在每一层递归调用 backtrack 时，会遍历所有可能的列位置（for col in range(n)），但只有当该列位置 col 不在当前的排列 perm 中（即还没有在这一列放置过皇后）并且在该位置放置皇后是安全的（is_safe(perm, len(perm), col)）时，才会继续向下一层递归调用 backtrack，继续放置下一个皇后。否则，会跳过该列位置，尝试其他可能的列位置。

分支限界法的搜索条件

放置皇后的合法性条件

• 同样是通过 is_safe 函数来判断在某个位置放置皇后是否合法，其检查内容与回溯法中的 is_safe 函数基本一致，包括：
  • 列冲突检查：在 is_safe 函数中，对于分支限界法的版本，会遍历当前行之前的所有行（for i in range(row)），检查在同一列是否已经放置了皇后。若已经有皇后在同一列，那么在当前位置放置皇后就是不合法的，函数返回 False。
  • 对角线冲突检查：
    • 左上对角线冲突检查：从当前位置沿着左上对角线方向（行减 1，将 i 减 1，列减 1）进行遍历（while i >= 0 and j >= 0），检查是否有皇后已经放置在这条对角线上。若有，返回 False。
    • 右上对角线冲突检查：从当前位置沿着右上对角线方向（行减 1，列加 1）进行遍历（while i >= 0 and j < n），检查是否有皇后已经放置在这条对角线上。若有，此句应改为若有皇后，返回 False。同样也是只有当这三个方面（列冲突、左上对角线冲突、右上对角线冲突）都没有冲突时，在当前位置放置皇后才被认为是合法的，is_safe 函数才会返回 True。

分支选择条件（基于启发式值）

• 在分支限界法中，通过 calculate_heuristic 函数来计算每个可能分支的启发式值。该函数根据当前的皇后放置排列 perm，先构建出一个完整的棋盘状态，然后计算出后续放置皇后可能产生的冲突数量作为启发式值。
• 启发式值越小，说明在当前排列基础上继续放置皇后产生冲突的可能性越小，也就越有可能找到一个可行解。
• 在搜索过程中，通过优先队列（heapq）来管理各个分支状态。每次从优先队列中取出具有最小启发式值的状态进行进一步探索。这意味着优先选择那些看起来更有希望找到可行解的分支进行处理，而不是盲目地遍历所有可能的分支。

解的完成判断条件

• 在 solve_n_queens_branch_and_bound 函数中，当取出的排列长度等于 N 时，说明已经成功在棋盘上放置了 N 个皇后，此时找到了一个完整的解，便可以根据该排列构建出完整的棋盘状态并返回。

综上所述，两种方法虽然在搜索策略上有所不同（回溯法是按深度优先搜索的方式递归探索解空间，分支限界法是基于启发式值通过优先队列选择更有希望的分支进行探索），但都是围绕着如何在满足皇后放置规则的前提下，通过合理的搜索条件在排列树结构的解空间中寻找 N 皇后问题的所有可行解。

代码案例 

# 以下是使用回溯法解决N皇后问题的代码

# 判断在给定棋盘状态下，在指定位置放置皇后是否安全
def is_safe(board, row, col):
    n = len(board)
    # 检查列是否有冲突
    for i in range(n):
        # 如果在当前列的其他行已经有皇后（值为1），则返回False，表示不安全
        if board[i][col] == 1:
            return False
    # 检查左上对角线是否有冲突
    i = row - 1
    j = col - 1
    while i >= 0 and j >= 0:
        # 如果在左上对角线上已经有皇后（值为1），则返回False，表示不安全
        if board[i][j] == 1:
            return False
        i -= 1
        j -= 1
    # 检查右上对角线是否有冲突
    i = row - 1
    j = col + 1
    while i >= 0 and j < n:
        # 如果在右上对角线上已经有皇后（值为1），则返回False，表示不安全
        if board[i][j] == 1:
            return False
        i -= 1
        j += 1
    return True

# 解决N皇后问题的主函数
def solve_n_queens(n):
    # 定义回溯函数，用于递归地尝试放置皇后
    def backtrack(perm):
        # 如果已经放置了n个皇后，说明找到了一个解
        if len(perm) == n:
            # 创建一个初始值全为0的n x n棋盘
            solution = [[0] * n for _ in range(n)]
            # 根据当前皇后的放置位置（perm），在棋盘对应位置设置为1
            for i, col in enumerate(perm):
                solution[i][col] = 1
            # 将找到的解添加到解列表solutions中
            solutions.append(solution)
            return

        # 遍历每一列，尝试放置皇后
        for col in range(n):
            # 如果当前列不在已经放置皇后的列列表（perm）中，并且在该位置放置皇后是安全的
            if col not in perm and is_safe(perm, len(perm), col):
                # 将当前列添加到已放置皇后的列列表中，继续递归放置下一个皇后
                backtrack(perm + [col])

    # 用于存储所有解的列表
    solutions = []
    # 从空的皇后放置列表开始回溯
    backtrack([])
    return solutions

n = 4
# 调用solve_n_queens函数解决4皇后问题，并获取解列表
solutions = solve_n_queens(n)
for solution in solutions:
    for row in solution:
        # 将每行中的0替换为'.'，1替换为'Q'，并以空格连接后打印
        print(' '.join(['Q' if cell == 1 else '.' for cell in row]))
    print()

# 以下是使用分支限界法解决N皇后问题的代码

# 判断在给定棋盘状态下，在指定位置放置皇后是否安全
import heapq


def is_safe(board, row, col):
    n = len(board)
    # 检查列是否有冲突
    for i in range(row):
        # 如果在当前列的前面行已经有皇后（值为1），则返回False，表示不安全
        if board[i][col] == 1:
            return False
    # 检查左上对角线是否有冲突
    i = row - 1
    j = col - 1
    while i >= 0 and j >= 0:
        # 如果在左上对角线上已经有皇后（值为1），则返回False，表示不安全
        if board[i][j] == 1:
            return False
        i -= 1
        j -= 1
    # 检查右上对角线是否有冲突
    i = row - 1
    j = col + 1
    while i >= 0 and j < len(board):
        # 如果在右上对角线上已经有皇后（值为1），则返回False，表示不安全
        if board[i][j] == 1:
            return False
        i -= 1
        j += 1
    return True


# 计算给定皇后放置排列（perm）对应的启发式值（即后续放置皇后可能产生的冲突数量）
def calculate_heuristic(perm, n):
    # 根据当前皇后放置排列创建一个初始值全为0的n x n棋盘
    board = [[0] * n for _ in range(n)]
    for i, col in enumerate(perm):
        board[i][col] = 1

    conflicts = 0
    for i in range(len(perm), n):
        for j in range(n):
            # 如果在后续行的某个位置放置皇后不安全（通过is_safe判断），则增加冲突计数
            if not is_safe(board, i, j):
                conflicts += 1
    return conflicts


# 使用分支限界法解决N皇后问题的主函数
def solve_n_queens_branch_and_bound(n):
    # 创建一个优先队列，用于存储待处理的状态
    priority_queue = []
    # 将初始状态（启发式值为0，空的皇后放置排列，皇后数量n）压入优先队列
    heapq.heappush(priority_queue, (0, [], n))
    while priority_queue:
        # 从优先队列中取出具有最小启发式值的状态
        _, perm, remaining_n = heapq.heappop(priority_queue)
        # 如果已经放置了n个皇后，说明找到了一个解
        if len(perm) == n:
            # 创建一个初始值全为0的n x n棋盘
            solution = [[0] * n for _ in range(n)]
            for i, col in enumerate(perm):
                solution[i][col] = 1
            return solution

        # 遍历每一列，尝试放置皇后
        for col in range(n):
            # 如果当前列不在已经放置皇后的列列表（perm）中，并且在该位置放置皇后是安全的
            if col not在perm and is_safe(perm, len(perm), com):
                # 创建一个新的皇后放置排列，将当前列添加进去
                new_perm = perm + [col]
                # 计算新排列对应的启发式值
                heuristic = calculate_heuristic(new_perm, n)
                # 将新状态（启发式值、新排列、剩余皇后数量减1）压入优先队列
                heapq.heappush(priority_queue, (heuristic, new_perm, remaining_n - 1))
    return None


n = 4
# 调用solve_n_queens_branch_and_bound函数解决4皇后问题，并获取解
solution = solve_n_queens_branch_and_bound(n)
if solution:
    for row in solution:
        # 将每行中的0替换为'.'，1替换为'Q'，并以空格连接后打印
        print(' '.join(['Q' if cell == 1 else '.' for cell in row]))
else:
    print("No solution found.")