【题目】
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例 1：
image.png
输入： n = 4
输出： 2
解释： 如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入： n = 1
输出： 1
提示：
1 <= n <= 9
【题目解析】
解题方法
解决N皇后II问题的关键在于使用回溯算法。回溯算法是一种通过试错来找到所有解的问题解决方法，如果当前选择不满足约束条件，则进行回溯。
- 维护状态：为了快速检查一个位置是否可以放置皇后，我们使用三个集合来分别记录已经放置皇后的列、对角线和反对角线。
- 深度优先搜索：从棋盘的第一行开始，递归地尝试在每一行的每一列放置皇后。如果当前位置满足约束条件（即不在同一列、对角线或反对角线上有其他皇后），则递归地处理下一行。
- 计数解法：每当到达棋盘的底部（即所有皇后都成功放置）时，增加解的计数。
执行效率
image.png
【总结】
适用问题类型
N皇后II问题属于约束满足问题（CSP），这类问题要求在满足一定条件或约束的前提下，找到问题的所有解。这种问题通常涉及组合优化、逻辑推理，以及搜索策略，广泛存在于计划和调度、逻辑编程、人工智能、算法游戏理论等领域。
解决算法：回溯法结合深度优先搜索（DFS）
算法描述：采用回溯法结合深度优先搜索的策略，系统地探索所有可能的放置组合。通过维护列、对角线和反对角线上皇后的占据情况，对每一行的每一列尝试放置皇后，并在发现当前尝试违反约束时回溯，寻找其他可能的放置方式。
-
算法特点：
- 高效的约束检查：利用集合维护已放置皇后的状态，快速检查当前放置是否满足约束，避免了冗余计算。
- 动态搜索空间剪枝：通过回溯，算法能够在遇到死路时撤销上一步的选择，回到上一个决策点，有效缩小搜索空间。
- 广泛适用性：该方法不仅适用于N皇后问题，还可以扩展到其他需要遍历解空间寻找所有可行解的问题。
时间复杂度与空间复杂度
- 时间复杂度：O(N!)，其中N是皇后的数量。虽然回溯法通过剪枝减少了搜索空间，但在最坏情况下，算法仍需尝试所有的排列方式。
- 空间复杂度：O(N)，主要空间消耗来源于递归调用栈及用于记录皇后位置的辅助数据结构。
实践意义
- 算法教育与研究：N皇后II问题及其解决方案是学习和教授回溯算法、深度优先搜索的极好案例，有助于深化对这些基本算法概念的理解和应用。
- 问题解决能力的提升：掌握这种算法能够增强解决实际约束满足问题的能力，尤其是在对解的数量而非具体解本身感兴趣时。
- 跨领域应用：从理论到实践，回溯法和深度优先搜索在许多领域都有应用，如自动化测试、人工智能（如游戏AI）、组合优化问题等，具有广泛的实践意义和应用价值。
总之，通过深入探索N皇后II问题的解决方案，我们不仅可以提升算法设计与问题解决的能力，还能够扩展这些策略到更广泛的应用场景中，展现计算机科学的实用性和创新性。
