第34卷 第4期 2006年12月 江汉大学学报(自然科学版) Journal of Jianghan University (Natural Sciences) Vol. 34 No. 4 Dec., 2006 N皇后问题Las Vegas优化算法的实现 邓宏涛，朱 殉 (江汉大学 数学与计算机科学学院，武汉 430056) 摘 要 : 介绍了n皇后问题常用的回溯解决策略，分析了概率算法中拉斯维加斯 (Las Vegas)算法的 特点及其在 n皇后问题中的应用，并给出了两者结合解决n皇后问题的算法策略和效率分析. 回溯算法;拉斯维加斯算法;n皇后 关键 词 : 中图分类号:TP301.6 文献标识码:A 文章编号:1673-0143(2006)04-0056-03 0 引言 置 n个皇后，任何 2个皇后不放在同一行或同一 列或同一斜线上. 回溯算法有 “通用解题法”之称 ，是一个既 带有系统性又带有跳跃性的搜索算法 ，用它可以 用 n元组x[l: n]表示 n皇后问题的解.其中 x[i]表示皇后 i放在棋盘的第 i行的第 x[i]列.由 系统地搜索问题的所有解.它在问题的解空间树 于不允许将 2个皇后放在同一列 ，所以解向量中 中，按深度优先策略，从根结点出发搜索解空间 的 x[a]互不相同.2个皇后不能放在同一斜线上 树 ，只要搜索到问题的一个解就可结束.它常用 是 问题 的隐约束.该条件可以化成显约束的形 于求解组合数较大的问题.n皇后问题就常常用 式.设 2个皇后放置的位置分别是 (i,力和 ((k, 1), 回溯法解决 ，可以得到所有的解决方案. 拉斯维加斯 (Las Vegas)算法属于概率算法 中的一种.它具有概率算法的特点 ，即允许算法 在执行的过程中随机选择下一个计算步骤.许多 情况下，当算法在执行过程中面临一个选择时， 随机性选择常比最优选择省时.因此概率算法可 只要 }i-kj = U-11成立，就表明2个皇后位于同 一条斜线上.问题的隐约束化成了显约束. 用回溯法解 n皇后问题时，用完全 n叉树表 示解空间.可行性约束 place剪去不满足行、列 和斜线约束的子树. 下面的解 n皇后问题的回溯法中，递归方法 在很大程度上降低算法的复杂度.拉斯维加斯算 法不会得到不正确的解，一旦用该算法找到一个 backtrack (1)实现对整个解空间的回溯搜索. backtrack (i)搜索解空间中第 Z层子树.sum记录当 解 ，那么这个解肯定是正确的.但是有时候用拉 斯维加斯算法可能找不到解.拉斯维加斯算法得 前已找到的可行方案数. 解 n皇后问题的回溯算法描述如下 : 到正确解的概率随着它用的计算时间的增加而提 public class NQueenI 高.对于所求解问题的任一实例，用同一拉斯维 加斯算法反复对该实例求解足够多次，可使求解 失效的概率任意小. 1 常用的回溯算法解决方案 n皇后问题 :在 nxn格 的棋盘上放置彼此不 受攻击的 n个皇后.按照国际象棋的规则 ，皇后 可以攻击与之处在同一行或同一列或同一斜线上 的棋子.n皇后 问题等价于在 nxn格 的棋盘上放 {static int n; //皇后个数 static int【」x;//当前解 static long sum; //当前已找到的可行方案数 public static long nQueen(int nn) { n=nn; sum=0; x=new int [n+l]; for(int i=0; i<=n; i++) x [i] =0; backtrack (1); return sum; 收稿 日期 作者简介 2006一01一12 邓宏涛 (1972一)，男，湖北武汉人，讲师，主要从事软件工程研究. 

2006年第4期 邓宏涛，等:N皇后问题Las Vegas优化算法的实现 } private static boolean place(int k) { for(int j=1; jn)sum++; else for(int i=1; i<--n; i-!-+) { x[t]二i; if(place (t)) backtrack (t+l); } } 2 拉斯维加斯算法解决方案 在用回溯法解 n皇后问题时 ，实际上是在系 统地搜索整个解空间树的过程中找出满足要求的 个解. public static void nQueen() { //解n皇后问题的Las Vegas算法 刀初始化x x=new int[n+l]; for( int i=0; i<=n; i++)x[i]=0; //反复调用随机放置n个皇后的Las Vegas算法， 直至放置成功 while(! queensLV()); } 上述算法一旦发现无法再放置下一个皇后 ， 就全部重新开始.为此 ，考虑将该随机放置策略 与回溯法相结合 ，以获得更好的效果. 3 两者结合解n皇后问题的优化解决方案 回溯算法和拉斯维加斯算法结合解 n皇后问 题的方案是先在棋盘的若干行 中随机地放置皇 后 ，然后在后继行中用回溯法继续放置 ，直至找 到一个解或宣告失败.随机放置的皇后越多，后 继回溯搜索所需的时间就越少 ，但失败的概率就 解.往往忽略了一个重要事实 :对于 r皇后问题 越大. 的任何一个解而言 ，每一个皇后在棋盘上的位置 与回溯法相结合的解n皇后问题的拉斯维加 无任何规律 ，不具有系统性 ，而更像是随机放置 斯算法描述如下: 的.由此想到可采用拉斯维加斯算法 ，在棋盘上 相继的各行中随机地放置皇后 ，并注意使新放置 的皇后与已放置的皇后互不攻击 ，直至 n个皇后 均已相容地放置好 ，或已没有下一个皇后的可放 置位置时为止. 方法queensLV()实现在棋盘上随机放置 n 个皇后的拉斯维加斯算法. private static Boolean queensLV () { //随机放置n个皇后的Las Vegas算法 rnd=new Random (); int k=1; int count= 1; while ((k<=n)&& (count>0)) 迈 count--O; int j=0; for(int i=1; i<=n; i++) { x[k]=i; if (place (k)) if (rnd.random(++count)一。)j=i;//随机位置 } if (count>0) x[k++] j; } return (count>O);//count>0表示放置成功 } 通过反复调用随机放置 n个皇后的拉斯维加 斯算法 queensLV()，直至找到 n皇后问题的一 public class LVQueenl {static Random rnd; static int n; static int[]x; static int[]Y; } 方法place (k)用于测试将皇后k置于第x[k]列 的合法性.方法 backtrack (t)是解 n后问题的回溯 法.方法queensLV(stopVegas)实现在棋盘上随机 放置若干个皇后的拉斯维加斯算法.其中 1‘ stopVegas <_ n表示随机放置的皇后数. private static boolean queensLV (int stopVegas) { /l随机放置n个皇后Las Vegas算法 //下一个放置的皇后编号 rnd二new Random(); //初始化随机数 int k=1; int count= 1; // 1<=stopVegas<=n表示允许随机放置的皇后数 while ((k<=stopVegas)&&(countVO) 毛 count--O; int j=0; for(int i=1; i<=n; i++) { x[k]=i; if ( place (k)) if ( md.random(++count)二二0)j=i; 刀随机位置 } if(counv0) x[k++]=j; 

58 江汉大学学报(自然科 学版 ) 总第34卷 return (count>O); //countv0表示放置成功 } 算法的回溯搜索部分与解 n皇后问题的回溯 法是类似的，所不同的是这里只要找到一个解就 可 以了. public static void nQueen(int stop) 1刀与回溯法相结合的解n皇后问题的Las Vegas算法 stopVegas=0相应于完全使用回溯法的情形. 表2是当n=12时，关于若干stopVegas值的 统计数据.由表 2可以看出，当 n二12时，取 stopVegas=5，算法效率很高. 表2 解12皇后问题的Las Vegas优化算法中不同的 stopVegas值所对应的算法效率 stopVegas p s e t x=new int[n+1]; y=new int[n+1]; for(int i=0; i<=n; i++){ x[i卜0; y[i]=0; 0 5 262.00 13.00 10.20 33.88 47.23 12 } while(!queensLV (stop)); //算法的回溯搜索部分 backtrack(stop+l); } 表 1给出了用上述算法解 8皇后问题时，关 于不同的stopVegas值，算法成功的概率P;一次 成功搜索访问的结点数平均值 :，一次不成功搜 索访问的结点数平均值e，以及反复调用算法得 到最终找到一个解所访问的结点数的平均值 t=s +(1-p)elp. 表1 解8皇后问题的Las Vegas优化算法中不同的 4 结语 n皇后问题是数据结构和算法设计中的一个 经典问题 ，常采用回溯法解决.而拉斯维加斯算 法解决 n皇后问题利用了每个皇后放置的随机 性 ，这种随机性选择常比最优选择省时.因此拉 斯维加斯算法解决 n皇后问题可在很大程度上降 低算法的复杂度.本文中给出的将回溯法与随机 策略相结合的优化策略，则避免了拉斯维加斯算 法中，一旦发现无法再放置下一个皇后 ，就需要 全部重新开始的缺点 ，从而获得 了更好的算法执 stopVegas值所对应的算法效率 行效率. stopVegas p s e t 1.0000 114.00 1.0000 39.63 114.00 39.63 参 考文献 : [I 1 Alsuwaiyel M H.算法设计技巧与分析[M].北京:电子 0.8750 22.53 39.67 28.20 0.4931 13.48 15.10 29.01 0.2618 10.31 8.79 35.10 工业出版社，2003. [2] 王晓东.计算机算法设计与分析〔M].北京:电子工业 出版社，2001. [31 Lafore R. Java数据结构与算法〔M].北京:中国电力出 0.1624 9.33 7.29 46.92 版社.,2004. 0.1375 9.05 6.98 53.50 0.1293 9.00 6.97 55.93 0.1293 9.00 6.97 55.93 Realization of Las Vegas Optimization Algorithm of N-queens Problem (School of Mathematics and Computer Science, Jianghan University, Wuhan 430056, China) DENG Hong-tao, ZHU Xun Abstract: Introduces the method of using trace-back algorithm to solve the n-queens problem, analyses the character of the Las Vegas algorithm and the application in n-queens problem, and re- alizes the algorithm strategy of the combination of the trace-back and Las Vegas algorithm to solve the n-queens problem, also gives the efficiency analysis. Key words: trace-back algorithm; Las Vegas algorithm; n-queen