徐少飞，张立臣，李鹏

（陕西师范大学计算机科学学院，西安 710119）

0 引言

八皇后问题是指在一个8×8的国际象棋棋盘上随机摆放八个皇后［1］，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，要求求出所有的可行解。一个八皇后问题的可行解如图1所示。

图1 八皇后问题的一个可行解

n皇后问题是八皇后问题的推广，是指在一个n×n的棋盘上放置n个皇后，使任意两个皇后不能相互攻击。我们知道，传统的回溯算法可以求解n皇后问题，但其时间复杂度是指数型的，算法效率较低。目前不少学者对传统回溯算法进行改进，文献［2］利用了n皇后问题解的对称性质对回溯法进行了改进，但优化效果并不明显；文献［3］和文献［4］利用基于位运算的回溯算法进行求解，在整个解空间中搜索，仍没有降低算法的时间复杂性。为了研究更高效、简洁求解n皇后问题一组可行解的算法，本文将传统的回溯算法与概率算法相结合，将棋盘分割为两部分，前半部分使用概率算法求解，后半部分采用回溯算法求解，并合理设置影响算法性能的分割系数和回溯方式。实验结果表明，相比于传统的回溯算法，该算法能够有效地缩短求解时间，因而可以极大拓展在规定时间内可求解问题的规模。

1 n皇后问题求解模型的建立

约定第i个皇后放在棋盘的第i行，设其所在的列为xi(i=1,2,3,…,n)，这样问题的解就是n个皇后所在列的序号组成的一个n元一维向量(x1,x2,x3,…,xn)，解空间是从1到n的全排列。……