如何在8皇后问题回溯实现中返回首个perm至函数外部？

原代码用sys.exit()直接终止程序，导致全局变量无法正常传递结果，以下是几种可行的改进方案：

方案1：让递归函数返回结果 #

修改extend函数为有返回值的函数，找到解时立即返回该排列的副本（避免后续pop操作修改结果），递归过程中一旦收到非空的返回值就向上传递，终止后续循环。

修改后的代码：

from typing import List, Optional

def can_be_extended_to_solution(perm: List[int]) -> bool:
    """检查皇后是否会互相攻击（对角线）"""
    i = len(perm) - 1
    for j in range(i):
        if i - j == abs(perm[i] - perm[j]):
            return False
    return True

def extend(perm: List[int], n: int) -> Optional[List[int]]:
    if len(perm) == n:
        return perm.copy()  # 返回副本，避免后续修改

    for k in range(n):
        if k not in perm:
            perm.append(k)
            if can_be_extended_to_solution(perm):
                result = extend(perm, n)
                if result is not None:
                    return result  # 找到解就直接返回，终止递归
            perm.pop()
    return None  # 没找到解返回None

# 调用示例
if __name__ == "__main__":
    solution = extend([], 8)
    print(solution)

方案2：自定义异常传递结果 #

通过抛出自定义异常来终止递归流程，同时携带找到的解，外部捕获异常即可获取结果，替代sys.exit()的粗暴终止方式。

修改后的代码：

from typing import List

class SolutionFound(Exception):
    def __init__(self, solution):
        self.solution = solution
        super().__init__()

def can_be_extended_to_solution(perm: List[int]) -> bool:
    """检查皇后是否会互相攻击（对角线）"""
    i = len(perm) - 1
    for j in range(i):
        if i - j == abs(perm[i] - perm[j]):
            return False
    return True

def extend(perm: List[int], n: int):
    if len(perm) == n:
        raise SolutionFound(perm.copy())  # 抛出异常携带解

    for k in range(n):
        if k not in perm:
            perm.append(k)
            if can_be_extended_to_solution(perm):
                extend(perm, n)
            perm.pop()

# 调用示例
if __name__ == "__main__":
    try:
        extend([], 8)
    except SolutionFound as e:
        print(e.solution)

方案3：使用可变容器存储结果 #

传递一个空的可变对象（比如列表）作为参数，找到解时将结果存入该容器，然后终止后续递归循环，外部直接读取容器内的值即可。

修改后的代码：

from typing import List

def can_be_extended_to_solution(perm: List[int]) -> bool:
    """检查皇后是否会互相攻击（对角线）"""
    i = len(perm) - 1
    for j in range(i):
        if i - j == abs(perm[i] - perm[j]):
            return False
    return True

def extend(perm: List[int], n: int, result: List[List[int]]):
    if len(perm) == n:
        result.append(perm.copy())
        return  # 找到解后直接返回，终止递归

    for k in range(n):
        if k not in perm and not result:  # 没找到解才继续循环
            perm.append(k)
            if can_be_extended_to_solution(perm):
                extend(perm, n, result)
            perm.pop()

# 调用示例
if __name__ == "__main__":
    result = []
    extend([], 8, result)
    print(result[0] if result else "无解")

以上三种方法都避免了sys.exit()的问题，能够正常将第一个符合要求的皇后排列返回至函数外部。

内容的提问来源于stack exchange，提问作者Devang