局部搜索解决N皇后问题试验报告（内含源代码）

局部搜索算法是解决N皇后问题的一种有效方法，它通过不断迭代和局部调整来寻找解决方案。N皇后问题是在一个N×N的棋盘上放置N个皇后，要求任意两个皇后都不能处于同一行、同一列或同一斜线上。这个问题是经典的回溯算法应用，但通过局部搜索策略，可以避免回溯过程中的大量无效尝试。 实验报告的目标是实现一个使用局部搜索的N皇后问题求解程序，并进行可视化展示。这里选择C++作为编程语言，并以八皇后问题为起点，因为八皇后问题相对直观且易于理解，解决它有助于理解和构建解决N皇后问题的基础。 局部搜索算法的基本思路如下： 1. 随机选择一个初始状态，例如在棋盘上随机放置皇后。 2. 对当前状态进行局部调整，例如随机选择两个皇后并尝试交换它们的位置。 3. 计算新状态与目标状态（无冲突的布局）的接近程度，通常用冲突数量衡量。 4. 如果新状态的冲突数量少于当前状态，就接受新状态并更新当前状态，否则保持原状。 5. 重复步骤2-4，直到找到无冲突的解决方案或者达到预设的停止条件（如达到最大迭代次数或无法进一步减少冲突）。 在提供的代码中，可以看到以下关键部分： - `change` 函数用于交换两个变量的值。 - `conflict` 函数计算当前状态中皇后的冲突数量。 - `main` 函数是整个程序的入口，其中包含了局部搜索的逻辑。 - 使用 `srand` 和 `rand` 函数进行随机数生成，用于随机选择皇后进行交换。 - 通过 `num` 计数器来监控新状态未被接受的次数，当超过一定阈值（2*N*N）时，认为当前路径可能不优，程序返回开始重新尝试。 在实验过程中，可以通过修改 `#define N 12` 来改变问题规模，例如将N设为4，程序将解决四皇后问题。输出的结果是一个一维数组，表示每一行的皇后位置，例如在四皇后问题中，输出 "1 2 3 4" 表示每行的皇后分别位于第1、2、3、4列。 这个实验报告通过局部搜索算法解决了N皇后问题，采用了一种随机化和迭代的方法来逼近最优解，同时简化了状态的表示和冲突的检查。通过这种方式，可以有效地在不同规模的棋盘上找到可行的皇后布局。