八皇后问题：算法详解及代码实现

八皇后问题是一个经典的计算机科学问题，要求在一个 8×8 格的棋盘上放置 8 个皇后，使得她们不能相吃。按照国际象棋的规则，一个皇后可以吃掉与她处于同一行、同一列、同一对角线上的任何棋子，因此每一行只能摆放一个皇后。八皇后等价于要求在一个 8×8 格的棋盘上放置 8 个皇后，使得任何 2 个皇后不能放在同一行或同一列或同一对角线上。

(8,5,3,1,2,1)=769 图 1 解空间树中一条随机路径所对应的棋盘状态

输入数据 8

输出数据

(2) 算法分析 对于n后问题，皇后的位置用一个一维数组 x[1…n] 来存放，其中 x[i] 表示第 i 行皇后放在第 x[i] 列。使用回溯算法，从第一行开始依次尝试在每一列放置皇后，如果满足条件则进入下一行继续放置，否则回溯到上一行重新尝试。在每一行放置皇后时，需要判断当前列、当前左斜对角线、当前右斜对角线是否已经有皇后，如果有则不能放置。

时间复杂度： O(n!)，其中 n 为皇后数量。因为每个皇后可以放置在 n 列中的任意一列，所以总共需要尝试 n^n 种情况。但是由于每次放置皇后后会剔除一些不符合条件的情况，所以实际时间复杂度要小于 n^n。

空间复杂度： O(n)，需要使用一个长度为 n 的一维数组来存放皇后位置。