用排列树解决n后问题的Python代码

在Python中，我们可以使用排列树（Permutation Tree）来解决n皇后问题，这是一个经典的回溯算法问题，目标是在一个n×n的棋盘上放置n个皇后，使得任意两个皇后都不在同一行、同一列或对角线上。这里我们将使用递归的方式来构建排列树。

首先，我们需要定义一个节点类，用于存储当前放置皇后的位置以及子节点：

class Node:
    def __init__(self, row=-1):
        self.row = row
        self.children = []

    def add_child(self, child):
        self.children.append(child)

然后，我们编写一个函数来生成所有可能的解决方案：

def generate_queens(n):
    if n == 0:  # 基线条件：当n=0时，表示没有皇后，返回空列表
        return [[]]
    
    result = []  # 存储所有解
    for i in range(n):  # 遍历每一行
        next_level = []  # 当前行的子节点
        for prev_solution in result:  # 对于每一种之前放置好皇后的方案
            # 创建一个新的节点，放置新的皇后在当前行
            new_node = Node(i)
            # 将新节点添加到父节点的孩子中
            prev_solution.append(new_node)
            # 尝试在这行之后的所有位置放置皇后
            for j in range(i+1, n):
                # 如果当前位置满足不在同一行、列和对角线上的条件，就尝试放置
                if is_valid(prev_solution[-1], j):
                    # 递归添加这个位置的子节点
                    new_node.add_child(generate_queens(n - (j - i)))
            # 回溯：移除最后一个节点，继续寻找其他位置
            new_node.children.pop()
        result.extend(next_level)  # 将这一层的子节点添加到结果中

    return result

def is_valid(parent, candidate):
    # 检查是否在同一行、列或对角线上
    same_row = parent.row == candidate.row
    same_col = parent.row + parent.column == candidate.row + candidate.column
    diag1 = abs(parent.row - candidate.row) == abs(parent.column - candidate.column)
    diag2 = abs(parent.row + parent.column) == abs(candidate.row + candidate.column)
    return not same_row and not same_col and not diag1 and not diag2

# 测试
n = 8
solutions = generate_queens(n)
for solution in solutions:
    print(solution)

在这个代码中，`generate_queens`函数会生成所有的皇后布局，`is_valid`函数用来检查每个位置是否符合规则。执行这段代码后，你会得到所有合法的n皇后布局。