拉斯维加斯算法 八皇后问题（C++实现）

#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;

//定义一个棋盘，初始化棋盘上没有放置任何王后
bool chess[8][8] =
{
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0},
};

//检测在row,col位置处放置王后是否与之前的王后放置冲突的函数
bool conflict(const int& row, const int& col)
{
    //如果放入的是第一个王后，则一定不会产生冲突
    if (row == 0)
        return false;
    //首先将棋盘上已经成功放置的每一行王后的列位置存入一个向量中
    vector<int> ColPos;
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            if (chess[i][j] == true)
            {
                ColPos.push_back(j);
                break;//由于一行只可能有一个王后，因此找到王后后可以提前终止循环
            }
        }
    }

    //检测当前放置的王后与之前的王后是否位于同一列（不检测同一行是因为算法本身就是一行一行放置的，不可能有两个王后位于同一行）
    for (int i = 0; i < row; i++)
    {
        if (col == ColPos[i])//当存在一个之前的王后和当前所放置列相同时，返回冲突标志
            return true;
    }

    //检测当前放置的王后和之前的王后是否位于同一斜线上，如果是则返回冲突标志
    for (int i = 0; i < row; i++)
    {
        int Row_dif = row - i;
        int Col_dif = ColPos[i] - col;
        if (Row_dif == Col_dif)
            return true;
        if (Row_dif == -Col_dif)
            return true;
    }
    //检测后如果不存在冲突，则返回不冲突标志
    return false;
}

//自定义的基于拉斯维加斯概率算法和回溯法的用于进行王后放置的函数
void Queen(void)
{
    int seed = 1;//制定随机数种子，初始化为1
    srand(seed);//通过循环遍历来手动设置不同的随机情况
    loop:
    for (int i = 0; i < 8; i++)
    {
        //每一次在当前行随机放置一个王后
        int pos = rand() % 8;

        int n = 1;//通过一百次随机数检测，如果仍然有冲突，则由概率原理可知该种情况无解，更换随机数种子进行下一种情况（重新开始摆盘）
        //检测是否与之前放置的王后有冲突，如果有冲突的话则随机放置在本行的另外一个位置
        while (conflict(i, pos) && n < 100)
        {
            pos = rand() % 8;
            n++;
        }
        //当前情况无解时，将当前棋盘清空，更换随机数种子重新摆盘重复上述步骤
        if (n >= 100)
        {
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    chess[i][j] = false;
                }
            }
            seed++;
            goto loop;
        }
        chess[i][pos] = true;
    }
    //输出得到的可行解
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            cout << chess[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int main(void)
{
    Queen();
	return 0;
}