n皇后

题目类型

搜索

题目描述

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将n个皇后放在棋盘上（有n × n个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

输入

n

输出

放置的具体方法，以及总共的方法数。

样例输入

4

样例输出

4 1 3
3 1 4 2
2

思路

搜索每一行皇后可以放的位置，具体见代码

上完整代码

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[100];//存储每一行皇后的位置 
int s(int x,int y)//判断皇后在x行的y个位置能否放置 
{
    for(int k=1;k<x;k++)//遍历x行以前的行 
    {
        if((y==a[k])||abs(a[k]-y)==abs(x-k))//判断与前面的皇后是否在同一行或同一对角线 
            return 0;
    }
    return 1;//返回1,表示此位置能放 
}
void f(int x)//计算第x行的皇后的位置 
{
    if(x==n+1)
    {
        for(int i=1;i<=n;i++)
            cout<<a[i]<<" ";//打印皇后所在每一行的位置 
        cout<<endl;
        ans++;//方案数 
        return;
    }

        for(int i=1;i<=n;i++)//遍历每一行的每一个位置 
        {
            if(s(x,i)){//如果满足条件 
                a[x]=i;//记录该行皇后的位置 
                f(x+1);//搜索下一行 
            }
        }

}
int main(){
    cin>>n;
    f(1);//从第一行开始 
    cout<<ans;
    return 0;
}