算法1
(dfs剪枝) $O(n!)$
递归解法类似_枚举_每一行能够在某一列放置棋子的情况,第i(0索引)行枚举$n-i$列.复杂度很高故而剪枝很重要.我们把已经防止的列、正对角线、副对角线用数组记录下来.
值得注意的是记录数组用固定数组才能过,用动态数组会TLE.
时间复杂度
第i(0索引)行枚举$n-i$列.共$n\*n(n-1)\*…\*1=O(n!)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 26;
int n, cnt;
vector<int> a;
vector<vector<int>> re;
int vis[3][maxn];
void dfs(int cur){
// for(int i = 0; i < n; ++i) cout << a[i]+1 << " ";
// cout << "\n";
if(cur == n){
if(cnt < 3){
re.push_back(a);
}
cnt++;
return ;
}
for(int i = 0; i < n; ++i){
if(!vis[0][i] and !vis[1][cur+i] and !vis[2][cur-i+n]){
a[cur] = i;
vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1;
dfs(cur+1);
vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0;
}
}
}
int main(){
cin >> n;
a.assign(n+1, -1);
// vis.assign(3, vector<int>(2*n, 0));
memset(vis, 0, sizeof vis);
dfs(0);
for(int i = 0; i < re.size(); ++i){
for(int j = 0; j < n; ++j){
cout << re[i][j] + 1 << " ";
}
cout << "\n";
}
cout << cnt << "\n";
}