【深搜】JYZOJ #399 n皇后问题

蠢萌_小三爷 · 2018-07-26 16:45:24 · 个人记录

问题描述

在一个n×n n×n的国际象棋棋盘上放置n个皇后，使得它们中任意2个之间都不互相“攻击”，即任意2个皇后不可在同行、同列、同斜线上。求N皇后问题的所有放法。

输入格式

一个整数n

输出格式

每行输出一种方案，每种方案顺序输出皇后所在的列号，各个数之间用空格隔开，以及方案数。如果无解输出“no solute!”。

算法分析

这是一道比较经典的深搜题目，先一个一个皇后放置（或者思考为在每一行放置皇后），枚举每个皇后放在哪一行，并同时记录答案，n个皇后全部放完后即可输出答案。

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=100;
int n;bool a[maxn],b[maxn],c[maxn],d[maxn];
int sta[maxn],top=0,ans=0;
void dfs(int x)
{
    if(x>n)//全部放完
    {
        ans++;
        for(int i=1;i<=n;++i)
        {
            printf("%d",sta[i]);
            if(i!=n)printf(" ");
        }
            printf("\n");//输出答案
        return;
    }
    for(int i=1;i<=n;++i)
    {
        if(!b[i]&&!c[i+x]&&!d[i-x+n-1])//可以放置
        {
            b[i]=true;//宣布占领i列
            a[x]=true;//宣布占领x行
            c[i+x]=true;//宣布占领两个对角线
            d[i-x+n-1]=true;
            //注意此时的对角线编号处理
            sta[++top]=i;//记录答案
            dfs(x+1);//放置下一行
            b[i]=false;
            a[x]=false;
            c[i+x]=false;
            d[i-x+n-1]=false;
            --top;//回溯
        }

    }
}

int main()
{
    scanf("%d",&n);

    dfs(1);
    if(ans)
    cout<<ans;
    else
        cout<<"no solute!";
}