实现代码

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

class Queens {
public:
int nQueens(int n) {
vector<int> pos(n, 0);
int i = 0;
fun(n, pos, i);
return 0;
}

void fun(int n, vector<int>& pos, int i)
{
if (i == n)
{
return;
}
for (int k = 0; k < n; k++)
{
pos[i] = k;
if (check(pos, i))
{
if (i == n - 1)
{
show(pos);
}
else
{
fun(n, pos, i + 1);
}
}
}
}

bool check(vector<int> pos, int i)
{
for (int k = 0; k < i; k++)
{
if (pos[k] == pos[i] || abs(k - i) == abs(pos[k] - pos[i]))
{
return false;
}
}
return true;
}

void show(vector<int> pos)
{
for (int i = 0; i < pos.size(); i++)
{
for (int j = 0; j < pos.size(); j++)
{
if (pos[i] == j)
{
cout<<'+'<<" ";
}
else
{
cout<<'0'<<" ";
}
}
cout<<endl;
}
cout<<endl;
}
};

int main()
{
Queens q;
q.nQueens(8);
}

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

class Queens {
public:
int nQueens(int n) {
vector<int> pos(n, 0);
//        递归方式
//        int count = 0;
//        fun(n, pos, 0, count);
//        return count;

//        非递归方式
return fun2(n, pos);
}

//非递归方式
int fun2(int n, vector<int> pos)
{
int i = 0;
pos[i] = -1;
int count = 0;
while (i >= 0)
{
pos[i]++;
while (pos[i] < n && !check(pos, i))
{
pos[i]++;
}
if (pos[i] < n)
{
if (i == n - 1)
{
count++;
}
else
{
i++;
pos[i] = -1;
}
}
else
{
i--;
}
}

return count;
}

//递归方式
void fun(int n, vector<int>& pos, int i, int& count)
{
if (i == n)
{
return;
}
for (int k = 0; k < n; k++)
{
pos[i] = k;
if (check(pos, i))
{
if (i == n - 1)
{
count++;
}
else
{
fun(n, pos, i + 1, count);
}
}
}
}

bool check(vector<int> pos, int i)
{
for (int k = 0; k < i; k++)
{
if (pos[k] == pos[i] || abs(k - i) == abs(pos[k] - pos[i]))
{
return false;
}
}
return true;
}
};

int main()
{
Queens q;
for (int i = 1; i <= 12; i++)
cout<<q.nQueens(i)<<endl;
}

+ 订阅