### N皇后问题的Python实现 N皇后问题是经典的回溯算法应用之一，目标是在 \(n \times n\) 的棋盘上放置 \(n\) 个皇后，使得它们互不攻击。以下是基于递归和回溯方法的一种 Python 实现方案。 #### 方法概述 通过逐行尝试放置皇后的方式解决问题。每次放置皇后时，需验证当前位置是否满足条件（即不在同一列、主对角线或副对角线上存在其他皇后）。如果找到合法解，则继续处理下一行；否则返回至上一层重新选择位置。 --- #### 完整代码示例 以下提供了一种简洁高效的实现： ```python class Solution: def solveNQueens(self, n: int): result = [] # 存储最终的结果集 board = [["."] * n for _ in range(n)] # 初始化棋盘 cols = set() # 记录已占用的列 diag1 = set() # 主对角线 (row - col) diag2 = set() # 副对角线 (row + col) def backtrack(row): if row == n: # 如果已经到达最后一行，则保存当前解 current_board = ["".join(r) for r in board] result.append(current_board[:]) return for col in range(n): # 尝试在当前行的每一列放置皇后 if col in cols or (row - col) in diag1 or (row + col) in diag2: continue # 若该位置冲突则跳过 # 更新状态 board[row][col] = "Q" cols.add(col) diag1.add(row - col) diag2.add(row + col) # 继续递归处理下一行 backtrack(row + 1) # 恢复状态（回溯） board[row][col] = "." cols.remove(col) diag1.remove(row - col) diag2.remove(row + col) backtrack(0) # 开始从第0行进行搜索 return result if __name__ == "__main__": solver = Solution() solutions = solver.solveNQueens(int(input("请输入皇后的数量："))) print(f"共有 {len(solutions)} 种解法") for idx, sol in enumerate(solutions): print(f"解法{idx+1}:") for line in sol: print(line) print("-" * 20) ``` 此代码定义了一个 `Solution` 类来封装求解逻辑，并利用集合记录已被占据的列以及两条对角线的状态以加速判断过程[^4]。 --- #### 关键点解析 1. **数据结构的选择** 使用三个集合分别存储被占用的列 (`cols`) 和两种类型的对角线 (`diag1`, `diag2`) 来快速检测冲突情况。 2. **回溯机制** 在函数内部维护一个栈式的调用链表，当发现某次决策无法达成有效路径时立即撤销此次操作并退回到之前的状态再作他选。 3. **终止条件** 当成功完成所有行的操作后意味着找到了一组符合条件的布局方案，此时将其加入结果列表中即可结束本轮探索。 4. **时间复杂度分析** 虽然理论上最坏情况下可能达到 O(N!) 的级别但由于剪枝的存在实际运行效率远低于理论上限[^1]. ---