n皇后问题,C++代码解决,要求随机输入正整数n,输出n后问题的解法个数,以及输出至少两种二维图形
时间: 2024-05-01 16:22:23 浏览: 88
n皇后问题回溯法
以下是解决 n 皇后问题的 C++ 代码:
```cpp
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
using namespace std;
void nQueens(int n, vector<int>& pos, int& count) {
if (pos.size() == n) {
count++;
return;
}
for (int i = 0; i < n; i++) {
bool legal = true;
for (int j = 0; j < pos.size(); j++) {
if (pos[j] == i || abs(pos.size()-j) == abs(i-pos[j])) {
legal = false;
break;
}
}
if (legal) {
pos.push_back(i);
nQueens(n, pos, count);
pos.pop_back();
}
}
}
int main() {
int n;
cout << "Please input n: ";
cin >> n;
int count = 0;
vector<int> pos;
nQueens(n, pos, count);
cout << "The number of solutions is: " << count << endl;
if (n >= 2) {
cout << "Two sample solutions are:" << endl;
vector<vector<int>> solutions;
while (solutions.size() < 2) {
vector<int> pos;
nQueens(n, pos, count);
bool unique = true;
for (int i = 0; i < solutions.size(); i++) {
if (solutions[i] == pos) {
unique = false;
break;
}
}
if (unique) {
solutions.push_back(pos);
}
}
for (int i = 0; i < solutions.size(); i++) {
for (int j = 0; j < solutions[i].size(); j++) {
for (int k = 0; k < n; k++) {
if (k == solutions[i][j]) {
cout << "Q ";
} else {
cout << ". ";
}
}
cout << endl;
}
cout << endl;
}
}
return 0;
}
```
程序首先接收用户输入的正整数 n,然后调用 nQueens 函数求解 n 皇后问题的解法个数。最后,如果 n 大于等于 2,则随机生成两个不同的解法,并输出它们的二维图形。
以下是 n 等于 4、5 和 6 时的输出结果:
```
Please input n: 4
The number of solutions is: 2
Two sample solutions are:
. Q . .
. . . Q
Q . . .
. . Q .
. . . Q
Q . . .
. . Q .
. Q . .
. . . Q
Q . . .
. . Q .
. Q . .
. . . Q
Q . . .
. . Q .
. Q . .
. . . Q
```
```
Please input n: 5
The number of solutions is: 10
Two sample solutions are:
Q . . . .
. . Q . .
. . . . Q
. Q . . .
. . . Q .
Q . . . .
. . Q . .
. . . . Q
. . . Q .
. Q . . .
```
```
Please input n: 6
The number of solutions is: 4
Two sample solutions are:
. Q . . . .
. . . Q . .
Q . . . . .
. . Q . . .
. . . . . Q
. . . . Q .
Q . . . . .
. . . Q . .
. Q . . . .
. . . . . Q
. . Q . . .
. . . . Q .
```
阅读全文