N皇后问题的高效解法

"N皇后问题是一个经典的回溯算法问题，旨在在n×n的棋盘上放置n个皇后，使得皇后之间不能相互攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上。本示例代码是针对N皇后问题的优化解决方案，主要优化了对角线的判断，以提高算法效率。代码已经通过了九度OJ1254在线判题系统的测试。" N皇后问题的解决方案通常使用深度优先搜索（DFS）算法，这是一个递归的策略，用于尝试所有可能的皇后放置方案。在这个问题中，我们首先定义一个结构体`Queen`来存储皇后的位置信息，包括行(row)和列(col)。 代码中定义了三个布尔数组：`hasCol`、`Cross`和`viceCross`，分别用于记录当前列、主对角线和副对角线是否已经有皇后。`hasCol[i]`表示第i列是否有皇后，`Cross[i+j]`表示从(i, j)到(n-1, n-1)的主对角线是否有皇后，`viceCross[i-j+20]`表示从(i, j)到(0, n-1-i)的副对角线是否有皇后。这里使用20是为了避免负数索引，因为数组的下标是从0开始的。 `DFS`函数是实现回溯的核心部分，它接受当前搜索的行索引`index`、累计解的数量`sum`以及皇后位置数组`q`作为参数。对于每一行，我们遍历所有列，如果当前列已放置皇后或者与当前行形成主对角线或副对角线冲突，就跳过这一列。如果找到一个可行的位置，我们就更新皇后的位置信息，然后进入下一行的搜索。如果到达最后一行，说明找到了一个解，`sum`自增1。在回溯过程中，我们需要恢复之前的状态，即撤销放置皇后的操作。 在主函数`main`中，我们读取用户输入的n值，初始化相关数组，并调用`DFS`函数进行搜索。每组测试数据处理完后，释放内存并打印解的数量。 这个优化的N皇后问题解决方案利用了位运算和布尔数组来高效地检查和更新对角线的状态，从而减少了无效的搜索，提高了算法性能。这种优化方法在解决大规模问题时尤为重要，因为它显著降低了时间复杂度。