题目
还是皇后问题
现在需要你求出一共有多少种可能的摆放
并且输出任意一种摆放
1 ≤ n ≤ 13 1\leq n\leq 13 1≤n≤13
思路
由于问题规模很小，考虑dfs可行
开一个数组row[N]，row[i]=j表示第i行的皇后在第j列，再开一个数组book[N+1]，book[i]=1表示第i列已经有皇后。如此一来，行列方向上的皇后对冲不再需要考虑，只需要考虑对角线方向。
逐行测试，将当前行标pos传入dfs。先考虑第pos行的皇后在列上是否与前pos-1行的皇后冲突，这一步通过遍历book[]找到还没放过皇后的列实现。然后再考虑第pos行的皇后在对角线上是否与前pos-1行的皇后冲突。
由于要求输出任意一种可能性，开一个数组tmp[]在每次res++后记录即可。
代码
#include<bits/stdc++.h>
using namespace std;#define N 13int n;
int row[N+1] = {
0}; // row[i]=j表示皇后在第i行j列
int res =0;
int book[N+1] = {
0}; // book[i]=1表示第i列已有皇后int tmp[N+1] = {
0};void dfs(int pos) // 当前在第pos行
{
// for(int i = 0; i < n; i++)// cout<<row[i]<<' ';// cout<<endl;if(pos==n){
// cout<<'*'<<endl;res++;for(int i = 0; i < n; i++)tmp[i] = row[i];return;}int flag = 0;for(int j = 0; j < n; j++)// 枚举每一列{
if(book[j]==0) // 找到没有皇后的列flag = 1;else continue;for(int i = 0; i < pos; i++)// 检查1~pos-1行是否有与当前皇后同一对角线的皇后{
if(abs(pos-i)==abs(row[i]-j)){
flag = 0;break;}}if(flag){
row[pos] = j;book[j] = 1;dfs(pos+1);book[j] = 0;}}
}int main()
{
cin>>n;dfs(0);cout<<res<<endl;if(res){
for(int i = 0; i < n-1; i++)cout<<tmp[i]<<' ';cout<<tmp[n-1]<<endl;}system("pause");return 0;
}```