1、（1）请编程实现从 n-皇后问题的所有 92 种可行解中筛选出 12 种独立解，而其余的解都 可以由这些独立解利用对称性或旋转而得到。 （2）若 n-皇后问题要求在求得第一个可行解之后算法即终止，请编程实现。 提示：可以用 flag 标志是否已经求得第一个可行解。根据 flag 的值决定是否继续进行本层 调用，还是直接返回上层调用点。

1、实现从 n-皇后问题的所有 92 种可行解中筛选出 12 种独立解可以通过以下步骤实现：

（1）生成所有可能的解，并存储在一个列表中。

（2）对于每个解，使用对称性和旋转来检查它是否等价于列表中的其他解。如果是，则从列表中删除该解。

（3）最终剩下的解就是独立解。

以下是 Python 代码实现：

def generate_all_solutions(n):
    solutions = []  # 存储所有可能的解
    cols = set()
    diag1 = set()
    diag2 = set()

    def backtrack(row, cur_state):
        if row == n:
            solutions.append(cur_state[:])
            return
        for col in range(n):
            if col in cols or row + col in diag1 or row - col in diag2:
                continue
            cols.add(col)
            diag1.add(row + col)
            diag2.add(row - col)
            cur_state.append(col)
            backtrack(row + 1, cur_state)
            cur_state.pop()
            cols.remove(col)
            diag1.remove(row + col)
            diag2.remove(row - col)

    backtrack(0, [])
    return solutions


def filter_independent_solutions(solutions):
    # 筛选独立解
    independent_solutions = []
    for i, sol in enumerate(solutions):
        is_independent = True
        for j in range(i + 1, len(solutions)):
            if is_equivalent(sol, solutions[j]):
                is_independent = False
                break
        if is_independent:
            independent_solutions.append(sol)
    return independent_solutions


def is_equivalent(sol1, sol2):
    # 检查两个解是否等价
    n = len(sol1)
    for _ in range(4):
        if rotate(sol1, n) == sol2:
            return True
        sol1 = reflect(sol1, n)
        if rotate(sol1, n) == sol2:
            return True
    return False


def rotate(sol, n):
    # 将解顺时针旋转 90 度
    return [n - 1 - c for c in sol]


def reflect(sol, n):
    # 将解水平翻转
    return [n - 1 - c for c in sol[::-1]]


n = 8
all_solutions = generate_all_solutions(n)
independent_solutions = filter_independent_solutions(all_solutions)
print(f"共有 {len(all_solutions)} 种可行解，其中 {len(independent_solutions)} 种独立解：")
for i, sol in enumerate(independent_solutions):
    print(f"{i+1}. {sol}")

2、要求在求得第一个可行解之后算法即终止，可以通过设置一个 flag 标志来实现。当找到第一个可行解后，将 flag 置为 True，然后在下一次调用 backtrack 时，如果 flag 已经为 True，就直接返回上层调用点，而不再继续搜索。以下是 Python 代码实现：

def find_first_solution(n):
    cols = set()
    diag1 = set()
    diag2 = set()
    flag = [False]  # 标志是否已经找到第一个可行解

    def backtrack(row, cur_state):
        if row == n:
            flag[0] = True
            print("找到一个可行解：", cur_state)
            return
        if flag[0]:
            return
        for col in range(n):
            if col in cols or row + col in diag1 or row - col in diag2:
                continue
            cols.add(col)
            diag1.add(row + col)
            diag2.add(row - col)
            cur_state.append(col)
            backtrack(row + 1, cur_state)
            cur_state.pop()
            cols.remove(col)
            diag1.remove(row + col)
            diag2.remove(row - col)

    backtrack(0, [])


n = 8
find_first_solution(n)