随机化算法在N皇后问题中的应用

陈晓梅 胡春花

摘要：回溯法是用于求解N后问题的常用算法。典型的回溯算法在N后问题的解空间中，用于判断合法子树的剪枝函数的时间效率较低。对于N后问题的任何一个解而言，每个皇后在棋盘上的位置无任何规律，更像是随机放置的。因此在回溯算法中引入随机化方法来解决N后问题，能获得很好的时间效率。

关键词：回溯法；随机化算法；时间效率

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）22-5325-03

在 n行n列的棋盘上需要放置n 个皇后，规定任何 2 个皇后不能放在同一行或同一列或同一斜线上。N皇后问题就是求满足条件的可行布局数量，或求出其中一个可行布局。该文讨论求N皇后问题的一个可行布局。

回溯法是求解N皇后问题的典型算法。以当前普通配置的计算机的运行速度而言，在n值小于28时，典型的回溯法能够在两秒钟之内获得其中一个可行布局。在n值大于100时，由于运行时间过长，无法获得结果。引入随机化算法，将之与典型回溯法结合，可以有效地提高算法的时间效率。

1 求解N皇后问题的典型回溯算法

用典型回溯法解这个问题的思路是，以完全n叉树来表示该问题的解空间，树中根节点设为第0层，第i层的节点表示棋盘在第i行的待选列。算法从n叉树的根节点开始，采用深度优先的方式进行搜索。对于当前的搜索到的某个节点，算法判断该节点是否同时满足约束条件①和②，若满足，继续按深度优先的方式进行搜索；否则，跳过对以该节点为根的子树的搜索，回溯至当前节点的父节点，继续按深度优先方式进行搜索。当搜索至叶子节点，判断该节点满足约束条件，若满足，则获得了关于该问题的一个合理布局。

在算法中，使用Place函数作为剪枝函数，对当前节点使用Place函数进行合法判断，跳过不满足约束条件的子树，以提高时间效率。Place函数使用前面的条件①和②作为判断条件。

典型回溯法求N后问题的一个可行布局的算法如下：

2 使用随机化算法与回溯法结合求解N皇后问题

其基本思想是，使用随机化算法获得前t行的合理布局，再使用回溯算法获得后面行的合理布局。函数Random（n）用于返回0～n-1之间的随机整数。函数QueensLV（t）用于随机生成棋盘前t 行的一个布局，其返回值为布尔型，表示本次调用获取随机布局成功或失败。Backtrack（t）是一个递归函数，其根据前t-1行的确定布局，获取第t～n行的一个合理布局。其返回值为布尔型，表示本次递归获取第t～n行布局成功或失败。

3 实验结果及分析

使用Dev- C++分别编写了关于求N皇后问题的一个合理布局的典型回溯法程序和随机算法结合回溯法的程序，在CPU为Core2 Duo 2.10 GHz，操作系统为Windows 7的计算上运行，它们的运行时间如表1所示：

从表1和表2可以看出，使用回溯法与随机化算法结合比单纯使用回溯法能更快地获得其中一个可行布局，其程序运行时间明显优于典型回溯法，当n为30 时，后者需要接近3分钟的时间才能获得一个可行布局，而前者使用4毫秒即可。当n值增加到200时，后者可以1秒内获得答案，这是前者所望尘莫及的。分析其原因，是因为对于N后问题的任何一个解而言，每个皇后在棋盘上的位置无任何规律，更像是随机放置的。因此在回溯算法中引入随机方法来求解N后问题的一个可行解，能获得很好的时间效率。

参考文献：

[1] 王晓东.计算机算法设计与分析[M]. 4版.北京：电子工业出版社，2012.