n皇后问题--拉斯维加斯

#include "iostream"
#include "cmath"
#include "cstdlib"
#include "ctime"
using namespace std;

class Queen
{
public:
friend void nQueen(int);
private:
int *x, *y;  //解向量
int n;       //皇后个数
bool place(int k);  //检查皇后位置合法性
bool QueenLV();
};

bool Queen::place(int k)
{
for(int i=1; i<k; i++)
if(abs(x[i]-x[k])==abs(i-k) || x[i]==x[k])
return false;
return true;
}

bool Queen::QueenLV()
{
//RandomNumber rnd;
int k = 1;  //记录下一个放置的皇后
int count = 1;  //记录当前要放置的第k个皇后在第k行的有效位置数
while(k<=n && count>0)
    {
        count = 0;
for(int i=1; i<=n; i++)
        {
            x[k] = i;
if(place(k))
                y[count++] = i;  //第k个皇后的第k行的有效位置存于y数组
        }
if(count > 0) 
            x[k++] = y[rand()%count];  //从有效位置中随机取一个放置皇后
    }
return count > 0;  //放置成功
}

void nQueen(int n)
{
    Queen queen;  //初始化
    queen.n = n;
    queen.x = new int[n+1];
    queen.y = new int[n+1];

bool success = false;
while(!success)  //反复调用放置n皇后的拉斯维加斯算法，直到调用成功
    {
memset(queen.x, 0, sizeof(queen.x));
memset(queen.y, 0, sizeof(queen.y));

if(queen.QueenLV())
        {
            success = true;
for(int i=1; i<=n; i++)
cout << queen.x[i] << " ";
        }
    }
}

int main() 
{
    srand(time(NULL));
cout << "输入皇后个数：";
int n;
cin >> n;
    nQueen(n);

cout << endl << endl;
return 0;
}