147 lines
2.5 KiB
C++
147 lines
2.5 KiB
C++
#include <iostream>
|
||
#include <vector>
|
||
using namespace std;
|
||
vector<vector<int>> result;
|
||
|
||
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){
|
||
result.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 : result){
|
||
for(auto y : x){
|
||
cout << y << " ";
|
||
}
|
||
cout << endl;
|
||
}
|
||
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
|
||
*/
|