题目描述

N 皇后问题（递归函数加DFS）

在 N×N 的棋盘上放置 N 个皇后（N≤10）而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置 2 个皇后），编程求解所有的摆放方法。

输入格式:
一个整数 n。

输出格式:
每行输出一种方案，每种方案顺序输出皇后所在的列号，各个数之间有空格隔开。若无方案，则输出 no solute!

输入样例:
在这里给出一组输入。例如：

4
输出样例:
在这里给出相应的输出。例如：

2 4 1 3
3 1 4 2
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB

样例

4

2 4 1 3 
3 1 4 2 

算法

(递归加DFS) $O(nlogn)$

典型皇后问题，但要DFS

时间复杂度

$O(nlogn)$

参考文献

普通皇后问题和DFS

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n;
bool flag;
int a[105],b[105],c[105],d[105];
void print()
{
    for(int i=1;i<=n;i++)
        cout<<d[i]<<" ";
    cout<<endl;
    flag=1;
}
void dfs(int s)
{
    if(s==n+1) print();
    for(int i=1;i<=n;i++)
        if(!a[s+i]&&!b[s-i+n]&&!c[i])
        {
            d[s]=i;
            a[s+i]=1;
            b[s-i+n]=1;
            c[i]=1;
            dfs(s+1);
            a[s+i]=0;
            b[s-i+n]=0;
            c[i]=0;
        }
}
int main()
{
    cin>>n;
    dfs(1);
    if(!flag)
        cout<<"no solute!"; 
}