217 lines
4.1 KiB
C++
217 lines
4.1 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
vector<vector<int>> solutions;
|
||
|
||
string serialize(const vector<int>& path) {
|
||
string s;
|
||
for (int x : path) s += char(x + '0');
|
||
return s;
|
||
}
|
||
|
||
// 将字符串反序列化回 vector<int>
|
||
vector<int> deserialize(const string& s) {
|
||
vector<int> path;
|
||
for (char c : s) path.push_back(c - '0');
|
||
return path;
|
||
}
|
||
|
||
// 生成旋转 90°（顺时针）棋盘序列
|
||
vector<int> rotate90(const vector<int>& path, int n) {
|
||
vector<int> newPath(n);
|
||
for (int i = 0; i < n; i++) {
|
||
newPath[path[i]] = n - 1 - i;
|
||
}
|
||
return newPath;
|
||
}
|
||
|
||
// 镜像（水平翻转）
|
||
vector<int> mirrorH(const vector<int>& path, int n) {
|
||
vector<int> newPath(n);
|
||
for (int i = 0; i < n; i++) newPath[i] = n - 1 - path[i];
|
||
return newPath;
|
||
}
|
||
|
||
// 生成最小的对称表示
|
||
string canonical(const vector<int>& path, int n) {
|
||
vector<string> forms;
|
||
vector<int> cur = path;
|
||
|
||
// 4 次旋转 + 镜像旋转
|
||
for (int k = 0; k < 4; k++) {
|
||
forms.push_back(serialize(cur));
|
||
forms.push_back(serialize(mirrorH(cur, n)));
|
||
cur = rotate90(cur, n);
|
||
}
|
||
|
||
return *min_element(forms.begin(), forms.end());
|
||
}
|
||
|
||
bool isValid(const vector<int>& path, int row, int col) {
|
||
for (int i = 0; i < row; i++) {
|
||
int prevCol = path[i];
|
||
if (prevCol == col) return false; // 同列冲突
|
||
if (abs(row - i) == abs(col - prevCol)) return false; // 对角线冲突
|
||
}
|
||
return true;
|
||
}
|
||
|
||
//path[i] = j; (i, j)，定行动列
|
||
void dfs(int _n, vector<int>& _path, int _i){
|
||
if(_i == _n){
|
||
solutions.push_back(_path);
|
||
return;
|
||
}
|
||
for(int j = 0; j < _n; j++){
|
||
//检测 插入
|
||
if(isValid(_path, _i, j)){
|
||
_path[_i] = j;
|
||
//调整引用path
|
||
dfs(_n, _path, _i + 1);
|
||
//恢复引用path
|
||
_path[_i] = -1;
|
||
}
|
||
}
|
||
}
|
||
|
||
int main(){
|
||
//考虑先放置每个皇后位i，后面通过移动行/列来确定
|
||
//每个皇后的标志是列(i)，生成的数列是从1 - N行插入了哪列的皇后
|
||
int n;
|
||
cin >> n;
|
||
//vector<vector<int>> mat(n, vector<int>(n, 0));
|
||
vector<int> path(n, -1);
|
||
dfs(n, path, 0);
|
||
for(auto x : solutions){
|
||
for(auto y : x){
|
||
cout << y << " ";
|
||
}
|
||
cout << endl;
|
||
}
|
||
cout << endl;
|
||
|
||
set<string> uniqueSolutions;
|
||
for (auto& sol : solutions) {
|
||
uniqueSolutions.insert(canonical(sol, n));
|
||
}
|
||
|
||
cout << "本质不同解数量: " << uniqueSolutions.size() << endl;
|
||
|
||
// 输出去重后的解
|
||
for (auto& s : uniqueSolutions) {
|
||
vector<int> path = deserialize(s);
|
||
for (int x : path) cout << x << " ";
|
||
cout << endl;
|
||
}
|
||
return 0;
|
||
}
|
||
/*
|
||
8
|
||
0 4 7 5 2 6 1 3
|
||
0 5 7 2 6 3 1 4
|
||
0 6 3 5 7 1 4 2
|
||
0 6 4 7 1 3 5 2
|
||
1 3 5 7 2 0 6 4
|
||
1 4 6 0 2 7 5 3
|
||
1 4 6 3 0 7 5 2
|
||
1 5 0 6 3 7 2 4
|
||
1 5 7 2 0 3 6 4
|
||
1 6 2 5 7 4 0 3
|
||
1 6 4 7 0 3 5 2
|
||
1 7 5 0 2 4 6 3
|
||
2 0 6 4 7 1 3 5
|
||
2 4 1 7 0 6 3 5
|
||
2 4 1 7 5 3 6 0
|
||
2 4 6 0 3 1 7 5
|
||
2 4 7 3 0 6 1 5
|
||
2 5 1 4 7 0 6 3
|
||
2 5 1 6 0 3 7 4
|
||
2 5 1 6 4 0 7 3
|
||
2 5 3 0 7 4 6 1
|
||
2 5 3 1 7 4 6 0
|
||
2 5 7 0 3 6 4 1
|
||
2 5 7 0 4 6 1 3
|
||
2 5 7 1 3 0 6 4
|
||
2 6 1 7 4 0 3 5
|
||
2 6 1 7 5 3 0 4
|
||
2 7 3 6 0 5 1 4
|
||
3 0 4 7 1 6 2 5
|
||
3 0 4 7 5 2 6 1
|
||
3 1 4 7 5 0 2 6
|
||
3 1 6 2 5 7 0 4
|
||
3 1 6 2 5 7 4 0
|
||
3 1 6 4 0 7 5 2
|
||
3 1 7 4 6 0 2 5
|
||
3 1 7 5 0 2 4 6
|
||
3 5 0 4 1 7 2 6
|
||
3 5 7 1 6 0 2 4
|
||
3 5 7 2 0 6 4 1
|
||
3 6 0 7 4 1 5 2
|
||
3 6 2 7 1 4 0 5
|
||
3 6 4 1 5 0 2 7
|
||
3 6 4 2 0 5 7 1
|
||
3 7 0 2 5 1 6 4
|
||
3 7 0 4 6 1 5 2
|
||
3 7 4 2 0 6 1 5
|
||
4 0 3 5 7 1 6 2
|
||
4 0 7 3 1 6 2 5
|
||
4 0 7 5 2 6 1 3
|
||
4 1 3 5 7 2 0 6
|
||
4 1 3 6 2 7 5 0
|
||
4 1 5 0 6 3 7 2
|
||
4 1 7 0 3 6 2 5
|
||
4 2 0 5 7 1 3 6
|
||
4 2 0 6 1 7 5 3
|
||
4 2 7 3 6 0 5 1
|
||
4 6 0 2 7 5 3 1
|
||
4 6 0 3 1 7 5 2
|
||
4 6 1 3 7 0 2 5
|
||
4 6 1 5 2 0 3 7
|
||
4 6 1 5 2 0 7 3
|
||
4 6 3 0 2 7 5 1
|
||
4 7 3 0 2 5 1 6
|
||
4 7 3 0 6 1 5 2
|
||
5 0 4 1 7 2 6 3
|
||
5 1 6 0 2 4 7 3
|
||
5 1 6 0 3 7 4 2
|
||
5 2 0 6 4 7 1 3
|
||
5 2 0 7 3 1 6 4
|
||
5 2 0 7 4 1 3 6
|
||
5 2 4 6 0 3 1 7
|
||
5 2 4 7 0 3 1 6
|
||
5 2 6 1 3 7 0 4
|
||
5 2 6 1 7 4 0 3
|
||
5 2 6 3 0 7 1 4
|
||
5 3 0 4 7 1 6 2
|
||
5 3 1 7 4 6 0 2
|
||
5 3 6 0 2 4 1 7
|
||
5 3 6 0 7 1 4 2
|
||
5 7 1 3 0 6 4 2
|
||
6 0 2 7 5 3 1 4
|
||
6 1 3 0 7 4 2 5
|
||
6 1 5 2 0 3 7 4
|
||
6 2 0 5 7 4 1 3
|
||
6 2 7 1 4 0 5 3
|
||
6 3 1 4 7 0 2 5
|
||
6 3 1 7 5 0 2 4
|
||
6 4 2 0 5 7 1 3
|
||
7 1 3 0 6 4 2 5
|
||
7 1 4 2 0 6 3 5
|
||
7 2 0 5 1 4 6 3
|
||
7 3 0 2 5 1 6 4
|
||
|
||
本质不同解数量: 12
|
||
0 4 7 5 2 6 1 3
|
||
0 5 7 2 6 3 1 4
|
||
1 3 5 7 2 0 6 4
|
||
1 4 6 0 2 7 5 3
|
||
1 4 6 3 0 7 5 2
|
||
1 5 0 6 3 7 2 4
|
||
1 5 7 2 0 3 6 4
|
||
1 6 2 5 7 4 0 3
|
||
1 6 4 7 0 3 5 2
|
||
2 4 1 7 0 6 3 5
|
||
2 4 7 3 0 6 1 5
|
||
2 5 1 4 7 0 6 3
|
||
*/
|