九度OJ优化八皇后问题解法

九度OJ八皇后问题是一个经典的计算机科学挑战，涉及了回溯算法（Backtracking）和逻辑推理，主要目标是在一个8×8的棋盘上放置八个皇后，使得任意两个皇后都不在同一行、同一列或对角线上。这个问题的优化重点在于减少对主对角线和副对角线判断的计算量，以提高算法效率。 首先，我们需要理解几个关键概念： 1. **数组hasCol**：用于记录某一列是否已经有皇后，帮助我们在搜索过程中避免重复放置。 2. **数组Cross** 和 **viceCross**：这两个数组用于检查当前位置与主对角线和副对角线的关系。Cross数组关注主对角线，从当前位置到右上角；viceCross数组关注副对角线，从当前位置到左下角。通过这两个数组，我们可以快速判断当前放置是否符合规则，减少不必要的递归。 **核心算法：深度优先搜索（DFS）** 函数Dfs是解决八皇后问题的核心部分，它采用递归的方式尝试在每一列中找到合适的放置位置。参数`num`表示当前正在处理的皇后位置，`cur`则记录已放置的皇后数量。当`num`达到8时，表示所有皇后都已放置，将当前布局打印出来并结束递归。 函数内部的循环遍历所有未被占用的列。如果`hasCol[i]`为真（即该列已有皇后），或者`Cross[i+num]`或`viceCross[i-num+20]`为真（即当前位置与主/副对角线冲突），则跳过此次尝试。若满足条件，就将皇后放在该列，更新相关数组状态，然后递归地继续在下一列寻找。当递归返回时，恢复该列的状态，以便尝试其他可能的布局。 **主函数**：主函数接收用户输入，包括棋盘大小`n`和每个测试用例中需要放置的皇后数量`count`。通过初始化数组，调用Dfs函数处理每个测试用例，直到处理完所有输入。 此代码实现了一种有效的解决方案，通过巧妙地利用数据结构和逻辑优化，能够在保证正确性的同时减少不必要的计算，提高了算法的运行效率。在九度OJ平台的1140题中，该代码已经成功通过测试，表明其在实际问题中的应用是可行且高效的。