LasVegas的特征用拉斯维加斯算法解决8皇后问题

因此通常用一个bool型函数表示拉斯维加斯算法。

void Obstinate(InputType x, OutputType &y){// 反复调用拉斯维加斯算法LV(x, y)，直到找到问题的一个解bool success= false;while (!success) success = LV(x,y);}考虑用拉斯维加斯算法解决N皇后问题：对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。

由此容易想到下面的拉斯维加斯算法。

在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后已相容地放置好，或已没有下一个皇后的可放置位置时为止。

注意这里解决的是找到其中一个方法，求不是求出N皇后的全部解。

这里提前说明一下，否则不好理解。

接下来的这个用Las vegas算法解决N皇后问题，我们采用的是随机放置位置策略和回溯法相结合，具体就是比如八皇后中，前几行选择用随机法放置皇后，剩下的选择用回溯法解决。

这个程序不是很好理解，有的地方我特别说明了是理解程序的关键，大家看时一定要认真了，另外，王晓东的书上先是用单纯的随机法解决，大家可以先去理解书上这个例子。

然后再来分析我这个程序。

不过那本书上关于这一块错误比较多，大家看时要注意哪些地方他写错了。

拉斯维加斯算法解决N皇后代码：依然用到了RandomNumber.h头文件，大家可以去看下第一章，我就不贴出来了。

剩下部分的代码：注意QueensLV()函数是这个程序的精髓所在。

Queen.h头文件#ifndef QUEEN_H#define QUEEN_Hclass Queen{friend bool nQueen(int);private:bool Place(int k); // 测试皇后k置于第x[k]列的合法性bool Backtrack(int t); // 解n后问题的回溯法bool QueensLV(int stopVegas); // 随机放置n个皇后拉斯维加斯算法int n, *x, *y;};#endifQueen.cpp文件#include #include "Queen.h"#include "RandomNumber.h"using namespace std;bool Queen::Place(int k){// 测试皇后k置于第x[k]列的合法性for(int j = 1; j n){for(int i=1; i 0)){count = 0;for(int i = 1; i 0) // -------------②x[k++] = y[rnd.Random(count)]; // 随机位置}return (count > 0); // count > 0表示放置位置成功}Main.cpp主文件：/** Author: Tanky woo* Blog: www.WuTianQi.com* Date: 2010.12.9* 拉斯维加斯(Las Vegas)算法解决N皇后问题* 代码来至王晓东《计算机算法设计与分析》*/#include "Queen.h"#include "RandomNumber.h"#include using namespace std;bool nQueen(int n){// 与回溯法结合的解n后问题的拉斯维加斯算法Queen X;// 初始化XX.n = n;int *p = new int[n+1];int *q = new int[n+1];for(int i=0; i 15)stop = n-15;bool found = false;while(! X.QueensLV(stop));// 算法的回溯搜索部分if(X.Backtrack(stop+1)){for(int i=1; i LasVegas,的,特,征用,拉斯,维,加斯,算法,解决,