八皇后问题的混合算法实现与分析
摘要：
八皇后问题常被作为计算机科学算法课程中讲解回溯法的典型范例，随着算法的分析
与设计的进一步研究，当考虑到时空复杂度时，人们对这一问题作了进一步发展，提出了
采用随机算法来解决这一问题。由于八皇后问题是这样一类问题：其约束规则明确，在约
束规则下必定有解。当然，当采用随机算法时，这个解不是一次性就一定能够得到，但必
定不会引入错误解，因此，采用随机算法中的 Las Vegas 算法来解决此问题成为一种可行途
径。本文主要介绍了在采用 Las Vegas 算法过程解决八皇后问题中通过融入与确定性算法中
的回溯算法的比较，从而直观性地显示如何权衡选择随机算法与回溯算法来解决此类问题。
问题背景
对八皇后问题的研究与讨论已有近两个世纪了。八皇后问题是由棋手 Max Bazzel 在
1848 年提出来的，此后，从 1850 年起就引起了许多数学家的兴趣，包括高斯、波利亚等，
并也成为了计算机科学中回溯算法、置换迭代、分化和约束范式、程序开发方法、整数规
划等学科中的经典实例，并且演化为 N 皇后问题，对解决超大规模集成电路设计、并行存
储器模式、交通控制、死锁预防等问题有重要的意义。
十九世纪著名的数学家高斯在 1850 年将该问题阐述为：在 8×8 格的国际象棋上摆放
八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上
问有多少种摆法。
算法实现
那么，在计算机科学中，对八皇后问题的探讨和实现也有很多看法，并且从许多不同
角度，如 Cengiz Erbas 等在[1]中作了详细而深入地分析，在这里，我参照了[2]及相关资料，
采用随机算法中的 Las Vegas 算法与回溯算法相结合，通过代码实际观察比较 Las Vegas 算法
与回溯算法的性能，从而对选择 Las Vegas 还是回溯算法来解决八皇后问题给出建议。
随机 Las Vegas 思路如下：假如有 k(1
≤ k ≤ 8
)行已经旋转好皇后，如果 k=8，表示八个皇
后已经找到一个合法布局，算法停止，输出成功。如果 k
¿
8，则我们希望将一个皇后放置
到(k+1)行。先计算该行所有可行的位置，即在这些皇后不会与前面已经放置的皇后相互攻
击。如果找不到这样的位置，则返回失败。否则，从该行可行的位置中随机地选择一个位
