### 回溯法解决8皇后问题 **八皇后问题**是一个经典的棋盘问题，目标是在8×8的国际象棋棋盘上放置八个皇后，使得它们互相之间不能攻击到对方。每个皇后的攻击范围包括同行、同列以及对角线方向的所有格子。 以下是用Python通过回溯算法求解该问题的具体步骤： --- #### **核心思想** 1. 使用一个数组`queens[]`表示每一行皇后所在的列位置。 - `queens[i] = j` 表示第 i 行的皇后放在了第 j 列。 2. 每次尝试将皇后放到某一行的新列位置，并检查是否冲突： - 同一列：如果已有其他行在同一列放有皇后，则冲突； - 对角线：若两皇后之间的行列差绝对值相等，则说明在对角线上。 3. 如果当前摆放合法，则递归处理下一行；否则回退至上一步重新选择。 --- #### **代码实现** ```python def is_valid(queens, row, col): """判断当前位置 (row, col) 是否可以放置皇后""" for r in range(row): # 只需检查之前的行是否有冲突 if queens[r] == col or abs(r - row) == abs(queens[r] - col): return False return True def solve_n_queens(n=8): def backtrack(row): nonlocal count, solutions if row == n: # 找到了一种解决方案 count += 1 solutions.append([queen_pos[:] for queen_pos in queens]) else: for col in range(n): # 尝试本行的所有列 if is_valid(queens, row, col): queens[row] = col # 放置皇后 backtrack(row + 1) # 进入下一行继续搜索 queens[row] = -1 # 移除皇后（回溯） queens = [-1] * n # 初始化皇后的位置 count = 0 # 解的数量统计 solutions = [] # 记录所有可行方案 backtrack(0) return count, solutions # 主程序运行并展示结果 count, all_solutions = solve_n_queens() print(f"总共有 {count} 种解法") if count > 0: print("前三个解：") for sol in all_solutions[:3]: for row in sol: line = ['Q' if col == 'Q' else '.' for col in range(8)] line[sol.index('Q')] = 'Q' print(line) ``` --- #### **运行解释** 1. 程序会计算出所有的可能摆放示意图及其总数； 2. 输出其中前三组及最后三组的详细布局情况。 > 注意：由于生成的是索引列表形式的结果，在打印时需要稍作转换来更直观地显示“.”代表空位，“Q”代表皇后所在之处。 --- #### 结果样例 假设最终得出92种解法（标准结果），则部分输出类似如下内容（仅举例示意）： ``` 总共有 92 种解法 前三个解： ['.', '.', '.', 'Q', '.', '.', '.', '.'] ['.', '.', '.', '.', '.', '.', 'Q', '.'] ['Q', '.', '.', '.', '.', '.', '.', '.'] ['.', '.', 'Q', '.', '.', '.', '.', '.'] ... 后三个解： [...] ``` --- ###